# Implement Fast Inverse Square Root in Javascript?

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;

}
``````
-
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. – Atav32 Jun 17 '12 at 4:32
Javascript has pointers? – Pubby Jun 17 '12 at 6:36
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
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. – Nevermind Jun 9 at 7:14
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. – John Henckel Jul 18 at 2:50

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 relatively new, but now standard, Typed Arrays facility, 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:

``````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); });``````
``````<pre id="x"></pre>
<canvas width="300" height="300" id="canvas"></canvas>``````

-
`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. – jhocking Sep 17 '14 at 15:34