Negli anni ’90 del secolo scorso i personal computer cominciavano a essere una presenza usuale, e spuntavano i primi giochi grafici: il guaio è che per avere della bella grafica occorre fare tanti conti e la potenza di quei computer non era certo quella attuale, soprattutto se si dovevano usare le operazioni in virgola mobile e non quelle con gli interi. Occorreva dunque inventarsi i più strani metodi per eseguire le operazioni più complicate: ma l’algoritmo per la radice quadrata inversa veloce ha battuto ogni record.

Per prima cosa, che significa “Radice quadrata inversa”? È l’operazione che da x ottiene x^−½, cioè l’inverso della radice quadrata di x. Naturalmente “veloce” significa che l’algoritmo usato è più veloce di quello standard, probabilmente legato all’iterazione con il metodo di Newton a partire da una approssimazione. La prima implementazione per la radice quadrata inversa veloce prevedeva una tabella precompilata di dati da cui partire e migliorare il risultato approssimato; ma anche lo spazio a disposizione non era poi troppo. L’algoritmo che secondo Wikipedia fu ideato alla Silicon Graphics non aveva invece bisogno di una tabella, ma solo di una costante magica: 0x5f3759df. Come funzionava questo algoritmo? Si prendeva il numero x (float a 32 bit), e si salvava la sua metà x2 = x/2 per dopo. Poi si prendeva x, lo si leggeva come se la successione di bit rappresentasse un intero, si faceva uno shift logico a sinistra di una posizione (il primo bit veniva buttato via, gli altri scalavano di una posizione a sinistra, e si metteva uno zero in fondo), si sottraeva questo numero dalla costante magica e si leggeva il risultato y come fosse un float. Seguiva un’iterazione dove y veniva ricalcolato come 1,5 − (x2 × y²). Tutto qua.

Ma come è stata trovata questa costante? Non ho avuto voglia di leggermi tutta questa tesina, lo ammetto :-) Tanto ormai le CPU calcolano in virgola mobile a una velocità incredibile…