11
\$\begingroup\$

The Fast Inverse Square Root from Quake III seems to use a floating-point trick. As I understand, floating-point representation can have some different implementations.

So is it possible to implement the Fast Inverse Square Root in Javascript?

Would it return the same result?

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;

}
\$\endgroup\$
5
  • \$\begingroup\$ Let me know if this question would be better asked on StackOverflow. It seemed more appropriate here since it has game dev roots and mostly game dev applications. \$\endgroup\$
    – Atav32
    Jun 17, 2012 at 4:32
  • 4
    \$\begingroup\$ Javascript has pointers? \$\endgroup\$
    – Pubby
    Jun 17, 2012 at 6:36
  • 2
    \$\begingroup\$ While its tempting to use a "special" function that speeds up your entire program, chances are that you introduce bugs or simply don't speed things up at all (see Kevin Reid's answer below for instance). c2.com/cgi/wiki?PrematureOptimization \$\endgroup\$ Jun 17, 2012 at 14:39
  • \$\begingroup\$ I'm sorry, but using low-level FP optimisations with Javascript looks like ordering 4 fat burgers with fries and a diet cola to stay thin. Don't do that, it's pointless and ridiculous. \$\endgroup\$
    – Nevermind
    Jun 9, 2016 at 7:14
  • \$\begingroup\$ The fast inverse sqrt is a very common operation in games programming, and all the game consoles implement this in hardware. ES6 should definitely consider adding Math.fastinvsqrt(x) to the language. \$\endgroup\$ Jul 18, 2016 at 2:50

1 Answer 1

16
\$\begingroup\$

The trick depends on reinterpreting the bits of a floating-point number as an integer and back again, which is possible in JavaScript by using the Typed Arrays facility, to create a raw byte buffer with multiple numeric views onto it.

Here is a literal conversion of the code you gave; note that it is not exactly the same, as all arithmetic operations in JavaScript are 64-bit floating point, not 32-bit, so the input will necessarily be converted. Also, like the original code, this is platform-dependent in that it will give nonsense results if the processor architecture uses a different byte order; if you must do things like this, I recommend that your application first execute a test case to determine that integers and floats have the byte representations you expect.

const bytes = new ArrayBuffer(Float32Array.BYTES_PER_ELEMENT);
const floatView = new Float32Array(bytes);
const intView = new Uint32Array(bytes);
const threehalfs = 1.5;

function Q_rsqrt(number) {
  const x2 = number * 0.5;
  floatView[0] = number;
  intView[0] = 0x5f3759df - ( intView[0] >> 1 );
  let y = floatView[0];
  y = y * ( threehalfs - ( x2 * y * y ) );

  return y;
}

I've confirmed by eyeballing a graph that this gives reasonable numeric results. However, it is not obvious that this will improve performance at all, since we are doing more high-level JavaScript operations. I have run benchmarks on the browsers I have handy and found that Q_rsqrt(number) takes 50% to 80% of the time taken by 1/sqrt(number) (Chrome, Firefox, and Safari on macOS, as of April 2018). Here is my complete test setup:

const {sqrt, min, max} = Math;

const bytes = new ArrayBuffer(Float32Array.BYTES_PER_ELEMENT);
const floatView = new Float32Array(bytes);
const intView = new Uint32Array(bytes);
const threehalfs = 1.5;

function Q_rsqrt(number) {
  const x2 = number * 0.5;
  floatView[0] = number;
  intView[0] = 0x5f3759df - ( intView[0] >> 1 );
  let y = floatView[0];
  y = y * ( threehalfs - ( x2 * y * y ) );

  return y;
}

// benchmark
const junk = new Float32Array(1);
function time(f) {
  const t0 = Date.now();
  f();
  const t1 = Date.now();
  return t1 - t0;
}
const timenat = time(() => { 
  for (let i = 0; i < 5000000; i++) junk[0] = 1/sqrt(i)
});
const timeq = time(() => {
  for (let i = 0; i < 5000000; i++) junk[0] = Q_rsqrt(i);
});
document.getElementById("info").textContent =
  "Native square root: " + timenat + " ms\n" +
  "Q_rsqrt: " + timeq + " ms\n" +
  "Ratio Q/N: " + timeq/timenat;

// plot results
const canvas = document.getElementById("canvas");
const ctx = canvas.getContext("2d");
function plot(f) {
  ctx.beginPath();
  const mid = canvas.height / 2;
  for (let i = 0; i < canvas.width; i++) {
    const x_f = i / canvas.width * 10;
    const y_f = f(x_f);
    const y_px = min(canvas.height - 1, max(0, mid - y_f * mid / 5));
    ctx[i == 0 ? "moveTo" : "lineTo"](i, y_px);
  }
  ctx.stroke();
  ctx.closePath();
}
ctx.strokeStyle = "black";
plot(x => 1/sqrt(x));
ctx.strokeStyle = "yellow";
plot(x => Q_rsqrt(x));
<pre id="info"></pre>
<canvas width="300" height="300" id="canvas"
        style="border: 1px solid black;"></canvas>

\$\endgroup\$
2
  • \$\begingroup\$ In classic JavaScript, it is not possible to... reinterpreting the bits of a floating-point number as an integer really? It was years ago so I don't recall exactly what operations I was using, but I once wrote a data parser in JavaScript that would convert a string of bytes into a series of N-bit (N was defined in the header) integers. That's pretty similar. \$\endgroup\$
    – jhocking
    Sep 17, 2014 at 15:34
  • \$\begingroup\$ @jhocking It's possible with a lot of mess. You will need to take a log 2 of the value to figure out the exponent, do a division and a subtraction by 1 for the mantissa, and some bit shifting according to IEEE-754 to finally pack it. \$\endgroup\$ Jun 12, 2020 at 18:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .