Implementar Fast Inverse Square Root en Javascript?

11

La raíz cuadrada inversa rápida de Quake III parece usar un truco de punto flotante. Según tengo entendido, la representación de punto flotante puede tener algunas implementaciones diferentes.

Entonces, ¿es posible implementar la raíz cuadrada inversa rápida en Javascript?

¿Devolvería el mismo resultado?

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;

}
Atav32
fuente
Avíseme si esta pregunta se haría mejor en StackOverflow. Parecía más apropiado aquí ya que tiene raíces de desarrollo de juegos y principalmente aplicaciones de desarrollo de juegos.
Atav32
44
Javascript tiene punteros?
Pubby
2
Si bien es tentador usar una función "especial" que acelere todo su programa, es probable que introduzca errores o simplemente no acelere las cosas (consulte la respuesta de Kevin Reid a continuación, por ejemplo). c2.com/cgi/wiki?PrematureOptimization
Daniel Carlsson
Lo siento, pero usar optimizaciones de FP de bajo nivel con Javascript parece pedir 4 hamburguesas gordas con papas fritas y una cola dietética para mantenerse delgado. No hagas eso, no tiene sentido y es ridículo.
importa
El sqrt inverso rápido es una operación muy común en la programación de juegos, y todas las consolas de juegos implementan esto en hardware. ES6 definitivamente debería considerar agregar Math.fastinvsqrt (x) al lenguaje.
John Henckel

Respuestas:

15

El truco depende de reinterpretar los bits de un número de coma flotante como un número entero y viceversa, lo cual es posible en JavaScript mediante el uso de Typed Arrays , para crear un búfer de bytes sin formato con múltiples vistas numéricas.

Aquí hay una conversión literal del código que le diste; tenga en cuenta que no es exactamente lo mismo, ya que todas las operaciones aritméticas en JavaScript son de coma flotante de 64 bits, no de 32 bits, por lo que la entrada necesariamente se convertirá. Además, al igual que el código original, esto depende de la plataforma, ya que dará resultados sin sentido si la arquitectura del procesador usa un orden de bytes diferente; si debe hacer cosas como esta, le recomiendo que su aplicación primero ejecute un caso de prueba para determinar que los enteros y flotantes tengan las representaciones de bytes que espera.

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

He confirmado mirando un gráfico que esto da resultados numéricos razonables. Sin embargo, no es obvio que esto mejorará el rendimiento, ya que estamos haciendo más operaciones de JavaScript de alto nivel. He ejecutado puntos de referencia en los navegadores que tengo a mano y descubrí que Q_rsqrt(number)lleva del 50% al 80% del tiempo que toma 1/sqrt(number)(Chrome, Firefox y Safari en macOS, a partir de abril de 2018). Aquí está mi configuración de prueba completa:

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>

Kevin Reid
fuente
In classic JavaScript, it is not possible to... reinterpreting the bits of a floating-point number as an integer¿De Verdad? Fue hace años, así que no recuerdo exactamente qué operaciones estaba usando, pero una vez escribí un analizador de datos en JavaScript que convertiría una cadena de bytes en una serie de enteros de N bits (se definió N en el encabezado). Eso es muy similar.
jhocking