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!

Yankeeism

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

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

Have you read here? – Bureaucratize

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

There are alot of resources on the internet.... codeproject.com/Articles/69941/… and en.wikipedia.org/wiki/Methods_of_computing_square_roots and #1623875 – Ovid

@Yankeeism 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. – Bureaucratize

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. – Debauched

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

@Ovid 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. – Yankeeism

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. – Joon

@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. – Yankeeism

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

@Joon 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. – Yankeeism

@Hardener 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? – Yankeeism

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

Apathy

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

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

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

Answer 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

Winstonwinstonn

Answer 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

Hiett

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! – Yankeeism

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

@Hardener 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(). – Yankeeism

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. – Lashing

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

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

For sqrt of values ranging from 100 to 10000 the error is only about 1% by my quick debugging. Thanks! Very useful for quick distance metric in tracking application. Is there an equivalent float version? – Hallsy