The famous inverse square root

I’ve already mentioned before that you can approximate divisions using a division-free Newton-Raphson approximation. You can also use the Newton-Raphson method for approximating the square root and the inverse square root function.

But first, what do we actually use inverse square root and square root for? A lot really – everything that uses a normalized vector; collision responses, lightning and reflection to mention a few. It is an important part of any game and the operation has to be as fast as possible. Back in the day when computers had weaker CPUs and no specialized hardware to handle floating point operations (Today we even have specialized physics cards and specialized lightning circuits), some steps had to be taken to compute the inverse square root a million times each second as quickly as possible.

And here it is:

normalize

I could go into details on how this works, but I think it has been described sufficiently on Wikipedia's article Fast inverse square root. Suffice to say that the line with 0x5f3759df is the interesting one, and even to this day we don’t know the origin of it. Several different papers has been written to try and explain where this magic hex code came from.

I included this fast inverse square root function in the Approx.net library (C#).

Comments

Popular posts from this blog

.NET Compression Libraries Benchmark

The Ramer-Douglas-Peucker Polygon Simplification Algorithm

The Power of Wolfram Alpha - Now in a .NET API