web analytics

Metaprogramación de plantillas C++: cálculos de reales usando únicamente enteros

El profesor e investigador de Cambridge (UK) Edward Rosten es muy conocido en el ámbito de la visión por computador por ser el inventor del detector de características FAST.

Pero además es un brillante programador (hacker) de metaprogramación con templates de C++ y tiene otros proyectos software (siempre software libre), como por ejemplo del que quiero hablar hoy por lo peculiar que es.

Normalmente, cuando programamos en C++, MATLAB, Java, Python o lo que sea, estamos obligados a utilizar solamente dos o tres tipos de datos para «números con decimales» (llamados reales), que son:

La limitación viene de que los ordenadores llevan un hardware especial para operar con números de esos tamaños, y en resumen no saben operar con otros tamaños (para los fans de las microarquitecturas: ¡sé que esto no es exacto al 100%, no me fustiguéis!).

Internamente, lo que se hace es usar registros del tamaño y estructuración adecuados:

De forma que un número N en realidad tiene tres partes: un signo S (-1 o +1), una mantisa (M) y un exponente (E), tal que:

N = S · M · 2E

Este formato estandarizado IEEE permite una representación muy compacta de números en rangos tan variados como mil millones o mil millonésimas sin ningún problema. A cambio, operaciones tan sencillas como sumar dos números reales requieren de un algoritmo que compare cual tiene el exponente más grande, normalizarlos, etc. Es por eso que se requiere de un hardware especial para manejar números reales en los ordenadores de hoy día.

Para la inmensa mayoría de operaciones que un mortal puede necesitar programar en su vida, los tres tipos de datos de arriba son más que suficientes. De hecho, el tipo double ya es más que suficiente para cualquier cálculo ingenieril.

Pero…¿y si quiero números mucho más grandes o mucho más pequeños que los que me permiten los tipos estándar? ¿O si quiero llevar las optimizaciones al límite?

Aquí es donde entra la librería fp_template, un conjunto de templates que permiten operar en tiempo de compilación con números flotantes con mantisa y exponentes creadas a mano mediante una estructura tal que:

struct this_is_a_floating_point_number
{
static const unsigned int mant = ???;
static const int expo = ???;
static const bool posi = ???;
};

Edward ya ha predispuesto una serie de plantillas auxiliares para declarar números cómodamente, como la fpd para formar un número a partir de su parte entera y su parte decimal:,decimal>

,decimal>
typedef fpd<3,14159> pi;,decimal>
typedef fpd<4,0> cuatro;

Así mismo, hay otras plantillas que representan operaciones aritméticas comunes, como la multiplicacion o la salida a pantalla:

typedef multiply a_por_b; 
print< ... >();,cuatro>

La idea fundamental de la metaprogramación es que cualquier operación, por compleja que sea, se puede «dejar ya pensada» en tiempo de compilación y generar código ensamblador únicamente para las mínimas operaciones posibles. Puede sonar una idea rara, y lo es. Tanto que la metaprogramación para C++ no fue inventada ni diseñada, sino descubierta por accidente al verificar (durante la estandarización de C++) que el sistema de plantillas era realmente una máquina Turing completa. ¡Cosas que pasan!

Pero en fin, volvamos al ejemplo. Pudiendo escribir:

std::cout << 3.14159 * 4;



¿por qué complicarse tanto la vida? Hay básicamente tres razones:

1. El mecanismo de templates permite trabajar con rangos numéricos astronómicos. El valor absoluto del máximo número representable para arquitectura de 32 bit es (232-1) * 2231-1, y de (264-1) * 2263-1 para las de 64 bit. El número de átomos en el universo representa el 0.0000123% del rango del que dispondríamos para 32 bit…

2. Porque dejas al compilador que se las ingenie y busque, en tiempo de compilación, el algoritmo óptimo para realizar la operación planteada.

3. Porque mola y ¡es frikísimo!

Por si aún no ves claro de qué va todo esto, que sería lógico si nunca has usado metaprogramación, miremos este programa para ver qué hace:

typedef fpd<3,14159> pi;
typedef fpd<4,0> cuatro;
print< multiply >();

Lo primero que hay que tener muy en cuenta es que la metaprogramación está limitada a datos conocidos de antemano a la hora de escribir el programa. Ni el valor «pi» ni el «cuatro» son variables, sino tipos de datos, ¡mucho ojo!.

El programa de arriba multiplicará pi por 4, y no podemos pedir por teclado ningún otro valor y operar con él. Esto es porque, repito, la multiplicación la está haciendo el compilador. Lo que sí se hace en tiempo de ejecución será sumar y restar valores de los exponentes de acuerdo al algoritmo de multiplicación, pero piensa que todo eso será operar con enteros, lo que es mucho más rápido que manejar números reales (sí, incluso con los procesadores de hoy día y con toda probabilidad todavía con los de dentro de 5 años).

Para terminar, un último ejemplo del poder de esta técnica: supongamos que queremos convolucionar una serie de números por un kernel Gausiano de una sigma dada. En un programa clásico, habría que o bien calcular en tiempo de ejecución los coeficientes de la Gausiana, o bien meterlos como una tabla, ya que esa parte siempre será invariable:

Pues bien, dado una sigma en concreto, se puede hacer a mano en un papel la secuencia de operaciones óptimas (aprovechar la simetría, etc.), y se podría llegar a algo así:

int *data;
int a;

void foo()
{
a = (data[-8] +data[8])*3;
a += (data[-7] +data[7])*12;
a += (data[-6] +data[6])*36;
a += (data[-5] +data[5])*88;
a += (data[-4] +data[4])*181;
a += (data[-3] +data[3])*318;
a += (data[-2] +data[2])*474;
a += (data[-1] +data[1])*603;
a += (data[0])*653;
a /= 4069;
}


Dificilmente se puede hacer algo más óptimo, pero piensa que has tenido que deducir a mano el algoritmo para un caso concreto del valor de sigma y para un tamaño de ventana fijo. Si en lugar de 17 muestras (-8...0...8) ahora quisiéramos 20 o 30, tendrías que echar cuentas y cambiar bastante el programa.


En cambio, con metaprogramación el número de muestras o el valor de sigma son constantes que se introducen a la hora de compilar, y es el compilador el que llega a la misma serie de operaciones que se han sacado arriba, o incluso a algo mejor. 


Podéis ver el código de este ejemplo con metaprogramación aquí y una comparación del código ensamblador generado por GCC comparado con la optimización manual... y ¡realmente sale ganando la metaprogramación!



Dedicado a... Ñbrevu ;-)

Puede que también te guste...

Shares