What is complexity of checking whether a natural number is a perfect square? [closed]

As the title says, what is complexity of checking whether a natural number is a perfect square?

• What do you think? Jan 17 '15 at 15:12
• Welcome! While this is indeed a question/answer site, it would help us a lot if you indicated what you tried and where you got stuck, so we could tailor our answers to your level of expertise. Jan 17 '15 at 20:16
• In addition to the other helpful comments, what complexity model do you want to use? Do you want to count bit-operations? Or do you want to treat each addition/multiplication/etc. as $O(1)$ time regardless of how big the operands are?
– D.W.
Jan 18 '15 at 6:50
• Did you mean to ask about the time complexity of checking whether an n-digit natural number is a perfect square? Jan 18 '15 at 18:41

For a given number $n$, binary searching for the square root $\sqrt n$ solves this problem in time $O(\log n)$.

• How? $\:$ (I can't think of any way to avoid having having binary search do $\hspace{1.81 in}$ $\Omega(\log(n))$ additions of $\Omega(\log(n))$-bit numbers.) $\;\;\;\;$
– user12859
Jan 18 '15 at 5:35
• I think multiplication and addition are taken to be $O(1)$ here. In which case this is legitimate.
– Jake
Jan 18 '15 at 8:58

There is a faster way to find (a good approximation of) the square root than the current answer (for 32-bit floating point numbers): a generalization of fast inverse square root (whose generalization you can read more about from this blog post) will give you the square root of a representable number. Normally, if you take the square root of a natural number you could lose some precision in floating point arithmetic of the result, but a perfect square will have its square root perfectly representable because the square root will also be an integer.

• 1. This only works for 32-bit numbers floating point numbers. 2. This does not give the exact square root; it only gives an approximation. Both limitations should be disclosed in your answer. Also, when you are working on fixed-size inputs, asymptotic notation is inappropriate.
– D.W.
Jan 18 '15 at 6:51