Tudo sobre o algoritmo de inversa da raiz quadrada rápida

Tudo sobre a inversa da raiz quadrada rápida

Algoritmo

• O algoritmo de inversa da raiz quadrada rápida ficou famoso no código-fonte de Quake 3 e foi usado por John Carmack.
• Esse algoritmo manipula os bits de ponto flutuante para calcular rapidamente a inversa da raiz quadrada.
• Exemplo de código:

  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 ) );  // 1차 반복
  
    return y;
  }
  

Ponto flutuante de 32 bits: representação

• O ponto flutuante IEEE-754 de 32 bits é composto por 3 elementos:
  • Sinal: 1 bit, indica se o número é positivo ou negativo.
  • Expoente: 8 bits, determina o intervalo do número.
  • Mantissa: 23 bits, especifica a posição do número dentro desse intervalo.
• O valor real é calculado da seguinte forma:

  N = -1^S * 2^(E-127) * (1 + M/2^23)
  

Ponto flutuante de 32 bits: interpretação dos bits

• A representação interna de ponto flutuante normalmente não é importante para programadores.
• No entanto, entender bem essa representação permite projetar algoritmos eficientes.
• Se o padrão de bits de um ponto flutuante for interpretado como inteiro, ele se torna uma aproximação da função logarítmica.

  log2(x) ≈ Ix / L - B
  

Método de Newton

• Para melhorar a aproximação inicial, usa-se o método de Newton.
• O método de Newton é um algoritmo que melhora iterativamente a aproximação de uma função dada.
• Exemplo de código:

  y = y * ( threehalfs - ( x2 * y * y ) ); // 1차 반복
  

Conclusão

• Esse algoritmo foi projetado com base em uma compreensão profunda dos detalhes matemáticos internos do sistema de ponto flutuante e no uso de operações que executam rapidamente no computador.
• A origem do algoritmo não é certa, mas ele é um exemplo de engenharia extremamente eficiente e bem projetada.

Opinião do GN⁺

• Importância histórica: esse algoritmo foi um método inovador criado para superar as limitações de hardware da época.
• Valor educacional: ajuda bastante a entender a estrutura interna do ponto flutuante e seus princípios matemáticos.
• Aplicação moderna: pode ser menos necessário no hardware moderno, mas os princípios do algoritmo continuam úteis.
• Possibilidade de otimização: o valor das constantes do algoritmo pode ser otimizado, o que abre espaço para pesquisas adicionais.
• Visão crítica: no hardware moderno podem existir métodos melhores, então é importante sempre comparar com as tecnologias mais atuais.

[joyfui]

Aquele código curioso que reaparece de tempos em tempos... haha

[GN⁺]

Opiniões no Hacker News

• Suporte a instruções SSE: computadores fabricados depois de 1999 oferecem suporte ao conjunto de instruções SSE, e é possível calcular rapidamente a inversa da raiz quadrada com a instrução _mm_rsqrt_ps.

• Avanços do hardware moderno: no hardware moderno, o cálculo da inversa da raiz quadrada pode ser feito rapidamente pela CPU, e é um equívoco achar que todas as operações de ponto flutuante são descarregadas para a GPU.

• Implementação em MMIX: há um exemplo de código que implementa o cálculo da inversa da raiz quadrada em linguagem MMIX. Esse código assume originalmente que o número é maior que 2^-1021.

• Erro de digitação na fórmula: há um erro de digitação na fórmula de ponto flutuante. O correto é (-1)^S.

• Interpretação dos logs: interpretar o padrão bruto de bits não é uma aproximação linear por partes do logaritmo. As linhas entre os pontos de dados não existem de fato.

• Referência da Wikipédia: há uma boa discussão sobre essa função e sua história na Wikipédia. Link da Wikipédia

• Coletânea de código no GitHub: alguns códigos relacionados foram reunidos no GitHub. Link do GitHub

• Referência no StackOverflow: também vale consultar uma pergunta no StackOverflow sobre aproximações otimizadas de baixa precisão. Link do StackOverflow

• Experiência com otimização de engines 3D: antes de Quake, houve experiência em criar engines 3D e aprender otimização, e a otimização de algoritmos sempre vence.

• Recomendação de vídeo no YouTube: há um vídeo interessante sobre esse tema. Link do YouTube

• Ladrão de tempo produtivo: mergulhar nesse tema roubou muito tempo produtivo.

• Número mágico ideal: o número mágico do famoso trecho de código não é a constante ótima. É possível encontrar uma constante melhor, e dá para achar o número mágico ideal com um notebook Jupyter.