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 it^{1}. 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 it^{1}.
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 lookup table)? If so, drop us a line, and hopefully we'll put your name up in lights.
