c - Is the Carmack/Welsh inverse square root algorithm biased -

c - Is the Carmack/Welsh inverse square root algorithm biased -

when implementing "carmack's inverse square root" algorithm noticed results seem biased. next code seems give improve results:

float invsqrtf(float x) { // initial approximation greg walsh. int = * ( int* ) &x; = 0x5f3759df - ( >> 1 ); float y = * ( float * ) &i; // 2 iterations of newton-raphson's method refine initial estimate. x *= 0.5f; float f = 1.5f; y = y * ( f - ( x * y * y ) ); y = y * ( f - ( x * y * y ) ); * ( int * )(&y) += 0x13; // more magic. homecoming y; }

the key difference in penultimate "more magic" line. since initial results low constant factor, adds 19 * 2^(exponent(y)-bias) result single instruction. seems give me 3 bits, overlooking something?

newton's method produces bias. function 0 found,

f(y) = x - 1/y²

is concave, - unless start y ≥ √(3/x) - newton method produces approximations ≤ 1/√x (and strictly smaller, unless start exact result) exact arithmetic.

floating point arithmetic produces big approximations, typically not in first 2 iterations (since initial guess isn't close enough).

so yes, there bias, , adding little quantity improves result. not always. in part around 1.25 or 0.85 example, results without adjustment improve with. in other regions, adjustment yields 1 bit of additional precision, in yet others more.

in case, magic constant add together should adjusted part x taken best results.

c algorithm math