compreender a raiz quadrada inversa rápida de Quake
um artigo e um artigo de pesquisa descrevem uma forma rápida, aparentemente mágica de calcular a raiz quadrada inversa ($1/\sqrt{x}$), usada no jogo Quake.
não sou especialista em gráficos, mas aprecio porque as raízes quadradas são úteis. O teorema de Pitágoras calcula a distância entre pontos, e dividir por distância ajuda a normalizar vetores. (Normalizar é muitas vezes apenas um termo chique para a divisão.)
3D games like Quake divide by distance zillions (yes zillions) of times each second, so “minor” performance improvements help immensely. Nós não queremos pegar a raiz quadrada e dividir a maneira regular: exponenciação e divisão são muito, muito caras para a CPU.
dadas estas condições, aqui está a fórmula mágica para obter $1/\sqrt{x}$, como encontrado no Quake (meus comentários inseridos):
meu entendimento: este incrível hack estima a raiz inversa usando o método de aproximação de Newton, e começa com um grande palpite inicial.
para fazer o palpite, ele leva o número de ponto flutuante na notação científica, e nega & metade do expoente para obter algo próximo da raiz quadrada inversa. Ele então executa uma rodada do método de aproximação de Newton para aperfeiçoar ainda mais a estimativa e tada, temos algo perto da raiz quadrada inversa.O método de Newton pode ser usado para encontrar raízes aproximadas de qualquer função. Você pode continuar iterando o método para ficar cada vez mais perto da raiz, mas esta função só usa um passo! Aqui está um crash-course sobre o método de Newton (era novo para mim):
você pode continuar repetindo este processo (conectando seu novo palpite na fórmula) e obter aproximações mais próximas para a sua raiz. Eventualmente você tem um “novo palpite” que faz f(novo palpite) realmente, muito perto de zero — é uma raiz! (Ou perto o suficiente para o trabalho do governo, como eles dizem).
é evidente que queremos fazer o nosso erro o mais pequeno possível. Isso significa encontrar o ” x ” que faz erro(x) = 0, que é o mesmo que encontrar a raiz da equação de erro. Se nós ficha de erro(x) em Newton aproximação fórmula:
e tomar as devidas derivados:
podemos ligá-los para obter a fórmula para uma melhor palpite:
o Que é exatamente a equação que você pode ver no código acima, lembrando que x é a nossa nova estimativa (g) e “xhalf” é a metade do valor original (r$0.5 i$):
x = x*(1.5f - xhalf*x*x);
Com esta fórmula, pode-se começar com uma estimativa “g” e repita a fórmula para chegar a melhores soluções. Tente esta demonstração para usar várias iterações para encontrar o quadrado inverso:
então, meus amigos, a pergunta se torna: “como podemos fazer um bom palpite inicial?”
Making a Good Guess
What’s a good guess for the inverse square root? É um pouco uma pergunta com rasteira — nosso melhor palpite para a raiz quadrada inversa é a raiz quadrada inversa em si!OK, espertalhão, você pergunta, Como é que conseguimos $1/\sqrt{x}$?
é aqui que a magia começa. Digamos que tem um número em forma exponencial ou notação científica.:
Agora, se você deseja encontrar o regular raiz quadrada, que tinha acabado de dividir o expoente por 2:
E se você quiser que o inverso da raiz quadrada, dividir o expoente por -2 para inverter o sinal:
Assim, como podemos obter o expoente de um número sem outras operações dispendiosas?
os flutuadores são armazenados em forma de expoente mantissa
bem, estamos com sorte. Números de ponto flutuante são armazenados por Computadores em forma mantissa-expoente, então é possível extrair e dividir o expoente!
mas em vez de fazer explicitamente a divisão (cara para a CPU), o código usa outro hack inteligente: ele muda bits. O deslocamento da direita por uma posição é o mesmo que dividir por duas (você pode tentar isso para qualquer poder de 2, mas ele vai truncar o restante). E se você quiser obter um número negativo, em vez de multiplicar por-1 (multiplicações são caras), apenas subtraia o número de “0” (subtrações são baratas).
assim, o código converte o número de vírgula flutuante em um inteiro. Ele então muda os bits por um, o que significa que os bits exponentes são divididos por 2 (quando eventualmente transformamos os bits de volta em um float). E por último, para negar o expoente, subtraímos do número mágico 0x5f3759df. Isto faz algumas coisas: preserva o mantissa (a parte não-expoente, aka 5 in: $5 \cdot 10^6$), lida com expoentes ímpares-mesmo, transferindo bits do expoente para o mantissa, e todos os tipos de coisas funky. O jornal tem mais detalhes e explicações, não apanhei tudo da primeira vez. Como sempre, sinta-se à vontade para comentar se você tiver uma melhor explicação do que está acontecendo.
o resultado é que temos um palpite inicial que é realmente perto da raiz quadrada inversa real! Podemos então fazer uma única rodada do método de Newton para refinar o palpite. Mais rodadas são possíveis (a uma despesa computacional adicional), mas uma rodada é tudo o que é necessário para a precisão necessária.Então, porquê o número mágico?
The great hack is how integers and floating-point numbers are stored. Números de vírgula flutuante como 5 dólares.4 \cdot 10^6$ armazenar o seu expoente em um intervalo separado de bits que “5.4”. Quando você muda o número inteiro, você divide o expoente por 2, bem como dividindo o número (5.4) por 2 também. É aqui que entra o número mágico.ele faz algumas correções legais para esta divisão, que eu não entendo muito bem. No entanto, existem vários números mágicos que podem ser usados — este acontece para minimizar o erro na mantissa.
o número mágico também corrige para expoentes par / ímpares; o artigo menciona que você também pode encontrar outros números mágicos para usar.
Recursos
não Há mais discussão no reddit (usuário pb_zeppelin) e slashdot:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 e o meu comentário
Outros Posts Desta Série
- Número de Sistemas e Bases
- A Guia Rápido para GUIDs
- Compreensão Quake Rápido Inverso da Raiz Quadrada de
- Um Simples Introdução A Redes de computadores
- Trocar duas variáveis usando XOR
- Compreensão Big e Little Endian Ordem de Byte
- Unicode e
- Um pouco de diddy sobre formatos de arquivo binário
- Algoritmos de Ordenação