Implementar raiz quadrada inversa rápida em Javascript?

11

A Raiz Quadrada Inversa Rápida do Quake III parece usar um truque de ponto flutuante. Pelo que entendi, a representação de ponto flutuante pode ter algumas implementações diferentes.

Então, é possível implementar a Raiz quadrada inversa rápida em Javascript?

Isso retornaria o mesmo 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
fonte
Deixe-me saber se esta pergunta seria melhor feita no StackOverflow. Parecia mais apropriado aqui, pois possui raízes para desenvolvedores de jogos e principalmente aplicativos para desenvolvedores de jogos.
Atav32
4
Javascript tem ponteiros?
Pubby
2
Embora seja tentador usar uma função "especial" que acelera todo o programa, é provável que você introduza bugs ou simplesmente não acelere as coisas (veja a resposta de Kevin Reid abaixo, por exemplo). c2.com/cgi/wiki?PrematureOptimization
Daniel Carlsson
Sinto muito, mas usar otimizações de FP de baixo nível com Javascript parece pedir 4 hambúrgueres gordos com batatas fritas e uma cola diet para ficar magro. Não faça isso, é inútil e ridículo.
Nevermind
O sqrt inverso rápido é uma operação muito comum na programação de jogos, e todos os consoles de jogos implementam isso no hardware. O ES6 definitivamente deve considerar adicionar Math.fastinvsqrt (x) ao idioma.
John Henckel

Respostas:

15

O truque depende da reinterpretação dos bits de um número de ponto flutuante como um número inteiro e vice-versa, o que é possível no JavaScript usando o recurso Arrays digitados , para criar um buffer de bytes brutos com várias visualizações numéricas nele.

Aqui está uma conversão literal do código que você forneceu; observe que não é exatamente o mesmo, pois todas as operações aritméticas em JavaScript são ponto flutuante de 64 bits, não 32 bits; portanto, a entrada será necessariamente convertida. Além disso, como o código original, isso depende da plataforma, pois fornecerá resultados sem sentido se a arquitetura do processador usar uma ordem de bytes diferente; se você precisar fazer coisas assim, recomendo que seu aplicativo execute primeiro um caso de teste para determinar se números inteiros e flutuantes têm as representações de bytes que você 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;
}

Confirmei ao observar um gráfico que isso fornece resultados numéricos razoáveis. No entanto, não é óbvio que isso melhore o desempenho, pois estamos realizando mais operações JavaScript de alto nível. Eu executei benchmarks nos navegadores úteis e descobri que Q_rsqrt(number)leva de 50% a 80% do tempo gasto 1/sqrt(number)(Chrome, Firefox e Safari no macOS, em abril de 2018). Aqui está minha configuração completa de teste:

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
fonte
In classic JavaScript, it is not possible to... reinterpreting the bits of a floating-point number as an integerrealmente? Isso foi há anos, então eu não lembro exatamente quais operações eu estava usando, mas uma vez escrevi um analisador de dados em JavaScript que converteria uma sequência de bytes em uma série de números inteiros de N bits (N foi definido no cabeçalho). Isso é bem parecido.
Jhocking