Fast integer square roots in Java

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

Thanks to Paul Hsieh's square root page for the accurate algorithm.

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] |