4

I found a very complex function this is an implementation of Fast inverse square root. I honestly do not understand how this function works but the following conversion between a long and a float has caught my eye:

i  = *(long *) &y;

And I leave the full code

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

    x2 = number * 0.5F;
    y  = number;
    i  = *(long *) &y;                      
    i  = 0x5f3759df - (i >> 1);            
    y  = * (float *) &i;
    y  = y * (threehalfs - (x2 * y * y));  

    return y;
}
lost_in_the_source
  • 10,998
  • 9
  • 46
  • 75
CooperJames
  • 79
  • 7
  • 1
    @AShelly: Personally, I don't see this as a duplicate. This is a much, much narrower question. – NPE Jan 04 '15 at 18:06

1 Answers1

7

The cast simply reinterprets the bits of y as a long so that it can perform integer arithmetic on them.

See Wikipedia for an explanation of the algorithm: Fast inverse square root.

The code makes use of the knowledge that, on the target platform, sizeof(long) == sizeof(float).

@R.. also helpfully adds the following in a comment:

It's also invalid C -- it's an aliasing violation. A correct version of this program needs use either memcpy or possibly (this is less clear that it's correct, but real compilers document support for it) union-based type punning. The version in OP's code will definitely be "miscompiled" (i.e. in a way different than the author's intent) by real compilers though.

This means that the code is not only architecture-specific, it is also compiler-specific.

Community
  • 1
  • 1
NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • 2
    It's also invalid C -- it's an aliasing violation. A correct version of this program needs use either `memcpy` or possibly (this is less clear that it's correct, but real compilers document support for it) `union`-based type punning. The version in OP's code will definitely be "miscompiled" (i.e. in a way different than the author's intent) by real compilers though. – R.. GitHub STOP HELPING ICE Jan 04 '15 at 17:20
  • @R.. - Thank you, I've added this to the answer (with attribution). – NPE Jan 04 '15 at 17:23
  • @NPE: where I can get more information about what you say – CooperJames Jan 04 '15 at 17:24
  • @CooperJames: Which part of it? ;-) – NPE Jan 04 '15 at 17:24
  • @CooperJames: I've added some links to the answer that might be helpful. – NPE Jan 04 '15 at 17:26
  • @NPE: more information on "cast simply reinterprets the bits" – CooperJames Jan 04 '15 at 17:37
  • 1
    @CooperJames: The same 32-bit pattern can be interpreted as an integer and as an IEEE float. The code takes the bits of the 32-bit float it is given, and looks at them as if they were the bits of a 32-bit integer. It then performs integer arithmetic on those bits to do its magic. – NPE Jan 04 '15 at 17:39
  • 2
    The only endianness assumption is that floating point and integer endianness match. This is, in practice, always true. – R.. GitHub STOP HELPING ICE Jan 04 '15 at 17:52
  • What's not true in practice is the assumption that `long` is 32-bit. `uint32_t` should be used instead. – R.. GitHub STOP HELPING ICE Jan 04 '15 at 17:53
  • @R.. The endianness matters in the magic constant, no? – NPE Jan 04 '15 at 17:57
  • @NPE: Nope. The constant is exactly the same for a little or big endian system as long as both integer and floating point types have matching endianness. It would only be wrong if they differed from each other. – R.. GitHub STOP HELPING ICE Jan 04 '15 at 18:02
  • @R.. Hm, I need to ponder this further. I'll delete that point from the answer until I've had a chance to think this through. – NPE Jan 04 '15 at 18:05