Fast integer square roots in Java

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¹.

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¹.

• SquareRoot.java - fast integer square root class;
• SquareRootTest.java - basic speed and accuracy test class.

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.

[1: your mileage may vary]