Fast inverse square root è un algoritmo che stima
, il reciproco (o inverso moltiplicativo) della radice quadrata di un numero in virgola mobile a 32 bit x in formato IEEE 754 in virgola mobile. Il calcolo delle radici quadrate reciproche è necessario in molte applicazioni, come la normalizzazione vettoriale nei videogiochi ed è principalmente utilizzato nei calcoli coinvolti nella programmazione 3D. Nella grafica 3D, normali di superficie, vengono utilizzati vettori a 3 coordinate di lunghezza 1, per esprimere illuminazione e riflessione. C’erano un sacco di normali di superficie. E calcolarli comporta la normalizzazione di molti vettori. La normalizzazione è spesso solo un termine di fantasia per la divisione. Il teorema di Pitagora calcola la distanza tra i punti e dividere per distanza aiuta a normalizzare i vettori: 
Questo algoritmo è meglio conosciuto per la sua implementazione nel 1999 nel codice sorgente di Quake III Arena Game, un videogioco sparatutto in prima persona che ha fatto un uso pesante della grafica 3D. A quel tempo, era generalmente computazionalmente costoso calcolare il reciproco di un numero in virgola mobile, specialmente su larga scala; la radice quadrata inversa veloce ha bypassato questo passaggio.
Algoritmo:
Passo 1: Reinterpreta i bit dell’input in virgola mobile come un numero intero.
i = * ( long * ) &y;
Passaggio 2 : prende il valore risultante e fa aritmetica intera su di esso che produce un’approssimazione del valore che stiamo cercando.
i = 0x5f3759df - ( i >> 1 );
Passaggio 3 : Il risultato non è l’approssimazione stessa, è un numero intero che sembra essere, se reinterpretate i bit come un numero in virgola mobile, l’approssimazione. Quindi il codice fa il contrario della conversione nel passaggio 1 per tornare in virgola mobile:
y = * ( float * ) &i;
Passo 4: E infine esegue una singola iterazione del metodo di Newton per migliorare l’approssimazione.
y = y * ( threehalfs - ( x2 * y * y ) ); //threehalfs = 1.5F;
L’algoritmo accetta un numero in virgola mobile a 32 bit come input e memorizza un valore dimezzato per un uso successivo. Quindi, trattando i bit che rappresentano il numero in virgola mobile come un intero a 32 bit, viene eseguito uno spostamento logico di un bit e il risultato viene sottratto dal numero magico 0x5F3759DF. Questa è la prima approssimazione della radice quadrata inversa dell’input. Trattando nuovamente i bit come un numero in virgola mobile, esegue un’iterazione del metodo di approssimazione di Newton, ottenendo un’approssimazione più precisa.
diciamo che c’è un numero in esponente forma o in notazione scientifica:
=100 milioni di
Ora, per trovare il regolare radice quadrata, avevamo appena dividere l’esponente da 2:
E se, volete sapere l’inverso della radice quadrata, dividere l’esponente da -2 a capovolgere il segno:
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, aka 5 in: 5 · 
), gestisce gli esponenti pari-dispari, spostando i bit dall’esponente alla mantissa e ogni sorta di roba funky.
Il seguente codice è l’implementazione della radice quadrata inversa veloce da Quake III Arena (esatto commento originale scritto nel gioco Quake III Arena).
#include<bits/stdc++.h> using namespace std; float inverse_rsqrt( float number ) { const float threehalfs = 1.5F; float x2 = number * 0.5F; float y = number; long i = * ( long * ) &y; i = 0x5f3759df - ( i >> 1 ); y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); return y; } int main(){ int n = 256; float f = inverse_rsqrt(n); cout << f << endl; return 0; } Uscita :
