README.md

Introduction

The fast inverse square root alogorithim to compute the inverse sqaure root 1\sqrt(x) of a number x. This algorithm was first used in the 1999 first person shooter Quake-III-Arena¹ You can find the original here near line 552.

The Quake Algorithm

We will not go in depth of how this algorithm works here, but basically we attempt inteprete a floating point number x as a integer in orger to approximate $log_2(x)$.

$$log_2(x) \approx \ e_x + m_x + \sigma$$

where

$$\begin{aligned} e_x & = \text{exponent} \\\ m_x & = \text{mantissa} \\\ \sigma & = \text{correction factor}\\\ \end{aligned}$$

And when we interprete it as an integer:

$$I_x = E_x L + M_x$$

where

$$\begin{aligned} I_x & = \text{integer representation of x} \\\ M_x & = m_x L = \text{manttisa as an integer} \\\ E_x & = e_x + B = \text{integral part of exponent} \\\ B & = \text{exponent Bias} \\\ L & = 2^{\text{number of bits in mantissa}}\\\ \end{aligned}$$

By substituting $e_x$ above, we can come up with:

$$log_2(x) \approx \frac{I_x}{L} - (B - \sigma)$$

We take $y = \frac{1}{\sqrt{x}}$ which gives $log_2(y) = - \frac{1}{2} log_2(x)$ When we apply this to the approximation above we get:

$$I_y \approx \frac{3}{2} L (B - \sigma) - \frac{1}{2} I_x$$

And this is the principal behind the quake algorithm. $\frac{3}{2} L (B - \sigma)$ is the "magic constant". In code this correspnods to:

	i  = 0x5f3759df - ( i >> 1 );       // what the fuck?

Q_Square_root

Here I attempt to Calculate the magic number automatically for certain floating point types at compile time using c++ templates and constexpr context. This is the only idea behind this repo.

In Quake.hpp:

constexpr static typename int_type<_T>::type magic_constant(void);

Building and testing

Along with giving a template implementation of the fast inverse sqare root, I have created a main.cpp to test the function. We test the code on both IEC 559 single and double precision. To build the test executable:

make
./build/quaketest 4.0

The syntax for quaktest is:

quaketest [option] <number>

The available options are -d for double precision and -f for single precision.

Footnotes

1. Wikipedia ↩