Understanding pointer syntax in fast inverse square root

Question

I have a question that's not so much about the algorithm, but the syntax in the fast-inverse square root:

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...? 
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

I don't understand the lines

i = * (long * ) &y;
y = * (float * ) &i;

I know that "&y" is the memory address of y, but I don't know what "(long * )" means, or what the asterisk at the start is doing.

Technically, `* ( long * ) &y;` is a cast of `&y` (the address of a `float`) to a *pointer to long* `(long*)` and then derefenced to access the value at that address. — David C. Rankin, Jan 29 '18 at 02:35
See [this Stack Overflow question](https://stackoverflow.com/questions/1349542/john-carmacks-unusual-fast-inverse-square-root-quake-iii) and [this Wikipedia page](https://en.wikipedia.org/wiki/Fast_inverse_square_root). — Eric Postpischil, Jan 29 '18 at 03:11
**Note:** This is not good code: Derefencing a pointer using invalid type is *strict aliasing violation* and results in *undefined behaviour*. Do not use this code as example how to do this. — user694733, Jan 29 '18 at 08:48

pcgben · Answer 1 · 2018-01-29T03:38:41.920

1

Let's declare an integer: int foo;

Let's now get the address of foo with the "address of" operator &. The & returns a pointer to -in this case- an integer:

int *bar = &foo;

The example above is storing dereferencing y, and casting the return value to * long, or a pointer to a long int.

edited Jan 29 '18 at 03:38

answered Jan 29 '18 at 02:31

pcgben

726
7
24

score 1 · Accepted Answer · answered Jan 29 '18 at 02:32

The (long * ) is a cast, it's basically telling the compiler hey, treat this float pointer as if it were a long pointer.

The * at the beginning is the unary operator that is used to dereference pointers. Dereference means access the memory through a pointer:

int a = 10;
int *p = &a;

printf("%d\n", *p);

Would print 10. It's the same as doing p[0].

So

i = * (long * ) &y;

is basically doing: treat y as if it were a pointer to long and save the value pointed to by y in i.

What this does is copying the internal bit pattern of the float value to i. Now i will have a value based on that bit pattern.

y = * (float * ) &i;

This does the same thing but with this time with the value of i.

With this code does is modifying the float bit pattern through a long. The code even has in the comment // evil floating point bit level hacking. I cannot tell you how this works, because I don't know the fast inverse square root algorithm.

score 1 · Answer 3 · answered Jan 29 '18 at 03:38

this is an interesting hack based on the x86 representation of 32 bit integer and single precision floating point numbers. Without testing I assume that it really works as some approximation of the function.

The *(long*) conversion of the float number actually takes the bits as represented int the float (exponent and fraction bits) and assigns them to a 32-bit integer in the same order. The address based casting guarantees that that no reformatting would happen on the way, like rounding and the int value will be bit by bit equivalent to the original float value. i.e.

             s exponent fraction
 (float) y = 0 10000000 10010010000111111011011

 i = *(long*) y;

  ==>        long int value 
 (long)  i = 0 10000000 10010010000111111011011

then there is an operation on the int value, including shift right by '1' which affects all bits in the int, moving all exponent and fraction bits right and subtracting it from a constant. I do not understand the logic behind this part, but it results in a new set for the exponent and fraction bits, still preserved in an integer form.

And the next conversion to *(float*) will again make the float bit-by-bit identical to the integer, but will allow the computer to use it as float and do float arithmetic on it.

So, it will work for a set of hardware platforms only and for 32-bit arithmetic only.

Understanding pointer syntax in fast inverse square root

3 Answers3