Fastest square root method with exact integer result?

Problem Detail: 

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.

Asked By : labotsirc

Answered By : Sasho Nikolov

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4789