Yesterday I have played a bit with reinventing a fast approximation for `sqrt()` in Java. This might be handy with J2ME. Wikipedia has a nice article about Approximations that depend on IEEE representation. My version works, and on my Intel Dual Core with an average error of 1.57%, maximum error 4.02% it is 3.5 times faster than the original sqrt. In addition, it is very simple to improve the precision to 0.000161% average error and 0.000775% maximum error which is then 1.56 times faster than `Math.sqrt()`.

## Sourcecode

I use floating point tricks based on my pow() approximation. Basically I just took the pow() formula and for a^b I substitued `b` with `0.5`, then simplified this as much as possible. As it turns out the result is very simple and short. This initial approximation can be easily made more precise with Newton’s method:

1 2 3 4 5 6 7 8 |
public static double sqrt(final double a) { final long x = Double.doubleToLongBits(a) >> 32; double y = Double.longBitsToDouble((x + 1072632448) << 31); // repeat the following line for more precision //y = (y + a / y) * 0.5; return y; } |

Here is a comparison of the performance and accurancy versus the number of repetitions:

Repetitions | Average error |
Maximum error |
Speedup |
---|---|---|---|

0 | 1.57% | 4.02% | 3.53 |

1 | 0.000161% | 0.000775% | 1.56 |

2 | 2.51e-8% | 3.00e-7 | 0.838 |

With 2 repetitions, the trouble is not worth the effort, as the approximation is already slower than the original Math.sqrt() which is more precise.

1 Comment on "Approximation of sqrt(x) in Java"

I’ve been checking this out and have a few observations.

The method doesn’t deal sensibly with a negative, infinite, or NaN parameter.

The errors become larger than stated for parameters below about 1.9E-308, and become extremely large below about 1.0E-310.

For positive parameters above 1.9E-308 I agree with the error and speedup figures, but find that I get an additional 10% speed improvement (for zero repetitions) by replacing ‘doubleToLongBits’ with ‘doubleToRawLongBits’.

An ‘invsqrt’ method can be created in a similar way from the ‘pow’ approximation, replacing ‘b’ with -0.5 instead of 0.5. This has similar errors, speedup, and limitations to the ‘sqrt’ method.