Fast Inverse Square Root in Javascript implementieren?

Die Fast Inverse Square Root von Quake III scheint einen Gleitkomma-Trick zu verwenden. Soweit ich weiß, kann die Gleitkommadarstellung verschiedene Implementierungen haben.

Ist es also möglich, die schnelle inverse Quadratwurzel in Javascript zu implementieren?

Würde es das gleiche Ergebnis zurückgeben?

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;

}

Der Trick hängt davon ab, dass die Bits einer Gleitkommazahl als Ganzzahl und wieder zurück interpretiert werden. Dies ist in JavaScript mithilfe der Funktion Typed Arrays möglich , um einen Rohbytepuffer mit mehreren numerischen Ansichten darauf zu erstellen.

Hier ist eine wörtliche Konvertierung des von Ihnen angegebenen Codes. Beachten Sie, dass dies nicht genau dasselbe ist, da alle arithmetischen Operationen in JavaScript 64-Bit-Gleitkommazahlen und keine 32-Bit-Operationen sind, sodass die Eingabe unbedingt konvertiert werden muss. Ebenso wie der ursprüngliche Code ist dies plattformabhängig , da es unsinnige Ergebnisse liefert, wenn die Prozessorarchitektur eine andere Bytereihenfolge verwendet. Wenn Sie solche Dinge tun müssen, empfehle ich, dass Ihre Anwendung zuerst einen Testfall ausführt, um festzustellen, ob Ganzzahlen und Gleitkommazahlen die erwarteten Bytedarstellungen haben.

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;
}

Ich habe durch Betrachten eines Diagramms bestätigt, dass dies vernünftige numerische Ergebnisse liefert. Es ist jedoch nicht offensichtlich, dass dies die Leistung überhaupt verbessern wird, da wir mehr JavaScript-Operationen auf höherer Ebene ausführen. Ich habe Benchmarks für die Browser ausgeführt, die ich zur Hand habe, und festgestellt, dass dies Q_rsqrt(number)50% bis 80% der Zeit in 1/sqrt(number)Anspruch nimmt (Chrome, Firefox und Safari unter macOS, Stand April 2018). Hier ist mein kompletter Testaufbau:

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>