0
$\begingroup$

I am working on something that requires checking a very large natural number $x$ to determine if it is the square root of an even larger natural number $y$. So I am wondering what are the fastest algorithms for computing square and square root, and how should I be approaching this i.e.

  1. Computing $\sqrt{y}$ and comparing it with $x$
    OR
  2. Computing $x^2$ and comparing it with $y$

So as to write a code that has minimum time complexity.

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ You can compute $x^2$ in $O(n \log n)$ time using FFT. The fastest I personally know of for $\sqrt y$ is $O(n^2)$. $\endgroup$
    – user114966
    Jan 31 at 15:49
  • $\begingroup$ @Dmitry with $n$ being the number of digits or the number itself?, but then the worst-case scenario for comparison of the $x^2$ and $y$ is unknown.I believe that the worst-case scenario for comparison should get reduced as $y$ gets larger because the distances between perfect squares increase as the numbers get larger $\endgroup$
    – Romantic Electron
    Jan 31 at 16:19
  • $\begingroup$ $n$ is the number of digits, yes. distances between perfect squares increase - I don't understand what you want to say. You can compare two numbers in $O(n)$ time. $\endgroup$
    – user114966
    Jan 31 at 17:09
  • $\begingroup$ You seem be taking an A/B approach: while it is sufficient for checking a larger number $L$ to be the square of a smaller one $s$ to have $s^2$ or $\sqrt L$, neither is necessary in all cases. You can pre-check L for not possibly being a square. Using uniform positional presentations, a square is twice as long or one "digit" shorter. You can stop computing the square if you check digit after digit starting from the least significant one (providing the squaring method gives its result in a suitable order). $\endgroup$
    – greybeard
    Jan 31 at 17:11
  • $\begingroup$ (Did I just let on I don't see a multiplication method generating "digits" most significant to least?) $\endgroup$
    – greybeard
    Jan 31 at 17:13
1
$\begingroup$

There is a simple randomized test: pick a random 32-bit prime $p$, and test whether $x^2 \equiv y \pmod p$. Do this a few times for a few random primes $p$. (You can even pick a random number $p$ without requiring it be prime.) If there is any error in your square root, then it is likely that it will be detected by this test. The chances of failing to detect an error is exponentially small.

Improve this answer
$\endgroup$
1
$\begingroup$

If you want to write the code with minimum time complexity, and you ask about it here, then you can't write it. If you ask about the simplest code with a better than quadratic time complexity, look up the Karatsuba method for fast multiplication, and possibly the Toom-Cook method.

In principle, the fastest square root algorithm and the fastest multiplication algorithm will have the same time complexity until we find a multiplication algorithm faster than O (n log n) since the square root can be calculated using few multiplications of n bit, n/2 bit, n/4 bit etc. numbers. But your problem is easier solved using multiplication.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Fun fact: If you're computing a square, rather than a general multiplication, Karatsuba's method has the same sub-quadratic complexity as Babbage's method (and Babbage's method has lower constant factors!). There's no reason to think that computing the square of a number has the same computational complexity as multiplying two general numbers, because there are more subproblems that can be shared. $\endgroup$
    – Pseudonym
    Feb 2 at 0:39
  • $\begingroup$ @Pseudonym The asymptotic ("big-O") complexity of squaring and multiplication is identical. Since general multiply can be reduced to squaring via $XY = ((X + Y)^{2} - (X^{2} + Y^{2}))/2$, in practical terms $T_{multiply}\le3T_{square}+O(n)$. $\endgroup$
    – njuffa
    Feb 2 at 0:54
  • $\begingroup$ @njuffa Sorry, I completely messed up my reasoning on that point. Never mind! $\endgroup$
    – Pseudonym
    Feb 2 at 5:25
1
$\begingroup$

D.W.'s suggestion is absolutely worth doing if you expect the answer to be "false" a significant proportion of the time. With very little effort, you will be able to calculate most of the "no" answers quickly.

You're not really asking about the complexity of computing a square or a square root, because the problem that you're actually trying to solve is to test if some specific number is the square of another specific number. This problem is known to be solvable in close-to-linear time.

Interestingly, integer root classification is also solvable in close-to-linear time. For example, Bernstein's paper below shows that given $y$, we can find an $x$ and $k\ge 2$ such that $x^k = y$, or show that they do not exist, in $O(n\,e^\sqrt{\log n \log \log n})$ time.

See:

Improve this answer
$\endgroup$
3
  • $\begingroup$ You mention testing if it is a square is solvable in close-to-linear time; might you be willing to edit your answer to explain how to solve it that rapidly? $\endgroup$
    – D.W. ♦
    Feb 2 at 4:12
  • $\begingroup$ @D.W. I haven't really taken the time to understand the algorithm, so I'm probably not the person to give an explanation. It's all in the linked papers. $\endgroup$
    – Pseudonym
    Feb 2 at 5:27
  • $\begingroup$ Ahh, I see, you meant solvable using those papers. OK, got it. Thanks. $\endgroup$
    – D.W. ♦
    Feb 2 at 6:11

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.