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