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.