How to compute 64-bit integer square roots very quickly

From an article section I’ve been working on for the past few days at code codex,

The int version simply casts the result of StrictMath.sqrt to an int, giving us full hardware speed.

The long version uses a trick by Programmer Olathe to get exact results from StrictMath.sqrt even though doubles only have 52 bits precision: StrictMath.sqrt is guaranteed to give the exact result or the exact result plus one. This gets us very near full hardware speed.

longs have 64 bits and Java keeps only the most significant 52 bits when casting to double, so you can lose up to 12 bits.

If the input uses more than 52 bits, the distance between squares is at least (226)2 – (226 – 1)2 = 227 – 1. So, even if you lose the maximum of 12 bits, the distance between perfect squares is much greater than a 12-bit number, and so there cannot be more than one perfect square per “zone” of longs that cast to the same double.

This leaves two possibilities.

  1. There are no perfect squares in the zone, in which case the integer part of sqrt will correspond to the next lowest perfect square, which is great.
  2. There is only one perfect square in the zone, in which case the integer part of sqrt will correspond to that perfect square, and that’s either great or, if our input is less than that perfect square, we simply need to subtract one.

The BigInteger version uses the long version to quickly get the square root of the most significant 64 bits, and then it fills in the remaining bits of the result from most to least significant, checking whether putting a 1 in that place would exceed the input and using 0 instead if that’s the case. It is designed to minimize BigInteger object creation, creating less than two intermediate BigIntegers per output bit.

public class MathTools {
  // floorSqrt :: unsigned long -> unsigned int
  // Gives the exact floor of the square root of x, treated as unsigned.
  public static final int floorSqrt(final int  x) { return (int) StrictMath.sqrt(x & 0xffffffffL); }
  public static final int floorSqrt(final long x) {
    if ((x & 0xfff0000000000000L) == 0L) return (int) StrictMath.sqrt(x);
    final long result = (long) StrictMath.sqrt(2.0d*(x >>> 1));
    return result*result - x > 0L ? (int) result - 1 : (int) result;
  }
}
Advertisements
This entry was posted in Java, Optimization. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s