Fast sqrt in Java at the expense of accuracy

Question

I am looking for a fast square root implementation in Java for double values in the input range of [0, 2*10^12]. For any value in this range, the precision should be upto 5 decimal places. In other words, the result can differ from the Math.sqrt() method after 5 decimal places. However, this method needs to be much faster than Math.sqrt().

Any ideas? Thanks!

Answer 1

Try this

double d = 289358932.0;
double sqrt = Double.longBitsToDouble( ( ( Double.doubleToLongBits( d )-(1l<<52) )>>1 ) + ( 1l<<61 ) );

I haven't benchmarked it, but I'd expect it to be faster. The accuracy isn't extremely good, but try it out and see if it meets your needs. I think you can add an additional bias term a to the end of the expression to make it more accurate.

EDIT: You can drastically improve the accuracy by passing it through a round or two of Newton's method

double better = (sqrt + d/sqrt)/2.0;
double evenbetter = (better + d/better)/2.0;

The second pass gives you almost the exact value of the square root.

sqrt            17022.533813476562
better          17010.557763511835
evenbetter      17010.553547724947
Math.sqrt()     17010.553547724423

Answer 2

I don't believe (without a benchmark to prove this wrong) that a pure Java implementation could me much faster than Math.sqrt(). Both the Oracle JRE implementation and the OpenJDK implementation are native implementations.

Answer 3

Once you give the code time to warm up. Math.sqrt() can be pretty fast

static double[] values = new double[500 * 1000];

public static void main(String... args) {
    for (int i = 0; i < values.length; i++) values[i] = i;

    for (int j = 0; j < 5; j++) {
        long start = System.nanoTime();

        for (int i = 1; i < values.length; i++) {
            values[i] = Math.sqrt(values[i]);
        }
        long time = System.nanoTime() - start;

        System.out.printf("Took %d ns to Math.sqrt on average%n", time / values.length);
    }
}

prints

Took 20 ns to Math.sqrt on average
Took 22 ns to Math.sqrt on average
Took 9 ns to Math.sqrt on average
Took 9 ns to Math.sqrt on average
Took 9 ns to Math.sqrt on average