InvSrqt (C code)

Post Reply New Topic

some guy i was tutoring in math showed me this. i found it veryyyyy interesting:

because he wanted to know where calculus was going, so i showed him a lot of the really interesting things Newton did. this was one for approximating roots.

i derived that for him, showed him how it works, and why its good. he then referred me to this code i posted already.
now even if your not a c programmer (i also am not a c programmer, just program in a couple languages as a hobby) you should have a basic idea of what its doing just by looking at it. its taking a float and casting the pointer to it, to be an int, so even through its a float it is now referred to as an int, allowing bit shifting. after the shifted int it is turned back into a float, it has guessed an initial guess point for newtons method and done the first step.
a float is a 32bit number that has a decimal in it. it works like scientific notation.

the bit shifting moves the least significant bit from the expoent and makes it the most significant bit in the base, while the bass looses its least significant bit, dividing it by 2 and subtracting 1 if it is off. its almost moving the sign bit into the exponent, but thats 0 for positive anyways.
this still does not explain how it works, and how it works so well.

i would be interesting in any insight anybody has about how this really works.

Hrm, let me think. That just looks weird. What the heck is the constant 0x5f3759df?? If you do an integer style shift on a float, bit will leak from the sign to the exponent (Actually not a problem if we assert that x=>0) and from the exponent to the mantissa.
What I'm doing now is to google for 0x5f3759df, and I recommend you to the same. Hopefully the algorithm is described somehwere.

its not described anywhere, i have read that attempted explanations are wrong.
the original coder of this is also unknown.
it works off something to do with how the 32bit x86 cpu physically works.
that constant and a bit shift is giving an initial guess and applying 1 step of newtons method on the guess. if u check the value of x when it turns back into a float it will already be very close. then after it does the math it gets even closer. what i am curious about is how this step works.

A guy called Greg Walsh is attributed with the code

It is an abysmal hack. It is totally dependent on so many uncontrolled factors, the least of which is which flavour of float might be the default "float" and ditto for "int". It totally ignores any bad inputs (negative, unnormal, etc). It is inaccurate and slower than other methods. It gets zero and infinity wrong.

Other than that, it's quite fun. See http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf for an analysis of how it works. It's just not very clever. It's vaguely useful if you require a fairly rough and ready approximation (about 0.2% relative error) and your FP processor doesn't have an inbuilt square root.

For a better explanation about this than Lomont's paper, check out http://www.mceniry.net/papers/Fast%20In ... 20Root.pdf