0
$\begingroup$

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

$\endgroup$

closed as unclear what you're asking by Luke Mathieson, D.W., David Richerby, hengxin, Ran G. Jan 18 '15 at 16:25

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ What do you think? $\endgroup$ – Yuval Filmus Jan 17 '15 at 15:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Rick Decker Jan 17 '15 at 20:16
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Jan 18 '15 at 6:50
  • $\begingroup$ Did you mean to ask about the time complexity of checking whether an n-digit natural number is a perfect square? $\endgroup$ – Francesco Gramano Jan 18 '15 at 18:41
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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.) $\;\;\;\;$ $\endgroup$ – user12859 Jan 18 '15 at 5:35
  • $\begingroup$ I think multiplication and addition are taken to be $O(1)$ here. In which case this is legitimate. $\endgroup$ – Jake Jan 18 '15 at 8:58
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jan 18 '15 at 6:51

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