Too Cool for Internet Explorer

Historia de una función

Hora y Fecha: Diciembre 5, 2006 @ 1:31 am Autor: Moisés Maciá
Categorías:
674 views

Hoy quiero llamar vuestra atención sobre una función incluida dentro del código fuente del afamado juego Quake3 (recordemos que ID publicó todos los fuentes del motor gráfico no hace mucho).

La función en cuestión calcula de una manera extremadamente eficiente la raíz cuadrada inversa de un número:

Raiz cuadrada inversa

Esta es una operación muy común en el tratamiento de gráficos 3D para normalizar vectores, y no solo en el mundo de los juegos, también resulta útil en herramientas de simulación científica.

Actualmente esta operación se puede realizar directamente sobre el hardware de algunas tarjetas gráficas o algunos sets de instrucciones vectoriales empleando el ensamblador de su microprocesador; pero cuando la necesidad aprieta y no hay hardware especializado, el ingenio de algunas personas nos da joyas como esta:

  1.  
  2. float InvSqrt (float x) {
  3.     float xhalf = 0.5f*x;
  4.     int i = *(int*)&x;
  5.     i = 0×5f3759df - (i >> 1);
  6.     x = *(float*)&i;
  7.     x = x*(1.5f - xhalf*x*x);
  8.     return x;
  9. }
  10.  

El código aprovecha muy inteligentemente la implementación interna que los procesadores utilizan para representar números en coma flotante.

Una máquina representa los números de coma flotante utilizando dos partes: mantisa (M) y exponente (E), según el estándar IEEE 754. La formula sería algo así:

Mantisa y exponente

Para calcular la raíz cuadrada inversa, tenemos:

Raiz cuadrada inversa

En la función observamos como se hace un cast del número flotante a un entero. Después se realiza un desplazamiento lógico de una posición hacia la derecha (que es lo mismo que dividir el exponente entre 2) y niega el resultado.

La constante mágica es probablemente lo más pintoresco del código y lo que más tiempo me ha llevado entender. La solución viene de la mano de la Wikipedia (en el artículo referente al estándar IEEE 754). Esta codificación utiliza un exponente desplazado 127 para permitir almacenar un signo. Así que en realidad partimos de la formula:

Raiz cuadrada inversa 2

La raiz cuadrad inversa queda como:

Raiz cuadrada inversa buena

Codificando esto en el estándar IEEE754 tenemos el exponente en el número mágico:

El primer bit es el bit de signo, los siguientes 8 bits representan el exponente (63+127=190)

1*2(63) => 01011111000000000000000000000000 = 0×5f000000

El resto de cifras del número mágico no tengo ni la menor idea de donde salen :) pero imagino que se trata de un factor de corrección ya que este método de cálculo es muy rápido a costa de ser algo impreciso, el error relativo ronda el 4% según mis cálculos.

En Beyond3D dedican un articulo a indagar sobre la autoria de semejante obra de arte.

PD. Post dedicado especialmente a todos aquellos que dicen que lo que se enseña en la carrera no vale para nada y con cariño a aquellos que creen que pintando controles en Visual Basic saben programar :D





« Anterior post: Multiple ‘GROUP BY’ en SQL | Próximo post: Lo que el código no hace en la vida real (y si hace en las películas) »

5 Comentarios para “Historia de una función”

Javuto
5 de Diciembre de 2006 a las 12:23 pm    

Sencillamente… precioso jeje.

Topo
6 de Diciembre de 2006 a las 11:58 pm    

Si esque la gente cree que la informatica en todo el mundo se basa en programar en .net, java o c++, y es para preguntarles si realmente quien creen que hacen los engines 3d, y demas historias de los juegos modernos, quien hace los calculos de los simuladores de fisica, quien hace los juegos de instrucciones de los procesadores, quien crea las redes wirless al adpatar ondas a 0 y 1, en fin, solo debian enseñarnos a programas .net

Cheli
7 de Diciembre de 2006 a las 3:45 pm    

Como de costumbre un fantástico artículo, enhorabuena.

Cheli

penyaskito
7 de Diciembre de 2006 a las 9:43 pm    

Genial :D

Te haré un trackback en breve… :P

Penyaskito
21 de Enero de 2007 a las 12:45 am    

Raíz cuadrada inversa…

float InvSqrt (float x) {

    float xhalf = 0.5f*x;

    int i = *(int*)&x;

    i = 0×5f3759df - (i >> 1);

    x = *(float*)&i;

    x = x*(1.5f - xhalf*x*x);

    r…


Bad Behavior has blocked 427 access attempts in the last 7 days.