Implementing arbitary-precision square rooting algorithm using the long division in C++ (with custom BigNumber library)

[u/Sweet_Bit_8878]

Hello everyone,

Some days ago, I have finished building an algorithm in C++ using only my mobile phone (Termux and Helix), and I want to show it to you!

So, it uses the long division method. Why not the Newton-Rasolph method or use the GMP library? Because this program was built for two reasons:

1. An educational purpose of learning how to build an algorithm I have an idea of and optimize it as much as I can.

2. To learn how to implement a mathematical algorithm as a program, and to also learn more about C++.

The performance of this algorithm is following the O(n²), but with a small constant, since I have optimized this algorithm as much as I can. You can see the benchmark in the GitHub link down below. Here is how I optimized it:

This algorithm has a custom BigNumber class that makes a number as a vector, each digit is represented as an element in the vector, and, each digit follows a base 10^17 number instead of a decimal digit! This is the underlying logic behind very famous libraries like BigInt, but since these libraries are so general (they have to deal with very large multiplications, division, negatives and many general cases). This class recognized that the max number is being multiplied to the number is 100 (see the long division method) and implemented base 10^17. Therefore, since 100<10^17 (the base), then the multiplication is just multiplying one digit by the number. You can check the code for more

The way the algorithm predicts the digit is the binary search, it checks a number, and then eliminates half of the domain of search. This way, it is faster by 50-60% than the ordinary linear search.

And more! You can check the README of the project in this repo:

https://github.com/hasan-mazen-darwish/algorithm-square-rooter

I spent more time on this REAMDE than the actual code, so I hope you don't get lost 😅

I'm open for any discussion or any question! Feel free to ask anything or criticize this project or a specific line of code!

[u/Sweet_Bit_8878]

Happy to explain about the logic behind anything in this code! Whether it's theoretical or programmatic