0x5f375a86 Magic Number

By chance, I came across this magical hexadecimal number 0x5f3759df and decided to make a note of it.

Science changes the world, and mathematics changes science.

Last time, I encountered an irrational number, 0.75, which appeared in the source code of Java HashMap and represents the default load factor. Let me briefly explain the meaning of this value: when the number of elements in the HashMap reaches 0.75 times its capacity (i.e., 12 elements when the capacity is 16), the HashMap will be resized to reduce hash collisions and avoid the degradation of HashMap into a linked list, which significantly increases the query time. As for why this value is 0.75, there is a simple explanation: it is a compromise between improving space utilization and reducing query costs, mainly based on the Poisson distribution, and 0.75 minimizes collisions.

Well, I can accept this explanation and the value of 0.75, but I simply cannot imagine how 0x5f3759df is derived. Here is some background information and source code introduction about this magic number, partly quoted from a post on Zhihu: What is the mathematical basis of the constant 0x5f3759df in the fast inverse square root algorithm?, and another blog post: The mathematical principle behind 0x5f3759df; you can also read the Chinese version here: The Beauty of Mathematics: The magical number 0x5f3759df in the fast inverse square root algorithm.

Quake-III Arena is one of the classic games of the 90s.
Not only does this series have great graphics and content, but it also runs extremely smoothly even on low-end computers. This is thanks to the developer of its 3D engine, John Carmack. In fact, as early as the DOS era in the early 90s, when even a small animation on a PC could amaze people, John Carmack released the groundbreaking Castle Wolfstein, and then continued to innovate with doom, doomII, Quake... each time pushing 3-D technology to the limit. His 3D engine code is extremely efficient, squeezing every computational instruction of the PC. Even MS had to listen to his opinions and made many modifications to Direct3D.

This magical number appears in the underlying code of this 3D engine, and its purpose is to calculate the square root of a number and take its reciprocal. Tests have shown that this code is 4 times faster than (float)(1.0/sqrt(x)):

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

#ifndef Q3_VM
#ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
    return y;
}

About Iterative Method

The iterative method calculates new values based on old values, repeating the process, which is very suitable for computer languages.
The most classic iterative algorithm is the Euclidean algorithm (also known as the Euclidean division algorithm), which is used to calculate the greatest common divisor of two integers, a and b. Its calculation principle relies on the following theorem:

gcd(a,b) = gcd(b,a mod b)

In addition to this, common examples like the Fibonacci sequence can also be calculated using the iterative method. Generally speaking, recursive algorithms have good readability but often require more overhead. In such cases, recursion can be converted into iteration to achieve higher efficiency. I have deeply felt this when solving algorithm problems.

About Newton's Iteration Method

Introduction: Newton's Iteration Method - Baidu Baike
The idea from 300 years ago still shines today. Mathematics is indeed the cornerstone of civilization.
The general sqrt algorithm uses Newton's iteration method, which continuously approximates the root of f(x) = a using x - f(x)/f'(x).

To put it simply, when calculating the square root, f(x) = x^2 = a, f'(x) = 2*x, and f(x)/f'(x) = x/2. Substituting f(x) into x - f(x)/f'(x), we get (x + a/x)/2. Now let's choose a = 5 and an initial guess of 2. We can calculate as follows:

1. 5/2 = 2.5; (2.5 + 2)/2 = 2.25;

2. 5/2.25 = 2.22; (2.25+2.22)/2 = 2.235;

3. 5/2.235 = 2.23713; (2.235+2.23713)/2 = 2.236065;

In just three steps, the value we obtained is very close to sqrt(5) = 2.23606797. It can be foreseen that by repeating this process, the result will converge to sqrt(5). Generally, after iterating 4 to 7 times, a relatively accurate value can be obtained. This is based on the assumption that the initial guess is relatively inaccurate. In theory, as long as the initial guess is accurate enough, the number of iterations can be greatly reduced. This is where the number 0x5f3759df comes into play.

For the specific derivation process, you can refer to the blog mentioned above. Here, I would like to quote the conclusion at the end, which also arouses my curiosity about game engines.

So magical, so strange, so contrary to common sense, so in line with common sense, so beautiful.

We have delved deep enough, at least I am satisfied, and there is nothing more to explore. Through this exercise, I have mainly learned that the bitwise conversion operations between integers and floating-point numbers are not meaningless. They are peculiar but economical numerical operations that are useful in calculations. I believe there are still more undiscovered uses for them.

This post is translated using ChatGPT, please feedback if any omissions.