# 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

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>
``````
-
`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