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.
sqrtf
? Without this knowledge, how can we tell whether another algorithm is superior? $\endgroup$