Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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;

}
share|improve this question
    
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. –  BBz Jun 17 '12 at 4:32
2  
Javascript has pointers? –  Pubby Jun 17 '12 at 6:36
1  
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 –  Daniel Carlsson Jun 17 '12 at 14:39
add comment

1 Answer 1

up vote 12 down vote accepted

In classic JavaScript, it is not possible to implement the trick, because it depends on reinterpreting the bits of a floating-point number as an integer and back again, whereas JavaScript does not include any operations to do that.

However, with the new Typed Arrays facility (info; spec), which is likely to make it into the next JavaScript standard, it is possible to create a raw data buffer and have 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.

Also note that, like the original code, this is platform-dependent in that it may 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.

var buf = new ArrayBuffer(Float32Array.BYTES_PER_ELEMENT);
var fv = new Float32Array(buf);
var lv = new Uint32Array(buf);
var threehalfs = 1.5;

function Q_rsqrt(number) {
  var x2 = number * 0.5;
  fv[0] = number;
  lv[0] = 0x5f3759df - ( lv[0] >> 1 );
  var y = fv[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 questionable whether this will improve performance at all, since we are doing many more high-level JavaScript operations. I have run benchmarks on the browsers I have handy and found that it is either nearly the same speed as 1/sqrt(number) (Chrome 21.0.1171.0 dev, Firefox 13.0) or ten times slower (Safari 5.1.7). Here is my complete test setup:

<!doctype html>
<title>“Fast” Inverse Square Root Test</title>
<pre id="x"></pre>
<canvas width="300" height="300" id="canvas"></canvas>
<script type="text/javascript">
    var sqrt = Math.sqrt;

    var buf = new ArrayBuffer(Float32Array.BYTES_PER_ELEMENT);
    var fv = new Float32Array(buf);
    var lv = new Uint32Array(buf);
    var threehalfs = 1.5;

    function Q_rsqrt(number) {
      var x2 = number * 0.5;
      fv[0] = number;
      lv[0] = 0x5f3759df - ( lv[0] >> 1 );
      var y = fv[0];
      y = y * ( threehalfs - ( x2 * y * y ) );

      return y;
    }

    // benchmark
    var junk = new Float32Array(1);
    var t0 = Date.now();
    for (var i = 0; i < 5000000; i++) junk[0] = 1/sqrt(i);
    var t1 = Date.now();
    var timenat = t1 - t0;
    var t0 = Date.now();
    for (var i = 0; i < 5000000; i++) junk[0] = Q_rsqrt(i);
    var t1 = Date.now();
    var timeq = t1 - t0;
    document.getElementById("x").textContent = "Native square root: " + timenat + " ms\nQ_rsqrt: " + timeq + " ms\nRatio Q/N: " + timeq/timenat;

    // plot results
    var canvas = document.getElementById("canvas");
    var ctx = canvas.getContext("2d");
    function plot(f) {
      ctx.beginPath();
      var mid = canvas.height / 2;
      for (var i = 0; i < canvas.width; i++) {
        ctx[i == 0 ? "moveTo" : "lineTo"](i, mid - f(i / canvas.width * 10) * mid / 5);
      }
      ctx.stroke();
      ctx.closePath();
    }
    ctx.strokeStyle = "black";
    plot(function (x) { return 1/sqrt(x); });
    ctx.strokeStyle = "yellow";
    plot(function (x) { return Q_rsqrt(x); });
</script>
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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