Understanding Quake’s Fast Inverse Square Root
Un articolo e un documento di ricerca descrivono un modo veloce e apparentemente magico per calcolare la radice quadrata inversa ($1/\sqrt{x}$), usata nel gioco Quake.
Non sono un esperto di grafica, ma apprezzo perché le radici quadrate sono utili. Il teorema di Pitagora calcola la distanza tra i punti e dividere per distanza aiuta a normalizzare i vettori. (La normalizzazione è spesso solo un termine di fantasia per divisione.)
Giochi 3D come Quake dividono per distanza zillions (sì zillions) di volte al secondo, quindi i miglioramenti delle prestazioni “minori” aiutano immensamente. Non vogliamo prendere la radice quadrata e dividere il modo regolare: l’esponenziazione e la divisione sono davvero, davvero costose per la CPU.
Date queste condizioni, ecco la formula magica per ottenere $1/\sqrt{x}$, come si trova in Quake (i miei commenti inseriti):
La mia comprensione: Questo incredibile hack stima la radice inversa usando il metodo di approssimazione di Newton, e inizia con una grande ipotesi iniziale.
Per fare l’ipotesi, prende il numero in virgola mobile in notazione scientifica e nega & dimezza l’esponente per ottenere qualcosa di vicino alla radice quadrata inversa. Quindi esegue un giro del metodo di approssimazione di Newton per perfezionare ulteriormente la stima e tada, abbiamo qualcosa vicino alla radice quadrata inversa.
Metodo di approssimazione di Newton
Il metodo di Newton può essere usato per trovare radici approssimative di qualsiasi funzione. Puoi continuare a iterare il metodo per avvicinarti sempre di più alla radice, ma questa funzione utilizza solo 1 passo! Ecco un corso accelerato sul metodo di Newton (era nuovo per me):
Puoi continuare a ripetere questo processo (inserendo la tua nuova ipotesi nella formula) e ottenere approssimazioni più vicine per la tua radice. Alla fine hai una “nuova ipotesi” che rende f (nuova ipotesi) davvero, molto vicino allo zero — è una radice! (O abbastanza vicino per il lavoro del governo, come si suol dire).
Chiaramente, vogliamo rendere il nostro errore il più piccolo possibile. Ciò significa trovare la ” x ” che fa error(x) = 0, che è la stessa cosa che trovare la radice dell’equazione di errore. Se colleghiamo errore(x) in Newton formula di avvicinamento:
e prendere gli opportuni strumenti derivati:
siamo in grado di collegare in per ottenere la formula per una migliore indovinare:
Che è esattamente l’equazione si vede nel codice sopra, ricordando che x è il nuovo credo (g) e “xhalf” è la metà del valore originale ($0.5 mi$):
x = x*(1.5f - xhalf*x*x);
Con questa formula, si può iniziare con un indovinare “g” e ripetere la formula per ottenere la migliore ipotesi. Prova questa demo per l’utilizzo di più iterazioni per trovare il quadrato inverso:
Così i miei amici, la domanda diventa: “Come possiamo fare una buona ipotesi iniziale?”
Fare una buona ipotesi
Che cosa è una buona ipotesi per la radice quadrata inversa? È un po ‘ una domanda trabocchetto our la nostra ipotesi migliore per la radice quadrata inversa è la radice quadrata inversa stessa!
Ok hotshot, chiedi, come otteniamo effettivamente $1 / \ sqrt{x}$?
È qui che entra in gioco la magia. Diciamo che hai un numero in forma di esponente o notazione scientifica:
Ora, se si desidera trovare il regolare radice quadrata, devi solo dividere l’esponente da 2:
E se si desidera che l’inverso della radice quadrata, dividere l’esponente da -2 a capovolgere il segno:
Così, come possiamo ottenere l’esponente di un numero senza altre operazioni dispendiose?
I float sono memorizzati nella forma mantissa-esponente
Beh, siamo fortunati. I numeri in virgola mobile sono memorizzati dai computer in forma mantissa-esponente, quindi è possibile estrarre e dividere l’esponente!
Ma invece di fare esplicitamente la divisione (costosa per la CPU), il codice utilizza un altro trucco intelligente: sposta i bit. Lo spostamento a destra di una posizione equivale a dividere per due (puoi provarlo per qualsiasi potenza di 2, ma troncerà il resto). E se vuoi ottenere un numero negativo, invece di moltiplicare per -1 (le moltiplicazioni sono costose), basta sottrarre il numero da “0” (le sottrazioni sono economiche).
Quindi, il codice converte il numero in virgola mobile in un numero intero. Quindi sposta i bit di uno, il che significa che i bit degli esponenti sono divisi per 2 (quando alla fine trasformiamo i bit in un float). E infine, per negare l’esponente, sottraiamo dal numero magico 0x5f3759df. Questo fa alcune cose: conserva la mantissa (la parte non esponente, alias 5 in: 5 5 \cdot 10^6$), gestisce gli esponenti pari-dispari, spostando i bit dall’esponente alla mantissa e tutti i tipi di cose funky. Il giornale ha più dettagli e spiegazioni, non l’ho preso tutto la prima volta. Come sempre, sentiti libero di commentare se hai una spiegazione migliore di ciò che sta accadendo.
Il risultato è che otteniamo un’ipotesi iniziale molto vicina alla radice quadrata inversa reale! Possiamo quindi fare un singolo giro del metodo di Newton per affinare l’ipotesi. Sono possibili più round (con una spesa computazionale aggiuntiva), ma un round è tutto ciò che serve per la precisione necessaria.
Quindi, perché il numero magico?
Il grande trucco è come interi e numeri in virgola mobile sono memorizzati. Numeri in virgola mobile come 5 5.4 \ cdot 10^6 store memorizza il loro esponente in un intervallo separato di bit rispetto a “5.4”. Quando si sposta l’intero numero, si divide l’esponente per 2, oltre a dividere anche il numero (5.4) per 2. Questo è dove il numero magico entra in gioco does fa alcune correzioni interessanti per questa divisione,che non capisco. Tuttavia, ci sono diversi numeri magici che potrebbero essere usati – questo succede per minimizzare l’errore nella mantissa.
Il numero magico corregge anche gli esponenti pari / dispari; il documento menziona che puoi anche trovare altri numeri magici da usare.
Risorse
C’è un’ulteriore discussione su reddit (utente pb_zeppelin) e slashdot:
- http://games.slashdot.org/article.pl?sid=06/12/01/184205 e il mio commento
Altri Post In Questa Serie
- Numero di Sistemi e Basi
- Guida Rapida per Guid
- Comprensione del Terremoto Veloce Inverso del Quadrato della Radice
- Una Semplice Introduzione Alle reti di Computer
- scambio di due variabili tramite XOR
- Comprensione Big e Little Endian Byte Order
- Unicode e
- Un po ‘ di diddy su binari formati di file
- Algoritmi di Ordinamento