Menerapkan Fast Inverse Square Root di Javascript?

Fast Inverse Square Root dari Quake III tampaknya menggunakan trik floating-point. Seperti yang saya pahami, representasi floating-point dapat memiliki beberapa implementasi yang berbeda.

Jadi mungkinkah menerapkan Fast Inverse Square Root di Javascript?

Apakah akan mengembalikan hasil yang sama?

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;

}

Triknya tergantung pada penafsiran kembali bit dari angka floating-point sebagai integer dan kembali lagi, yang dimungkinkan dalam JavaScript dengan menggunakan fasilitas Typed Array , untuk membuat buffer byte mentah dengan beberapa tampilan numerik.

Berikut ini adalah konversi kode yang Anda berikan secara literal; perhatikan bahwa ini tidak persis sama, karena semua operasi aritmatika dalam JavaScript adalah titik apung 64-bit, bukan 32-bit, sehingga input akan selalu dikonversi. Juga, seperti kode asli, ini bergantung pada platform karena akan memberikan hasil yang tidak masuk akal jika arsitektur prosesor menggunakan urutan byte yang berbeda; jika Anda harus melakukan hal-hal seperti ini, saya sarankan agar aplikasi Anda terlebih dahulu menjalankan test case untuk menentukan bahwa integer dan float memiliki representasi byte yang Anda harapkan.

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

Saya telah mengkonfirmasi dengan melihat grafik bahwa ini memberikan hasil numerik yang masuk akal. Namun, tidak jelas bahwa ini akan meningkatkan kinerja sama sekali, karena kami melakukan lebih banyak operasi JavaScript tingkat tinggi. Saya telah menjalankan benchmark pada browser yang saya miliki dan menemukan bahwa Q_rsqrt(number)dibutuhkan 50% hingga 80% dari waktu yang diambil 1/sqrt(number)(Chrome, Firefox, dan Safari di macOS, per April 2018). Ini adalah pengaturan pengujian lengkap saya:

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>