Vamos a plantear un reto para el que hace falta contar con conocimientos universitarios de matemáticas y programación. El reto está relacionado con el cálculo de la raíz cuadrada inversa de un número.

 

Introducción

Para calcular vectores unitarios o normalizados, es necesario dividir el vector por su módulo. 

$\mathbf{\hat{v}} = \frac{\mathbf{v}}{||\mathbf{v}||}$

La norma euclídea de un vector se calcula como la raíz cuadrada del cuadrado de sus componentes.

$||\mathbf{v}|| = \sqrt{v_x^2 +v_y^2 + v_z^2}$

Dado que en el campo de los gráficos 3D es necesario calcular este tipo de vectores para determinar la iluminación y los reflejos en las distintas superficies mostradas en pantalla, este tipo de operaciones supusieron un gran cuello de botella en los primeros videojuegos en 3D (a medida que ha pasado el tiempo el hardware se ha ido adaptando para poder resolver este tipo de operaciones de la forma más eficiente posible).

 

(1) Quake III

En los primeros años de los videojuegos en 3D, cuando todavía no existían arquitecturas hardware específicamente adaptadas a los videojuegos, para tratar de minimizar el impacto de esta operación sobre la velocidad de ejecución de los videojuegos, a algún empledo de Silicon Graphics se le ocurrió una implementación aproximada de la raíz cuadrada inversa que proporciona resultados muy cercanos a la implementación tradicional y que se ejecuta mucho más rápido. Para más detalles, existe una entrada de Wikipedia (en inglés) que lo explica todo con alto nivel de detalle.

 

(2) Raíz cuadrada + inverso rápidos

Otra alternativa consiste en encadenar dos métodos acelerados para calcular la raíz cuadrada (incluido en el "Intel Software Optimization Cookbook") y el inverso de un número

 

Reto

Si tras leer lo anterior te interesa aportar información sobre el cálculo de la raíz cuadrada inversa, o proponer implementaciones alternativas te animamos a que participes. Hemos desarrollado un pequeño código en el que medimos tanto el tiempo de ejecución como el error medio y la desviación estándar del error de la raíz cuadrada inversa utilizando ambos métodos (asumiendo como groundtruth el resultado de la función estándar sqrt). En el código, hemos llamado Q_rsqrt a la función (1) y Q_rsqrt2 a la función (2). Si proponéis funciones que implementen aproximaciones de la raíz cuadrada inversa, las testearemos e incluiremos los resultados en este artículo. 

 

Resultados provisionales

De momento, de acuerdo a nuestros tests (todos en el mismo PC), la función sqrt tarda de media unos 3.65 ns, mientras que la alternativa rápida (1) tarda 0.76 ns sin iteraciones de refinamiento, 1.9 ns con una iteración y 3.63 ns con dos iteraciones. Además, estas tres implementacion tienen un error relativo medio de 0.01 (1%), 0.00033 (0.033%) y 0.00000128 (0.000128%). Como vemos, incluso la aproximación más rápida produce resultados bastante aproximados.

Por su parte, el método rápido (2) invierte 0.6 ns en el cálculo de cada raíz cuadrada inversa (siendo la alternativa más rápida por el momento) pero su error es 0.021 (2.1 %).


Temas

Síguenos

 
Template Settings
Select color sample for all parameters
Red Green Blue Gray
Background Color
Text Color
Google Font
Body Font-size
Body Font-family
Scroll to top