# 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 '16 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 '16 at 2:50

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 = number;
intView = 0x5f3759df - ( intView >> 1 );
let y = floatView;
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 = number;
intView = 0x5f3759df - ( intView >> 1 );
let y = floatView;
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 = 1/sqrt(i)
});
const timeq = time(() => {
for (let i = 0; i < 5000000; i++) junk = 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>

• 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