In fact a lot has already been written about this topic so, in order to save you some time, I want to start commenting that there is a machine instruction in the SSE (

*Streaming SIMD Extensions*) set that should be much faster. This instruction is the

**rsqrt,**in fact if we do not seek an exact square root the calculation of

**rsqrt (x) * x**should be faster than the

**sqrt**instruction, although the latter has more precision. Anyway, it is always better to test things out.

If you want to pursue the subject, the algorithm is discussed in this research paper from 2003.

float fastInvSqrt(float x) {

float xhalf = 0.5f * x;

int i = *(int *)&x;

*// Cast the number to integer*i = 0x5f3759df - (i >> 1);

*// Magic number*x = *(float*)&i;

*// Cast result back to float*x = x*(1.5f-(xhalf*x*x));

*// Apply one iteration of the Newton's method*return x;

}

The magic number allows to approximate the inverse square root using integer arithmetic. In order to obtain it properties of logarithms and changes of representation between integer and floating point are used. At the end one iteration of Newton's method is applied.

The explanation is here.

Related entries:

Counting bits