这个算法是我在大一时候看到的，顿时惊为天人，现在大二了，来补一篇，多少有点纪念意义：D
也可以去我的博客阅读，能跳转双链（如果你想看 IEEE 754 相关的话）
Why care
The cryptic function we see was used to calculate the reverse of square root, namely \frac{1}{\sqrt{c^{2}}}, but why care?
It turns out that if we want to implement physics or lighting in the game engine, it helps when the vector you're calculating with are normalized to have length 1. The length of the vector can be calculated using Pythagorean theorem \sqrt{x^2+y^2+z^2} (in 3D of course), and thus each component will be x \times \frac{1}{\sqrt{x^{2} + y^{2} + z^2}}, you might see where this is going 🙂.
However, even though calculating exponent on computer is easy, doing division is slow and expensive. In a performance-critical scenario such as gaming, this "evil" function can dramatically improve performance (in that particular era).
Aside: Normal vectors are unit vectors aligned perpendicularly to a surface, defining its direction. They are commonly used for lighting, collisions, and other operations involving surfaces. Most of the time we only care about the direction of the light or physics and bringing in magnitude may even bring in some weird bugs, so a normalized vector is all we need. It also helps to separate the direction from the magnitude of your vector. For example, you can keep the speed of a character constant, even when they travel in weird diagonal directions.
But How
It mostly involves [[Binary]] calculation, Newton's method, a few math tricks and [[Floating Point Representation]], an additional blog concerning IEEE 754 can be found [[Introduction to Floating Point Number|here]].
Detailed visual proof can be found Here.
What Now
The first time I saw this algorithm, I was thrilled and immediately compare it with y = 1 / sqrt(x). But it disappointed me, by a lot. This magic function is now 10x slower!!!
Modern compiler, "No one knows optimization better than me".
It is still a good starting point to learn IEEE 754 though.
Aside: In a recent Lex Fridman podcast with Carmack, he actually says that he didn't invent this algorithm, this piece of code was found in the codebase but somehow everyone credits this function to him. He is now an AI researcher in Meta.
References
Vector math — Godot Engine (stable) documentation in English
Fast Inverse Square Root — A Quake III Algorithm - YouTube
Why would you normalize a vector ? : r/gamedev
