6
$\begingroup$

I am dealing with the problem of computing $ s = \lfloor sqrt(x)\rfloor$ with $x \in [0,30000^2]$. The common sqrtf(x) on C language is too slow for this case, however it always gives me the correct result. I've tried with the Newton's method but I get very small errors when the square root of a number is exact. This leads to an uncertain pattern of $s-1$ results along the interval. If I increase the number of iterations the method becomes too slow but more exact.

Does anyone know of faster methods or directions on the latest research done in the area?

note to clarify: input is idealy a real number (i.e floating point) but i also accept solutions with integer as input.

$\endgroup$
  • 6
    $\begingroup$ How about binary search for $[x]$ in $\{0,1^2, 2^2, ..., 30^2\}$? Or a lookup table for each integer in $\{0,1,2,3,...,30^2\}$? and performing the lookup on $[x]$ (if you can afford that much memory, which does not seem much)? $\endgroup$ – Aryabhata Sep 29 '12 at 5:53
  • 1
    $\begingroup$ What is the algorithm implemented in sqrtf? Without this knowledge, how can we tell whether another algorithm is superior? $\endgroup$ – Raphael Sep 29 '12 at 11:52
  • 1
    $\begingroup$ Raphael, this is not a general square root, this is a square root of a number $x \leq 900$. A general algorithm is useless. As for sqrtf, it could be a (slow) machine instruction. $\endgroup$ – Yuval Filmus Sep 29 '12 at 14:45
  • 2
    $\begingroup$ So you don't want the conceptually fastest method, but the one fastest on your platform in your language? In that case, you should probably ask on Stack Overflow. $\endgroup$ – Raphael Sep 29 '12 at 20:56
  • 1
    $\begingroup$ @labotsirc, The fastest method depends on the range of the integers and on the processor. The theoretically fastest method is sometimes slowest in practice; that is the case, for example, for matrix multiplication. $\endgroup$ – Yuval Filmus Sep 30 '12 at 0:26
5
$\begingroup$

You do not need an exact method, anything with error less than 1 is OK. Say you want to compute $\lfloor \sqrt{x} \rfloor$. This is the largest integer $y$ such that $y^2 \leq x$. Say you have an algorithm $\mathcal{A}$ which on input $x$ outputs $z = \mathcal{A}(x)$ such that $|z - \sqrt{x}| < 1$. You can just:

  • Compute $z = \mathcal{A}(x)$
  • Let $z_0 = \lfloor z \rfloor$
  • Let $S = \{z_0 - 1, z_0, z_0 + 1\}$
  • Output $y = \max\{y \in S: y^2 \leq x\}$ (in words: output the largest integer among $z_0 - 1$, $z_0$, $z_0 + 1$ whose square is at most $x$).

You can also verify you have the correct number by checking that $(y+1)^2 > x$.

Correctness follows from the fact that if $|z - \sqrt{x}| < 1$, then $|\lfloor z \rfloor - \lfloor \sqrt{x} \rfloor| \leq 1$.

I think Newton's method with a small number of iterations is the best thing you can do. Since you only need error smaller than 1, I believe a few iterations will indeed suffice. Doing extra three integer multiplications and comparisons at the end cannot slow you down so much.

$\endgroup$

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.