4
$\begingroup$

I wanted to know is there any algorithm / function / process through which I can calculate square root of a very large integer number. I wants to know current state of the research in this field.

No approximate methods please.

$\endgroup$
  • $\begingroup$ What do you expect to output if the integer is not a perfect square? $\endgroup$ – xskxzr Sep 13 '18 at 8:20
  • $\begingroup$ if perfect square is not found then not an issue but if there is one then the method must be able to find it. $\endgroup$ – Bhagwan Parge Sep 13 '18 at 8:28
  • $\begingroup$ I am confounded by references to Babylonian/Newton, only. To the point of refusing to stay dumbfounded, and plugging a "real world" reference, somewhere between Newton's and the Shifting_root_algorithm. I don't know about fastest - anybody in a mood to prove there can't be a method faster than her favourite? $\endgroup$ – greybeard Sep 15 '18 at 9:17
3
$\begingroup$

It seems a bit surprising that you did not find the Wikipedia article on integer square root where the Newton's algorithm is described in detail.

Here is the implementation in Python:

def integer_sqrt(n):
    """Compute the integer square root of n, or None if n is not a perfect square."""
    x = n // 2
    while True:
        y = (x + n // x) // 2
        if abs(x - y) < 2: break
        x = y
    return (x if x * x == n else None)

This takes about 0.018 seconds for a 1000 digit number on my MacBook Air. It's not clear why you're asking for the particular range between 200 and 500 digits, but I think you should be able to go on from here, especially if you take the time to read the Wikipedia page.

You may also be interested in the Rosetta Code integer roots page, where you can find fast implementations of integer root algorithms in many languages.

By the way, I just googled "integer square root" to find all of this, except I wrote the Python code.

$\endgroup$
  • 1
    $\begingroup$ For what it's worth, for bignums you can construct a much better starting approximation by splitting the number in half (bitwise). Changing the estimate to x = n & (2**(n.bit_length()//2) - 1) sped up the computation on a 15600 (decimal) digit input from 20 seconds to 100 milliseconds on my machine. That might not be the best way of dividing a number in half in Python; it's just the first one which occurred to me. $\endgroup$ – rici Sep 15 '18 at 2:52
  • $\begingroup$ Thanks @Andrej, this is what I was looking, I thought just like Integer factorization there is no definite algorithm or the algorithm takes time in hours...I asked this question to double check my algorithm which can find square root in O(n*n). I found this algorithm while finding solution for Integer factorization. $\endgroup$ – Bhagwan Parge Sep 15 '18 at 11:05
  • $\begingroup$ just to clear the clouds (why I was not able to find answer early) ... I am not a mathematician...I am a programmer. $\endgroup$ – Bhagwan Parge Sep 15 '18 at 11:10
0
$\begingroup$

That’s quite trivial. First, you use Newton iteration to get the square root of 1/x, which doubles the number of correct digits in each step and uses only multiplications. Multiply the result by x, then calculate the square to see if x equals a square.

No research needed, it’s all quite simple and public knowledge.

You found a website that advises you to use the Newton method for f(x) = x^2 - 612 to find the square root of 612. Use the Newton method for f(x) = 1/x^2 - 612 and you find the square root of 1/612 without any divisions, multiply by 612 and you have the square root of 612.

If you double the precision for each iteration step and use trivial O (n^2) multiplication, it takes $O (n^2)$ with a very small constant factor. If you use FFT for the multiplication (for large n, say a million digits), I'd say $O (n log^2 n)$

With your 100 digit example, double precision gives you a first approximation to $x^{1/2}$ with 15 digit precision, two iterations using 30 and 60 bit precision give you a solution with about 60 digits precision, you round that to the nearest integer and calculate the square with 100 digits precision and you're done. The last step is usually not needed if your result is far enough away from an integer.

$\endgroup$
  • $\begingroup$ if it's trivial then can you provide me link to a online calculator which will solve my problem or at least give me proper hints (& I will save my time). will this be a exact solution or approximate & what is the complexity of this algorithm (in terms of Big O notation) $\endgroup$ – Bhagwan Parge Sep 13 '18 at 14:27
  • $\begingroup$ till the time I will continue searching on net... found many ... en.wikipedia.org/wiki/Newton%27s_method#Square_root_of_a_number $\endgroup$ – Bhagwan Parge Sep 13 '18 at 14:30
  • $\begingroup$ tried wolframalpha.com/input/… but still not able to get result after 15 mins... $\endgroup$ – Bhagwan Parge Sep 13 '18 at 15:02
  • $\begingroup$ @bhagwanparge If I wanted the solution, I wouldn't use an online calculator, I'd write a bit of code. And not Mr. Wolfram's finest hour - square root of a 100 digit integer should be a small number of microseconds. $\endgroup$ – gnasher729 Sep 13 '18 at 21:46
  • $\begingroup$ at least give me a link from where i can build the solution. $\endgroup$ – Bhagwan Parge Sep 14 '18 at 4:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.