• Re: Mandatory post: (unregistered) in reply to Bluprintz

You can use such an iterative method for calculating inverse sqrt, but it turns out that 0x5f3759df is a 'near perfect' first guess. You (and the article you posted) missed the magic in this technique: it's treating the number you want to find the root of (an IEEE floating-point number) as an integer, shifting it, and subtracting it from 0x5f3759df .

Most of the articles you'll find by googling '0x5f3759df ' are garbage: the authors miss that the code isn't casting the float to an integer, but taking the pointer to the float, casting that to an int pointer, and dereferencing it. By doing this it creates an int with the same bitfield the float had, instead of an int with the same value the float had.

Treating a float as an int in this way would normally just give you garbage, but the code then goes on and does some real magic: IEEE floating-point numbers are stored as a sign bit, a mantissa and an exponent - (+-)a*2^b , packed into a single bitfield. If you right-shift this bitfield, you'll divide both the mantissa (a), and the exponent(b) by two.

It's this division of the exponent that's interesting: remember that a^n*a^m=a^(n+m), so if you half the exponent, you square-root the number. The subtraction then cleans up the last bit of exponent that might have leaked into the mantissa (the exponent is stored on MSB-end, so if its LSB is one, that would end up as the MSB of the mantissa), sorts out that IEEE floating-point is biased rather than two's complement by subtracting half the bias, negates the exponent so as to give the inverse square root instead of the square root, and does some wizardry on the mantissa as well.

It then uses the same cast trick to get the bitfield back into a float again, and needs to run only a single round of Newton-Raphson iteration to bring the guess close enough to the true value.

The best explanation I've found for what this actually does is http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ , all the others don't even understand what's really going on, let alone why it works.

• Michoel (unregistered) in reply to Vollhorst

That's amazing! it even does negatives!

"The Square Root of 5 is something like -2.2360679774997"

Why didn't they teach us this in school?

• OBloodyhell (unregistered) in reply to JD
JD:
Satanicpuppy:
Heh. Root finding launched me to cult hero status in college, as I managed to be the first person to program my graphing calculator to calculate roots via Newton's Method while showing the work. Made a tedious test question the work of seconds.

Sure it was cheating, but I was a CS major, and I felt it was "better" for my career to be able to hack together the code on my calculator than it was to actually be able to do the math.

Finally, a voice of reason. I'm entirely with you my friend; as a CS student who hated maths I also found it a great deal more beneficial to program maths solutions on my graphical calculator than to figure them out by hand. This was many years ago now and since then, I've re-written (in production apps) plenty of the logic that I originally implemented on my calculator. In contrast, I've never had to work out any of those sums by hand at any time in my programming career. So with the power of hindsight I can say with absolute certainty that it was better from an educational standpoint to "cheat" with my calculator than to "do it properly". QED.

Unfortunately, I don't really have anything relevant to note about today's post. So I'm just going to say thanks for the interactive Javascript root finder - that defnitely added a certain something to the tale for me.

Math is beautiful. Math is gorgeous. Math is what makes us human.

You are not human, you are a well trained monkey, who has learned not to fling poo too often and to push buttons as taught.

;oP

Seriously, though -- if you don't understand the math, you can't understand why things DON'T work, or where the edges of the mathematics break down (and there are always such). This can often be a guideline towards when calculations are wrong.

I've never been one to go for mindless tedium -- that's not math, it's arithmetic. By programming it, though, you're making it clear you understand the process, which is what really matters, there, not the tedium. The tedium is just an uninventive way to show you aren't just plugging numbers into the calculator like... well, a monkey. So programming it does what the instructor (should) want of you (buying it from you does not, so that might be a legitimate "cheating" offense at most universities).

.

• Pseudonymous Coward (unregistered) in reply to Bluprintz
You can use such an iterative method for calculating inverse sqrt, but it turns out that 0x5f3759df is a 'near perfect' first guess.

As opposed to, say, multiplying the number by itself ?-)

• davo (unregistered) in reply to jmroth
jmroth:
city building departments come to us for help in developing codes and standards for the computer age

gimme teh codez :)

gimme teh beamz :)

• Sean (unregistered) in reply to Endo808

Nancy?!?!

• Dave (unregistered) in reply to Marc B

I would think they didn't write the script because it would actually be MORE WORK than maintaining the existing program and wouldn't work any better. (In fact, since it would be a wrapper for a 3rd-party app, it would probably work LESS well, since they don't actually know of the code is garbage or not, and have no way to validate it either way, and the vendor might change the interface in a revision.)

If you look at the recent information release about the code base for a brethaliser commonly used in the US for roadside checks (I hope it made the site) then you see what sort of crap makes it into commercial products all the time, so you have to wonder...