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$
11
  • 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, 2012 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, 2012 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$ Sep 29, 2012 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, 2012 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$ Sep 30, 2012 at 0:26

1 Answer 1

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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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