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.