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!

Solution 1

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.

Solution 2

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

Solution 3

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

Comments

[Luiggi Mendoza]

Have you looked anything on internet before asking here? What did you get?

[Paresh]

@LuiggiMendoza Mostly C and assembly level hacks, most of which rely on a float value being 32 bit

[Luiggi Mendoza]

Have you read here?

[Paresh]

@LuiggiMendoza Yes. However, the max error is 4%, which means it will make a huge difference when the input is 10^12.

[Dreamer78692]

There are alot of resources on the internet.... codeproject.com/Articles/69941/… and en.wikipedia.org/wiki/Methods_of_computing_square_roots and stackoverflow.com/questions/1623375/…

[Luiggi Mendoza]

@Paresh 4% the first time, if you read the repeat the following line for more precision and the explanation, you would have a better and fastest sqrt method. Still, it's up to you.

[Antimony]

Have you profiled? Are you sure that sqrt is the bottleneck? Sqrt is already pretty fast. I believe modern computers have dedicated hardware for it. If you want something faster, you'll probably have to descend to assembly level hacks.

[Luiggi Mendoza]

If these methods still don't convince you, you can always call a C/C++ method from Java using JNI

[Paresh]

@Dreamer78692 Thank you. As I mentioned above, in the first link, all the fast methods (1, 2, 3, 6, 7, 13, 14) either assume a 32 bit float, or are assembly level codes. Some of the methods in the wiki link are already implemented in the first link, and are slower. I have not adapted the Babylon method to Java double, and was hoping if someone knew a good implementation already.

[GraphicsMuncher]

Perhaps this is a long shot, but is the sqrt() necessary? Can you modify something somewhere else to deal with the squared value? Getting rid of a sqrt for the price of a * is always a good idea.

[Paresh]

@LuiggiMendoza Thank you! I did read the repeat part, and I have benchmarked it too. For getting the accuracy I need, I need to use that line 2 times atleast, which makes it considerably slower than Math.sqrt(). Which probably is in line with what Antimony mentions about sqrt already being fast.

[starblue]

There's nothing wrong with 32 bit floats if you want 5 digits precision.

[Paresh]

@GraphicsMuncher Yes, that was my first thought too. I tried to remove the need for sqrt() but could not. I need to compare two values (say a and b), and consider them equal if they are within some delta of each other. However, if all I have is the squares of a and b, then I am unable to check if they are equal within that delta.

[Paresh]

@starblue But I am working with double values. Or are you suggesting that I cast them to float? Is it a good idea to do that?

[Paresh]

I see! I was hoping that sacrificing accuracy might yield a faster method.

[tskuzzy]

After JIT'ing, Java code can be as fast as native code. Not always, but it can be.

[Paresh]

Thanks! It definitely is orders of magnitude faster if used without the Newton's method. But it is also very inaccurate. Each iteration of Newton's method seems to add an incredible amount of time: I suppose it may be due to division being expensive. 2 iterations gives the required accuracy, but makes it slower than Math.sqrt(). I guess I will have to live with Math.sqrt() after all!

[starblue]

Each iteration doubles the number of correct digits. better already has 7 digits accuracy.

[Paresh]

@starblue I require 5 decimal places of accuracy, not 5 digits. better is accurate only upto 2 decimal places. evenbetter does the job but ends up being slower than Math.sqrt().

[Paresh]

After some experimentation, it turns out, for the required accuracy, Math.sqrt() is the best option afterall!

[Joe C]

I found this works for a good approximation, Double.longBitsToDouble(((Double.doubleToRawLongBits(number) >> 32) + 1072632448 ) << 31); If you're working with number above 100,000 use this 1072679338 number over the 1072632448 because it will be more accurate.

[BrainSlugs83]

In my own tests -- on average -- this appears to be the same speed as Math.sqrt (before the extra passes).

[Santosh Tiwari]

Instead of dividing by 2.0, multiply by 0.5 to make it tiny bit faster.