Fast integer square roots in JavaHere are several fast integer square root methods, written in Java, including:
sqrt(x) agrees completely with (int)(java.lang.Math.sqrt(x)) for x < 2147483648 (i.e. 2^31), while executing about three times faster than it1.
fast_sqrt(x) agrees completely with (int)(java.lang.Math.sqrt(x)) for x < 289 (and provides a reasonable approximation thereafter), while executing about five times faster than it1.
This code has been placed in the public domain.
Can you improve on the speed or accuracy of these methods (without chewing an "unreasonable" quantity of cache with a huge look-up table)?
If so, drop us a line, and hopefully we'll put your name up in lights.