Revisitando la raíz cuadrada invertida

Hace algunos años se puso de moda hablar en blogs del algoritmo que se incluyó en el Quake III Arena para calcular una aproximación rápida de la raíz cuadrada invertida. Esta operación matemática es útil para calcular los ángulos de incidencia y reflexión de los efectos de iluminación y profundidad.

De hecho se ha hablado ya mucho sobre el tema así que para ahorraros tiempo quiero comentar que hay una instrucción máquina en el conjunto SSE (Streaming SIMD Extensions) que la calcula mucho más deprisa que si escribimos nosotros el código. Dicha instrucción es la rsqrt de hecho si no buscamos una raíz cuadrada exacta calcular rsqrt(x) * x puede llegar a ser más rápido que la instrucción sqrt, aunque esta última tiene más precisión. De todas formas no está de más probar las cosas siempre para estar totalmente seguros.

Si queréis profundizar en el tema. el algoritmo se discute en este artículo de investigación escrito en el año 2003.

float fastInvSqrt(float x) {
    float xhalf = 0.5 * x;
    int i = *(int *)&x; // Castea a entero el número en coma flotante
    i = 0x5f3759df - (i >> 1); // Número mágico
    x = *(float*)&i; // Vuelve a castear a float
    x = x*(1.5-(xhalf*x*x)); // Aplica una iteración del método de Newton
    return x;
}

El número mágico permite aproximar la raíz cuadrada inversa usando aritmética entera, para obtenerlo se usan propiedades de logaritmos y cambios de representación entre enteros y coma flotante. Después se aplica una iteración del método de Newton.

Podéis encontrar una descripción completa en este enlace de wikipedia.

Artículos relacionados:

Contando bits