More Bit-Shifting Examples: The Fast 1/sqrt()

[DelSquared]

Back in the late 90s, the game Quake III was very influential in the computer graphics sector by taking huge advantage of bit-shifting in order to estimate the value of y=1/√x many times per frame for lighting calculations and to normalise vectors.

The original code was written in C meaning it makes heavy use of pointers so off the top of my head I don't know if an equivalent algorithm can be implemented in Java/Javascript. However if so, it would be a good way to demonstrate the power of bit-shifting beyond the 8 segment display and simple halving.

Because the code was requested in the comments (copied from here and re-commented):

float Q_rsqrt( float number )
{
        //personally not too fond of all these variable declarations (like "threehalfs")
        //but that's how it is usually presented so I just went with it
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;

        //Below is the magic part, not sure what is happening but it seems to be converting y to long
    i  = * ( long * ) &y;

        //Bitshifting the exponent to divide it by 2 (hence applying sqrt). This is what makes it fast
    i  = 0x5f3759df - ( i >> 1 );

        //Turning the value back to float
    y  = * ( float * ) &i;

        //1st iteration of Newton-Raphson Method
    y  = y * ( threehalfs - ( x2 * y * y ) );   

        //2nd iteration, this is optional unless great precision is required
        //alternatively more can be added if more precision is needed
    y  = y * ( threehalfs - ( x2 * y * y ) );   
    return y;
}

[lazycuh]

Posting the original code here would be helpful

[AlcaDesign]

Here's an article on Wikipedia: https://en.wikipedia.org/wiki/Fast_inverse_square_root With an overview of the code and a worked example: https://en.wikipedia.org/wiki/Fast_inverse_square_root#Overview_of_the_code

[DelSquared]

Posting the original code here would be helpful

I edited my post with the code provided on Wikipedia as well as the link that I sourced it from. Thanks for your suggestion @nhuyvan1106 :)

[ShivanshuKantPrasad]

So if i understand this correctly then floating point numbers are stored in scientific notation, in the form of significand and exponent. In the above algorithm we are dividing the exponent part of the floating number in half leading to square root of the number. So basically we have shifted the hard part of the calculation on the implementation of floating point numbers. Is this right?

[lazycuh]

@DelSquared I often use bit shifting and bitwise-and to manipulate RGB pixels

For example, generating a random pixel

(Javascript)

const r = (Math.random() * 256) & 0xff;
const g = (Math.random() * 256) & 0xff;
const b = (Math.random() * 256) & 0xff;

const pixel = (r << 16) | (g << 8) | b;

console.log(pixel)

The equivalent code in Javascript, one important thing to note here is that because all numbers in Javascript are already represented as double-precision IEEE-754 float point numbers, and there is no specific type for integers, no need to convert back to float.

function Q_rsqrt(num) {
  let i, x2, y;     
  const threehalfs = 1.5; 
  x2 = num * 0.5;   
  y = num;

  i = y | 0; 
  i = 0x5f3759df - ( i >> 1);

  y = i;
  y = y * ( threehalfs - ( x2 * y * y ) );
  y = y * ( threehalfs - ( x2 * y * y ) );  
  return y;
}

Java

float inverseSquare(float num) {
  int i;
  float x2, y;  
  final float threehalfs = 1.5; 
  x2 = num * 0.5;   
  y = num;

  i = (int) y; 
  i = 0x5f3759df - ( i >> 1);

  y = (float) i;
  y = y * ( threehalfs - ( x2 * y * y ) );
  y = y * ( threehalfs - ( x2 * y * y ) );  
  return y;
}

[ShivanshuKantPrasad]

@nhuyvan1106 Your JavaScript code does not seem to work.

[lazycuh]

@ShivanshuKantPrasad 

It is probably because the statement i = * ( long * ) &y; simply is not a mere cast from float to long, the C compiler may do something else which I have no clue about, after reading the wikipedia article, that seems to be the case

[DelSquared]

@DelSquared I often use bit shifting and bitwise-and to manipulate RGB pixels

For example, generating a random pixel

(Javascript)

const r = (Math.random() * 256) & 0xff;
const g = (Math.random() * 256) & 0xff;
const b = (Math.random() * 256) & 0xff;

const pixel = (r << 16) | (g << 8) | b;

console.log(pixel)

The equivalent code in Javascript, one important thing to note here is that because all numbers in Javascript are already represented as double-precision IEEE-754 float point numbers, and there is no specific type for integers, no need to convert back to float.

function Q_rsqrt(num) {
  let i, x2, y;   
  const threehalfs = 1.5; 
  x2 = num * 0.5;     
  y = num;

  i = y | 0; 
  i = 0x5f3759df - ( i >> 1);

  y = i;
  y = y * ( threehalfs - ( x2 * y * y ) );
  y = y * ( threehalfs - ( x2 * y * y ) );    
  return y;
}

Java

float inverseSquare(float num) {
  int i;
  float x2, y;    
  final float threehalfs = 1.5; 
  x2 = num * 0.5;     
  y = num;

  i = (int) y; 
  i = 0x5f3759df - ( i >> 1);

  y = (float) i;
  y = y * ( threehalfs - ( x2 * y * y ) );
  y = y * ( threehalfs - ( x2 * y * y ) );    
  return y;
}

What is the | operator in JS? I have never come across it @nhuyvan1106 .

[lazycuh]

@DelSquared It is called Bitwise-OR