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\$
  • \$\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 '12 at 4:32
  • 4
    \$\begingroup\$ Javascript has pointers? \$\endgroup\$ – Pubby Jun 17 '12 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\$ – Daniel Carlsson Jun 17 '12 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 '16 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\$ – John Henckel Jul 18 '16 at 2:50
15
\$\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\$
  • \$\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 '14 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.