8

I need to write program to find the integer square root of a number which is thousands of digits long. I can't use Newton Raphson as I don't have data types to store and divide such large numbers. I am using a long array in C to store the number. Is there any algorithm to find the square root by maybe iterating over the digits?

Edit:

I can't use external library like GMP.

Naman
  • 2,569
  • 4
  • 27
  • 44
  • 1
    See [wikipedia](http://en.wikipedia.org/wiki/Methods_of_computing_square_roots). – Alex VII May 25 '14 at 11:55
  • @alexvii The method given there for decimal base requires to find x(20*p+x), but since my digit is very large, p will also be large and calculating such value might be very slow. I was wondering if there's any method which won't require me to multiply such large numbers. – Naman May 25 '14 at 12:53
  • 1
    Are you allowed to bring in external libraries? Because [GNU Multiple Precision Arithmetic Library](https://gmplib.org/), among others. – Wayne Conrad May 25 '14 at 13:19
  • 2
    "I don't have data types to store and divide such large numbers" Then why not get such a type? There are readily available libraries for the task. In the end you will at least need to be able to do multiplication or division and both of these are not easy to implement fast manually (think FFT) – Niklas B. May 25 '14 at 13:42
  • 7
    You're trying to run before you walk. If you can't write your own code that adds two enormous numbers then it is premature to work on square roots. My advice is that you write yourself a library of methods that adds two enormous numbers together, and then work your way up from there: subtraction, multiplication, division, remainder and *then* square roots. – Eric Lippert May 25 '14 at 14:28
  • https://en.wikipedia.org/wiki/Methods_of_computing_square_roots but it's better use an arbitrary precision library such as GMP – phuclv May 25 '14 at 14:51
  • http://stackoverflow.com/questions/4930307/fastest-way-to-get-the-integer-part-of-sqrtn – phuclv May 25 '14 at 14:55
  • @EricLippert I have written code for adding, subtracting and multiplying large numbers. My problem is that I can't divide a very large number with another very large number because that will be very slow. That's why looking for an algorithm that can do it digit by digit. – Naman May 25 '14 at 15:19
  • @Naman: Computing `x(20p+x)` only requires multiplying a big_number by a digit, which can be easily be computed in time `O(|p|)` (where `|p|` is the length of `p`). Since the algorithm generates one digit on each iteration, and the number of digits in the square root of `p` is roughly `|p|/2`, the total time will be `O(|p|^2)`, which should be acceptable. It's important to find a good estimate for `x`, so that you don't have to do the trial multiplication too many times. – rici May 25 '14 at 15:29
  • @rici I agree, I'll try this. – Naman May 25 '14 at 15:39
  • [An efficient algorithm to calculate the integer square root (isqrt) of arbitrarily large integers](http://stackoverflow.com/questions/21657491/an-efficient-algorithm-to-calculate-the-integer-square-root-isqrt-of-arbitrari?rq=1) – phuclv May 25 '14 at 15:40
  • @rici One last question, is the digit by digit calculation possible at higher base like 10^8 or something? – Naman May 26 '14 at 08:47

3 Answers3

2

If you can input the target number, then you must have a way to store at least one such large number. For Newton-Raphson you only need to be able to halve and add numbers. Think of a way to halve a number without using division.

ETA: Correction: division can be avoided by doubling and subtraction.

rossum
  • 15,344
  • 1
  • 24
  • 38
  • 2
    How do you use Newton-Raphson without dividing? The iteration is `x' = (x + S/x)/2` which involves computing `S/x` each time (as well as the addition and halving). – rici May 25 '14 at 15:22
  • You can't do Newton Raphson without divide. What you are mentioning is Binary Search method. But there also i'll have to check whether my estimated number is correct by squaring it and comparing it with given number, which is a hard task with very large numbers. – Naman May 25 '14 at 15:25
  • @rossum I am confused, how will you avoid division in Newton Raphson by 'doubling and subtraction'? Are you talking about Binary Search method? – Naman May 26 '14 at 08:49
  • @Naman You can use doubling and subtracting to build an integer division method. You could do it with subtracting alone, but that would be very slow. – rossum May 26 '14 at 11:38
2

You seem to have a lot of very unrealistic constraints on your 'bignum' implementation. I might suggest a binary search? At each iteration, find the 'half-way' value mid = (hi + lo) / 2, and prune the search space as [hi, mid], or [mid, lo] depending on the square of those values.

Not as fast as NR, etc. But should converge with careful treatment of squaring range values...

Brett Hale
  • 21,653
  • 2
  • 61
  • 90
1

You can implement long division method to compute square root which is being taught at school. You can implement this method for base 10 and the result is computed digit by digit from left to right. You can stop once integer part is calculated.

Calculation of squareroot

Mohit Jain
  • 30,259
  • 8
  • 73
  • 100
  • 1
    I was trying this method but the problem is that divisor gets bigger and bigger. And if my given number is of thousand of digits then dividing and finding remainder will be very hard. – Naman May 25 '14 at 15:30
  • 1
    You can store numbers into c-strings (character arrays terminate by a `NUL` character) and perform arithmetic the way we do on papers. I wrote [this example](http://codepad.org/T2AcSJzN) years ago for addition and multiplication. Gradually I kept adding functionalities and cutting down redundant time with aid of profiling and after few months ended up with an efficient big number library. If you don't want to use a third party big-integer library, then write one for yourself using basic arithmetic concepts and make it rugged and efficient. – Mohit Jain May 25 '14 at 15:43
  • For this method you need only Multiplication and Substraction operations. – Mohit Jain May 25 '14 at 15:44
  • 1
    I agree, I will try this method. And this method might be efficient also since it requires multiplication of large number with a single digit number. Just wondering whether this is the standard approach for this problem? – Naman May 25 '14 at 16:11