Little Endian y Big Endian

August 3rd, 2010 admin No comments

¿De qué va esto del endian? No, no se trata de indios pequeñitos…
El endianness de un procesador indica, básicamente, el orden de almacenamiento de los bytes de las variables de más de un byte en la memoria.
Los dos tipos de endian principales son el Little-Endian y el Big-Endian.
En little-endian los bytes se almacenan en orden inverso al natural, es decir, primero el byte menos significativo (LSB) y de último el más significativo (MSB).
Por ejemplo el número de 32 bits 0×10203040 se almacena así en memoria (cada recuadro representa un byte):

Y el número de 16 bits 0×1020 así:

En big-endian se sigue el orden normal, primero el byte más significativo (MSB) y de último el menos significativo (LSB):

En la plataforma PC (procesadores Intel y AMD) se utiliza little-endian así como en los Z80 y VAX.
Los procesadores Motorola 68000, los PowerPC (de Motorola) y los SPARK (de Sun) son big-endian.
Luego hay procesadores que son configurables y pueden operar en los dos formatos; MIPS, ARM y los SPARC y PowerPC modernos, por ejemplo.

Como regla general si un programa va a ser compilado y ejecutado en diversas plataformas hay que tener en cuenta el endian y programarlo de forma que se detecte el endian del procesador y se actúe en consecuencia en cada caso, de lo contrario te vas a encontrar con una larga serie de preciosos bugs muy difíciles de rastrear y que te pueden dar largas horas de “diversión”.
Hay dos casos principales en donde se debe tener muy en cuenta el endian; el primero es cuando el programa graba/lee archivos y el segundo cuando establece conexiones de red.
El problema en el primer caso es evidente, un ejemplo; con el programa ejecutándose en un PC grabas una serie de estructuras de datos en un archivo, si luego ejecutas el mismo programa en un procesador 68000 y cargas el archivo que previamente habías grabado desde un PC, los datos de las estructuras del archivo se cargarán invertidos ya que el endian de ambas plataformas no es el mismo (se grabaron los datos en little-endian y los lees como big-endian).
Con la programación de red el problema es más simple: todas las transferencias de datos se realizan en big-endian independientemente de la plataforma que las ejecute, éste es el motivo por el cual al formato big-endian también se le conoce como “Network Byte Order”.  Por eso las librerías de sockets incluyen funciones de conversión de endian:

  • htonl(): Host to network byte order (long, 32 bits). Convierte una variable de 32 bits del endian del procesador a formato big-endian.
  • ntohl(): Network to host byte order (long, 32 bits). Convierte una variable de 32 bits de big-endian al endian del procesador.
  • htons()Host to network byte order (short, 16 bits). Convierte una variable de 16 bits del endian del procesador a formato big-endian.
  • ntohs()Network to host byte order (short, 16 bits). Convierte una variable de 16 bits de big-endian al endian del procesador.

Volviendo al problema de la grabación de archivos, tienes dos alternativas para evitar este tipo de problemas:

  • La primera forma es incluir una firma al inicio del archivo que servirá no sólo para identificar el tipo de archivo sino también para saber si fue grabado en una plataforma de distinto endian, y si es así ya sabes que tendrás que leerlo invirtiendo los datos, si por ejemplo usas como firma dos bytes al inicio del archivo como 0xAAFF (un entero de 16 bits) y en otra plataforma al leer el short de la firma se carga como 0xFFAA significa que el programa tendrá que convertir el endian del archivo, si la hubiera leído como 0xAAFF entonces significa que el endian del procesador que grabó el archivo y el endian del procesador que lo ha leído son el mismo y no es necesaria ninguna conversión.
  • La segunda es grabar siempre los archivos en un endian determinado (a ser posible en el endian de la plataforma que se vaya a utilizar con más frecuencia), de esta forma, si por ejemplo has decidido que el archivo sea de formato big-endian lo único que tendrás que hacer es grabarlo y leerlo como big-endian siempre, independientemente de la plataforma. Fácil, no?

¿Y cómo detectas el endian de un procesador? Pues muy fácil, comprobando cómo almacena las variables de más de un byte en memoria:

1
2
3
4
5
6
7
8
enum Endian { LITTLE_ENDIAN, BIG_ENDIAN };

Endian ComprobarEndian()
{
  unsigned i = 1;

  return(((*(char*)&i) == 1) ? LITTLE_ENDIAN : BIG_ENDIAN);
}

Con un puntero char comprobamos el contenido del primer byte en memoria de los cuatro que forman la variable entera i de 32 bits, si el procesador es little-endian el valor 1 estará almacenado en el primer byte de la secuencia en memoria [0x01, 0x00, 0x00, 0x00] y por lo tanto la comparación será verdadera y se devolverá LITTLE_ENDIAN, si el procesador es big-endian el 1 estará en el cuarto byte en la memoria [0x00, 0x00, 0x00, 0x01] y la comparación será falsa devolviendo por lo tanto BIG_ENDIAN.

Para terminar solo queda por ver cómo cambiar el endian de una variable (de little-endian a big-endian y viceversa), esta función cambia variables de 16 bits (short):

1
2
3
4
5
6
7
8
9
short CambiarEndian(short valor)
{
  char *p = (char *)&valor;
  char tmp = p[0];
  p[0] = p[1];
  p[1] = tmp;

  return(valor);
}

Y ésta cambia el endian de variables de 32 bits:

1
2
3
4
5
6
7
8
9
10
11
12
int CambiarEndian(int valor)
{
  char *p = (char *)&valor;
  char tmp = p[0];
  p[0] = p[3];
  p[3] = tmp;
  tmp = p[1];
  p[1] = p[2];
  p[2] = tmp;

  return(valor);
}

Evaluar expresiones matemáticas

July 25th, 2010 admin No comments

Existen tres notaciones básicas para representar expresiones matemáticas; infija, prefija y postfija.
La infija es la más conocida porque es la que más se utiliza, por ejemplo: (1+2)*(3-4).
En forma prefija se representaría como *+12-34, y en forma postfija sería 12+34-*.

La forma infija resulta muy sencilla para los humanos, estamos acostumbrados a ella y es muy simple. Sin embargo requiere del uso de paréntesis para establecer el orden correcto de las operaciones a realizar, y esto supone un engorro a la hora de programar un evaluador de expresiones.  El “truco” consiste en convertir la expresión de infja a postfija o prefija, de esta forma nos deshacemos de los paréntesis ya que las notaciones prefija y postfija no los necesitan.

Una vez convertida la expresión a notación postfija o prefija es muy fácil crear un árbol binario para calcular el resultado de la expresión.

Los más observadores ya se habrán dado cuenta de que la notación postfija es también conocida como RPN (“Reverse Polish Notation”, notación polaca inversa). Fué inventada por el filósofo y matemático polaco Lukasiewicz precisamente como una notación alternativa para evitar los paréntesis en la expresiones. Más de uno habrá usado esta notación en las calculadoras RPN, especialmente de HP, ¿verdad?

Vamos a ver con un ejemplo muy simple como, usando simplemente un stack,  se puede convertir cualquier expresión infija (por compleja que sea) a notación postfija. Explicaré solamente la conversión de infija a postfija. La conversión a prefija es igual de sencilla pero lo dejo como ejercicio de pasatiempo para el que le apetezca.

Se va cogiendo cada elemento de la expresión (de izquierda a derecha) y se siguen estos pasos:

  1. Si el elemento es un número o variable se copia directamente a la salida.
  2. Si es un paréntesis izquierdo se mete en el stack.
  3. Si es un paréntesis derecho, se van sacando uno a uno todos los elementos del tope del stack (y copiándolos en la salida) hasta encontrar un paréntesis izquierdo en el stack. Finalmente ambos paréntesis se descartan.
  4. Si es un operador y en el tope del stack no hay un operador o hay un operador de menor precedencia entonces se añade el nuevo operador al stack.
  5. Si es un operador y en el tope del stack hay un operador de mayor o igual precedencia entonces se saca el operador del stack y se copia en la salida, y se repite la comparación del operador con el nuevo tope del stack.
  6. Cuando ya no quedan más elementos en la expresión se van sacando uno a uno todos los elementos del stack y se copian en la salida.

Usaré el ejemplo inicial en notación infija: (1+2)*(3-4).

  • ( Se mete en el stack.  
    STACK[ ( ]  SALIDA[ ]
  • 1 Se copia en la salida.
    STACK[ ( ]  SALIDA[ 1 ]
  • + Operador, en el tope del stack no hay otro operador, se mete en el stack.
    STACK[ +( ]  SALIDA[ 1 ]
  • 2 Se copia en la salida.
    STACK[ +( ]  SALIDA[ 12 ]
  • ) Se sacan del stack y se copian en la salida todos los elementos hasta encontrar un paréntesis izquierdo.  
    STACK[ ]  SALIDA[ 12+ ]
  • * Operador, en el tope del stack no hay otro operador, se mete en el stack.  
    STACK[ * ]  SALIDA[ 12+ ]
  • ( Se mete en el stack.  
    STACK[ (* ]  SALIDA[ 12+ ]
  • 3 Se copia en la salida.
    STACK[ (* ]  SALIDA[ 12+3 ]
  • - Operador, en el tope del stack no hay otro operador, se mete en el stack.  
    STACK[ -(* ]  SALIDA[ 12+3 ]
  • 4 Se copia en la salida.  
    STACK[ -(* ]  SALIDA[ 12+34 ]
  • ) Se sacan del stack y se copian en la salida todos los elementos hasta encontrar un paréntesis izquierdo.  
    STACK[ * ]  SALIDA[ 12+34- ]
  • Ya no quedan más elementos en la expresión, se sacan todos del stack y se copian en la salida.  
    STACK[ ]  SALIDA[ 12+34-* ]

El resultado final en notación postfija es 12+34-*

Ahora resulta muy sencillo evaluar la expresión creando un árbol binario. Para crearlo usamos un stack y vamos cogiendo cada elemento de la expresión en notación postfija (de izquierda a derecha);

  • Si el elemento es un número o variable se crea un nodo con él y se mete en el stack.
  • Si el elemento es un operador binario se crea un nodo con dicho operador, se extraen del stack dos nodos y se le añaden como hijos, finalmente el nuevo nodo se añade al stack.
  • Si el elemento es un operador unuario se crea un nodo con dicho operador, se extrae del stack un nodo y se le añade como hijo, finalmente el nuevo nodo se añade al stack.
  • El proceso se repite hasta que no queden más elementos en la expresión.

Para terminar, simplemente recorriendo recursivamente el árbol en inorden podemos calcular el resultado final de la expresión o incluso reconstruirla en su notación infija:

  1. Imprimimos paréntesis izquierdo.
  2. Visitamos subárbol izquierdo (*).
  3. Imprimimos la raíz.
  4. Visitamos subárbol derecho (*).
  5. Imprimimos paréntesis derecho.

(*): El proceso se repite recursivamente en los pasos 2 y 4.

Interpolando que es gerundio

June 20th, 2010 admin No comments

Hay pocas cosas tan útiles en programación como la interpolación, de hecho son tantos los casos en los que resulta útil (o incluso esencial) que ni me voy a molestar en mencionarlos.
Directamente dejo aqui un par de ejemplos, el primero es una función de interpolación lineal:

1
2
3
4
float InterpLineal(float tiempo, float inicio, float fin)
{
  return(tiempo * inicio + (1.0f - tiempo) * fin);
}

Esta es una función de interpolación cuadrática (“Easy In”):

1
2
3
4
float InterpCuadIn(float tiempo, float inicio, float fin)
{
  return(InterpLineal(tiempo * tiempo, incio, fin));
}

Y por último una interpolación cuadrática (“Easy In-Out”):

1
2
3
4
5
6
7
8
9
10
11
12
float InterpCuadInOut(float tiempo, float inicio, float fin)
{
  float medio = (inicio + fin) * 0.5f;
  tiempo *= 2.0f;
  if(tiempo <= 1.0f)
  {
    return(InterpLineal(tiempo * tiempo, inicio, medio));
  }
  tiempo -= 1.0f;
   
  return(InterpLineal(tiempo * tiempo, medio, fin));
}

En los tres casos se fija el rango a interpolar con los parámetros inicio y fin, y con el parámetro tiempo se indica el punto de interpolación (por supuesto se asume que tiempo tendrá un valor comprendido entre 0.0 y 1.0).

Transformaciones inversas, inversión de matrices

August 17th, 2009 admin No comments

En programación 3D en tiempo real es imprescindible optimizar todo lo posible, y la inversión de matrices homogéneas es uno de los casos complejos (aparentemente) en donde se puede conseguir una excelente optimización siguiendo las reglas del álgebra matricial y conociendo cómo ha sido generada la matriz a invertir (conociendo su estructura).

Nota: En este post usaré el formato fila (pre-multiplicación) para representar las matrices y la formulación.

Vamos a ver primero la inversión aislada de los tres casos básicos, matriz de rotación, escala y traslación:

Si la matriz de rotación R es ortogonal (si sus tres ejes son perpendiculares entre si), entonces su inversa es simplemente su traspuesta:

R=\begin{bmatrix}RXx&RXy&RXz&0\\RYx&RYy&RYz&0\\RZx&RZy&RZz&0\\0&0&0&1\end{bmatrix}

R^{-1}=R^{T}=\begin{bmatrix}RXx&RYx&RZx&0\\RXy&RYy&RZy&0\\RXz&RYz&RZz&0\\0&0&0&1\end{bmatrix}

La inversa de una matriz de escala S es muy sencilla:

S=\begin{bmatrix}Sx&0&0&0\\0&Sy&0&0\\0&0&Sz&0\\0&0&0&1\end{bmatrix}

S^{-1}=\begin{bmatrix}\frac{1}{Sx}&0&0&0\\0&\frac{1}{Sy}&0&0\\0&0&\frac{1}{Sz}&0\\0&0&0&1\end{bmatrix}

Y la inversa de una matriz de traslación T también es muy simple:

T=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\Tx&Ty&Tz&1\end{bmatrix}

T^{-1}=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\-Tx&-Ty&-Tz&1\end{bmatrix}

Ahora veamos un caso más práctico, cómo invertir una matriz de transformación RT (es decir, una matriz que primero realiza una rotación y luego una traslación). Es imprescindible saber siempre el orden de las transformaciones contenidas en una matriz para poder optimizar el cálculo de su inversa ya que vamos a optimizar los cálculos por partes y siguiendo una regla muy simple; la inversa del producto de dos matrices es igual al producto invertido de las inversas de dichas matrices: (A*B)^{-1}=B^{-1}*A^{-1}

Con esta regla tan simple podemos invertir una matriz RT multiplicando la inversa de la traslación por la inversa de la rotación: (R*T)^{-1}=T^{-1}*R^{-1} y como ya sabemos que la inversa de una matriz ortogonal es su traspuesta la fórmula final será: (R*T)^{-1}=T^{-1}*R^{T}

Con lápiz y papel calculamos la estructura final de la matriz inversa de una transformación RT:

\large(R*T)^{-1}=\begin{bmatrix}RXx&RYx&RZx&0\\RXy&RYy&RZy&0\\RXz&RYz&RZz&0\\-(RXx*Tx+RXy*Ty+RXz*Tz)&-(RYx*Tx+RYy*Ty+RYz*Tz)&-(RZx*Tx+RZy*Ty+RZz*Tz)&1\end{bmatrix}

Para invertir una matriz TR es incluso más simple: (T*R)^{-1}=R^{T}*T^{-1}

(T*R)^{-1}=\begin{bmatrix}RXx&RYx&RZx&0\\RXy&RYy&RZy&0\\RXz&RYz&RZz&0\\-Tx&-Ty&-Tz&1\end{bmatrix}

Ahora veremos cómo invertir matrices que incluyen transformaciones de escala isométrica (que significa que se ha aplicado la misma escala a los tres ejes), empecemos por la clásica transformación SRT (donde primero se escala, luego se rota y finalmente se traslada). Como siempre su inversa será: (S*R*T)^{-1}=T^{-1}*R^{T}*S^{-1}

Volvemos a coger el lápiz y calculamos:

\large(S*R*T)^{-1}=\begin{bmatrix}\frac{RXx}{S}&\frac{RYx}{S}&\frac{RZx}{S}&0\\\frac{RXy}{S}&\frac{RYy}{S}&\frac{RZy}{S}&0\\\frac{RXz}{S}&\frac{RYz}{S}&\frac{RZz}{S}&0\\-\frac{RXx*Tx+RXy*Ty+RXz*Tz}{S}&-\frac{RYx*Tx+RYy*Ty+RYz*Tz}{S}&-\frac{RZx*Tx+RZy*Ty+RZz*Tz}{S}&1\end{bmatrix}

La misma inversa SRT pero de una matriz con escalado anisométrico (escalado no idéntico en los tres ejes) sería:

\large(S*R*T)^{-1}=\begin{bmatrix}\frac{RXx}{Sx}&\frac{RYx}{Sy}&\frac{RZx}{Sz}&0\\\frac{RXy}{Sx}&\frac{RYy}{Sy}&\frac{RZy}{Sz}&0\\\frac{RXz}{Sx}&\frac{RYz}{Sy}&\frac{RZz}{Sz}&0\\-\frac{RXx*Tx+RXy*Ty+RXz*Tz}{Sx}&-\frac{RYx*Tx+RYy*Ty+RYz*Tz}{Sy}&-\frac{RZx*Tx+RZy*Ty+RZz*Tz}{Sz}&1\end{bmatrix}

Para terminar veremos la inversa de una matriz que represente una transformación RTS. La inversa con escalado isométrico es:

\large(R*T*S)^{-1}=\begin{bmatrix}\frac{RXx}{S}&\frac{RYx}{S}&\frac{RZx}{S}&0\\\frac{RXy}{S}&\frac{RYy}{S}&\frac{RZy}{S}&0\\\frac{RXz}{S}&\frac{RYz}{S}&\frac{RZz}{S}&0\\-(RXx*Tx+RXy*Ty+RXz*Tz)&-(RYx*Tx+RYy*Ty+RYz*Tz)&-(RZx*Tx+RZy*Ty+RZz*Tz)&1\end{bmatrix}

Y la inversa de una matriz RTS con escala anisométrica es:

\large(R*T*S)^{-1}=\begin{bmatrix}\frac{RXx}{Sx}&\frac{RYx}{Sy}&\frac{RZx}{Sz}&0\\\frac{RXy}{Sx}&\frac{RYy}{Sy}&\frac{RZy}{Sz}&0\\\frac{RXz}{Sx}&\frac{RYz}{Sy}&\frac{RZz}{Sz}&0\\-(RXx*Tx+RXy*Ty+RXz*Tz)&-(RYx*Tx+RYy*Ty+RYz*Tz)&-(RZx*Tx+RZy*Ty+RZz*Tz)&1\end{bmatrix}

Si teneis dificultades para ver alguna de las matrices pulsad con el botón derecho del ratón sobre ella y elegid Abrir/Ver imagen.

Formato interno de las matrices en OpenGL

August 15th, 2009 admin No comments

Desde los inicios de OpenGL existe una confusión bastante importante sobre cómo administra internamente las matrices. Unos piensan que las almacena en formato fila y otros piensan que lo hace en formato columna. Pues lo cierto es que ni una cosa ni la otra!
OpenGL almacena las matrices en un array unidimensional de 16 elementos y es el programador quien decide cómo prefiere interpretarlas.

Quedará más claro con un ejemplo:

1
2
GLfloat m[16];
glGetFloatv(GL_MODELVIEW_MATRIX, m);


Con el código anterior leemos la matriz actual MODELVIEW y la almacenamos en el array m.

¿Y cómo están estructurados los elementos de la matriz? Pues muy sencillo, secuencialmente:

m = \{m0,m1,m2,m3,m4,m5,m6,m7,m8,m9,m10,m11,m12,m13,m14,m15\}

Ahora el programador puede decidir interpretarlo como una matriz de tipo columna:

\begin{bmatrix}m0&m4&m8&m12\\m1&m5&m9&m13\\m2&m6&m10&m14\\m3&m7&m11&m15\end{bmatrix}

O como una matriz de tipo fila:

\begin{bmatrix}m0&m1&m2&m3\\m4&m5&m6&m7\\m8&m9&m10&m11\\m12&m13&m14&m15\end{bmatrix}

Matemáticamente es indiferente cómo prefieras interpretarlas, pero recuerda que si utilizas el formato columna debes realizar post-multiplicaciones, y si usas el formato fila pre-multiplicaciones.

Supongamos que tienes una matriz R que representa una rotación y la matriz T que realiza una traslación, y quieres combinarlas en una matriz C, de forma que la matriz de trasformación resultante realice primero la rotación y luego la traslación. Si usas el formato fila tendrás que hacer una pre-multiplicación: C=R*T (Esto se lee: la matriz R pre-multiplica a la matriz T).
Pero si usas el formato columna el orden se invierte ya que es una post-multiplicación: C=T*R (Y esto se lee: la matriz R post-multiplica a la matriz T).

Otro ejemplo; quieres transformar el vector V=\{x,y,z,0\} por la matriz M para obtener el vector transformado V'.
Si la matriz M es de tipo fila pre-multiplicas: V'=V*M
En cambio, si es de tipo columna post-multiplicas: V'=M*V

En algebra matricial siempre se multiplican filas por columnas, por lo tanto si la matriz M es de tipo fila V y V' deben ser interpretados como un vectores fila, y si M es de tipo columna entonces V y V' deberán ser interpretados como vectores columna.

Un último ejemplo; transforma el vector V por las matrices A,B,C (en éste orden).
La pre-multiplicación sigue el orden natural de las transformaciones por lo que resulta más intuitiva: V'=V*A*B*C
La post-multiplicación sería el proceso inverso: V'=C*B*A*V

Para terminar un truco para no liarte; cuando utilices matrices y vectores columna (post-multiplicación) debes interpretar las transformaciones como series de funciones: V'=C(B(A(V)))

Declaraciones complejas en C/C++

June 5th, 2009 admin No comments

Aunque parezca sorprendente muy pocos programadores pueden entender una declaración como ésta:

int *const(*(*(*dec)())[64])(int (*)(void *), double[10]);

No es extraño que sea poco comprensible ya que las declaraciones en C y C++ mezclan operadores que se evalúan de forma infija con otros de evaluación postfija, para el compilador esto no supone ningún problema pero para los programadores sí.
El truco está en interpretarlas tal y como lo hace el compilador; a partir del identificador avanzar hacia la derecha siempre que sea posible, y si no lo es, avanzar hacia la izquierda.

Quedará más claro con un ejemplo mucho más simple:

float *var[];

¿Qué representa var?, ¿es un puntero a un array de floats, o es un array de punteros a float?
Es un array de punteros a float:

  • A partir del identificador var avanzamos hacia la derecha y nos encontramos con [] (var es un array…).
  • No podemos seguir avanzando hacia la derecha, entonces lo hacemos hacia la izquierda y nos encontramos con * (var es un array de punteros…) y luego con float (var es un array de punteros a float).

    Otro ejemplo muy simple:

    const double *(*op)(int);
  • A partir del identificador op avanzamos hacia la derecha y nos encontramos con ) (cierre de paréntesis), por lo que el avance rebota hacia la izquierda y…
  • Nos encontramos con * (op es un puntero…) y luego con ( por lo que el avance vuelve a rebotar y ahora avanzamos hacia la derecha y…
  • Nos encontramos con (int) (op es un puntero de función que recibe un int…), ya no podemos avanzar más hacia la derecha, por lo que volvemos hacia la izquierda y…
  • Encontramos un * (op es un puntero de función que recibe un int y devuelve un puntero…), seguimos hacia la izquierda y…
  • Finalmente encontramos a double y const, (op es un puntero de función que recibe un int y devuelve un puntero a double constante).

    ¿Qué pasaría si eliminamos los paréntesis?

    const double **op(int);

    Pues que la declaración cambia totalmente y ahora op es una función que recibe un int y que devuelve un puntero de puntero a double constante. ¿A que ahora ya entiendes el porqué de los paréntesis en las declaraciones de punteros de función (*)()?

    Vamos a ver ahora el primer ejemplo que he puesto:

    int *const(*(*(*dec)())[64])(int (*)(void *), double[10]);
  • A partir del identificador dec avanzamos hacia la derecha y nos encontramos con ) por lo que el avance rebota hacia la izquierda y…
  • Encontramos * (dec es un puntero…) y luego con ( por lo que el avance vuelve a rebotar y ahora avanzamos hacia la derecha y…
  • Encontramos () (dec es un puntero de función…), seguimos hacia la derecha y encontramos ), volvemos hacia la izquierda…
  • Encontramos * (dec es un puntero de función que devuelve un puntero…), a continuación encontramos otro ( por lo que volvemos hacia la derecha y…
  • Encontramos [64] (dec es un puntero de función que devuelve un puntero a un array de 64…), ahora encontramos otro ), volvemos a la izquierda y…
  • Encontramos * (dec es un puntero de función que devuelve un puntero a un array de 64 punteros…), seguimos hacia la izquierda y encontramos (, volvemos hacia la derecha y…
  • Encontramos (int (*)(void *), double[10]) (dec es un puntero de función que devuelve un puntero a un array de 64 punteros de función que reciben un puntero de función (que a su vez recibe como primer parámetro un puntero de función que devuelve int y recibe un puntero void, y recibe como segundo parámetro un array de 10 doubles)…), hacia la derecha ya no podemos avanzar más, volvemos hacia la izquierda y…
  • Finalmente encontramos const, * y luego int (dec es un puntero de función que devuelve un puntero a un array de 64 punteros de función que reciben un puntero de función (que a su vez recibe como primer parámetro un puntero de función que devuelve int y recibe un puntero void, y recibe como segundo parámetro un array de 10 doubles) y que devuelven un puntero constante a int)

    Al principio dije que las declaraciones se comienzan a leer a partir del identificador, pero ¿qué pasa cuando hay más de uno?

    int *const(*a(char *b))(long c, const int &d)

    En ésta declaración tenemos cuatro identificadores; a, b, c y d. ¿Por cuál se empieza? Debes fijarte que b, c y d están realmente declarando parámetros de función, por lo tanto se comienza por a (a es una función que recibe (char *b) y devuelve un puntero de función que recibe (long c, const int &d) y que devuelve un puntero constante a int).

    Veamos un último ejemplo:

    char (*(*extra[32])(const float &))[16];
  • A partir de extra vamos hacia la derecha y encontramos [32] (extra es un array de 32…), seguimos y encontramos ), cambiamos hacia al izquierda…
  • Encontramos * (extra es un array de 32 punteros…), seguimos hacia la izquierda y encontramos (, cambiamos hacia la derecha…
  • Encontramos (const float &) (extra es un array de 32 punteros de función que reciben una referencia a float constante…), seguimos hacia la derecha y nos encontramos con ), cambiamos hacia la izquierda…
  • Encontramos * (extra es un array de 32 punteros de función que reciben una referencia a float constante y devuelven un puntero…), seguimos hacia la izquierda y encontramos (, cambiamos hacia la derecha y…
  • Encontramos [16] (extra es un array de 32 punteros de función que reciben una referencia a float constante y devuelven un puntero a un array de 16…), ya no podemos seguir más hacia la derecha, volvemos a la izquierda…
  • Encontramos char (extra es un array de 32 punteros de función que reciben una referencia a float constante y devuelven un puntero a un array de 16 chars…).

    El hecho de que puedas crear y entender declaraciones de cualquier grado de complejidad no significa que debas hacerlo. Es siempre recomendable intentar no complicarlas demasiado y, si no queda más remedio, simplificarlas usando alias con typedef. Aquí unos ejemplos muy desglosados:

    typedef int *I;

    I es un puntero a int.

    typedef I J[];

    J es un array de punteros a int.

    typedef J K();

    K es una función que devuelve un array de punteros a int.

    typedef K *X;

    X es un puntero a una función que devuelve un array de punteros a int.

    typedef bool Y(X);

    Y es una función que devuelve un bool y recibe un puntero de función que devuelve un array de punteros a int.

    typedef Y *Z[10];

    Z es un array de 10 punteros de función que devuelven bool y reciben un puntero de función que devuelve un array de punteros a int.

    Declarando una variable var a partir del alias Z esta sería su declaración:

    Z var; // Esto es equivalente a declarar: bool (*var[10])(int *(*)()[])

    Es evidente que usando typedef la declaración es mucho más simple que hacer declaraciones complejas directamente. Aunque hay que tener en cuenta que este es un ejemplo y en realidad no es ni mucho menos necesario declarar el alias Z usando seis typedefs tan simples, se podría haber declarado usando solamente dos, tres… los que se consideren necesarios… o incluso sólo una:

    typedef bool (*Z[10])(int *(*)()[]);

    El uso correcto de typedef es esencial para mantener un código lo más sencillo y claro posible, porque sino, entre otras cosas, puede pasar ésto:

  • Categories: C++ Tags: , ,

    Raíz cuadrada, optimización redonda

    May 7th, 2009 admin No comments

    En programación 3D hay pocas funciones tan necesarias como la raíz cuadrada. ¿Quién no recuerda el famoso teorema de Pitágoras? El cuadrado de la hipotenusa es igual a la suma de los cuadrados de los catetos h^{2}=x^{2} + y^{2} por lo tanto la hipotenusa será h=\sqrt{x^{2} + y^{2}}

    Esto lo podemos emplear con cualquier número de dimensiones, en 3D tendremos tres coordenas \left\{x,y,z\right\} que definen un punto o vector en un espacio tridimensional, aplicando el mismo teorema podemos saber el módulo (longitud) del vector m=\sqrt{x^{2}+y^{2}+z^{2}} y a partir del módulo podemos, por ejemplo, normalizarlo (hacer que el vector sea de módulo 1).

    Un ejemplo práctico:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    V3 &NormalizarVector(V3 &v)
    {
      float modulo = sqrt( v.x*v.x + v.y*v.y + v.z*v.z);

      assert(modulo != 0.0f);

      v.x /= modulo;
      v.y /= modulo;
      v.z /= modulo;

      return(v);
    }

    La función anterior para normalizar vectores es perfectamente correcta pero se puede optimizar bastante. En primer lugar calcular raíces cuadradas tiene un coste computacional bastante importante y en aplicaciones 3D como juegos se usa constantemente por lo que es interesante optimizarla todo lo posible. Además de la raíz cuadrada también podemos sustituir las tres divisiones por tres multiplicaciones, ¿cómo lo hacemos? usando la inversa de la raíz cuadrada \frac{1}{\sqrt{x}} que nos permitirá multiplicar en lugar de dividir ya que la división está implícita en el cálculo.

    ¿Y cómo optimizamos la raíz cuadrada? Existen muchas formas de hacerlo pero vamos a ver la más rápida y sencilla, la raíz cuadrada inversa rápida (Fast InvSqrt):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    float InvSqrt (float x)
    {
      float x_div2 = x * 0.5f;         // Dividimos x entre 2
      int i = *(int*) &x;              // Pasamos de float a int (ambos de 32 bits)
      i = 0x5f3759df - (i >> 1);       // Hacemos una primera aproximación del resultado
      x = *(float*) &i;                // Pasamos de int a float
      x = x * (1.5f - x_div2 * x * x); // Recalculamos para aproximar más el resultado

      return(x);
    }

    Esta función se aprovecha de la forma interna de trabajo de la unidad de punto flotante (normativa IEEE 754)  para calcular una buena aproximación del resultado exacto. No es más que una simple aproximación por el método Newton.
    Este código se hizo muy popular por haber sido utilizado en el Quake 3 y aunque su origen no está nada claro parece que surgió de SGI (Silicon Graphics) hace bastantes años.

    La nueva función de normalización vectorial quedaría de la siguiente manera:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    V3 &NormalizarVector(V3 &v)
    {
      float m = InvSqrt( v.x*v.x + v.y*v.y + v.z*v.z);

      v.x *= m;
      v.y *= m;
      v.z *= m;

      return(v);
    }

    El incremento de velocidad conseguido es muy importante pero también hay que tener en cuenta que el resultado es una aproximación y que este código sólo puede usarse en procesadores cuyas unidades de punto flotante sigan la normativa IEEE 754.

    En ocasiones veo tanques…

    February 27th, 2009 admin No comments

    Crear y entrenar correctamente RNAs (Redes Neuronales Artificiales) tiene más de arte que de ciencia.

    En primer lugar debes decidir el tipo de red más apropiada para el trabajo que debe realizar (Backpropagation, Hopfield, Adaline, Kohonen, Perceptrón Multicapa, máquina de Boltzman, etc. Incluyendo también la elección de sus funciones de propagación, activación/transferencia) y luego decidir su topología (monocapa, multicapa o recurrente), después viene su entrenamiento (con aprendizaje supervisado o no supervisado) para lo cual debes escoger una buena selección de ejemplos del problema que deba resolver y entrenarla lo justo y necesario para que entienda el problema correctamente en lugar de simplemente memorizar los ejemplos que ha visto durante su entrenamiento. O lo que puede ser aún peor; que entienda el problema de una forma completamente distinta a la que tu esperas…  …bueno, lo cierto es que siempre lo entienden como les da la gana, y como casi todo en IA una pequeña dosis de caos es esencial.

    Para cada problema es necesario encontrar la mejor elección de su tipología (tipo de red), topología (número de capas y número de neuronas por capa -en el caso de redes multicapa-), cuál es la estructura y codificación de la información de entrada y salida que sea más adecuada; muestras y método de entrenamiento, tipo de función de transferencia…
    Si diseñas una red demasiado grande para el problema a tratar o la sobreentrenas lo único que hará será memorizar las muestras de entrenamiento, si es demasiado pequeña o no has escogido una buena y variada selección de muestras no logrará entenderlo o lo hará de una forma parcial. No te queda otra que probar y probar hasta encontrar el balance ideal para que la red pueda generalizar en base a su entrenamiento.

    Toda su inteligencia reside en el peso de sus conexiones, en el caso de las redes multicapa, cada neurona recibe las señales de las neuronas de la capa anterior, multiplica cada señal por el peso asociado a cada conexión y hace un sumatorio de todas, si su valor es positivo la neurona excitará a las neuronas de la siguiente capa y si es negativo las inhibirá. A ésto se le denomina como función de propagación.
    Generalmente se programa también una función de activación o transferencia, que sirve para normalizar la salida de la función de propagación dentro de un intervalo determinado, las más utilizadas son:

    • Sigmoidea: 1/1+exp(-x) (para un intervalo de 0 a 1).
    • Tangente hiperbólica:  tanh(x) (para un intervalo de -1 a 1).

    Es también habitual realizar un escalamiento de la salida de la función de activación simplemente multicándolo por un valor de escala más la suma de un valor de desplazamiento. Integrándolo directamente en las funciones de activación que he puesto de ejemplo quedarían así:

    • Sigmoidea: 1/1+exp(-2*s*(x+t))
    • Tangente hiperbólica: tanh(s*(x+t))

    Siendo x el valor de entrada, s la escala y t el desplazamiento.

      Ejemplo de una red Perceptrón Multicapa (MLP) de 3 capas; una de entrada de 27 neuronas,
      una capa oculta de 22 y una capa de salida con una neurona. Haciendo un total de 13.090 conexiones sinápticas.

      Y ahora el mejor ejemplo de cómo las RNAs hacen lo que les da la gana. En los 80 los militares norteamericanos se gastaron un buen montón de millones de dólares en un proyecto para incorporar en sus tanques un sistema de detección de tanques enemigos. El sistema consistía en una cámara conectada a un ordenador que iba analizando constantemente las imágenes y avisaba en el caso de que detectase un tanque.

      Para este problema decidieron usar una red neuronal. La entrenaron con 200 fotografías; 100 fotos de tanques ocultos tras arboledas y 100 de árboles sin tanques. Hasta aquí todo bien, el entramiento funcionó perfectamente y el sistema era capaz de clasificar las fotos del entrenamiento.

      Llegó el momento de probarlo y… oh! sorpresa! El sistema fallaba por todos lados y no daba ni una! En primer lugar pensaron que había memorizado las fotos de entrenamiento (y por lo tanto estaría intentando recordar en lugar de generalizar), pero después de mucho investigar, comprobar, verificar, analizar  y gastar pasta, se dieron cuenta de que las 100 fotos con tanques las habían sacado en días nublados y las otras 100 sin tanques en días soleados, la red había aprendido a reconocer lo que era más evidente; el cielo!
      Millones de dólares para que un tanque te diga si hace sol… Ummm, un poco caro, no?

      Y ahora os dejo con un buen ejemplo muy original de una red neuronal de 10 millones de conexiones sinápticas y una tasa de aciertos del 80% que es capaz de adivinar en qué objeto estás pensando con menos de 20 preguntas.

    Falsas entrevistas y C++0x

    February 21st, 2009 admin No comments

    Queda oficialmente inaugurado este pequeño blog, tengo poco tiempo pero intentaré actualizarlo al menos un par de veces por semana. Hace tiempo que tenía ganas de hacer uno pero siempre la falta de tiempo para atenderlo iba posponiendo la idea, ahora he decidido hacerlo pero, como indica su título, pretendo no emplear nunca más de 10 minutos para crear cada nueva entrada. Como veis los comentarios están desactivados (al menos de momento) así no quedo de maleducado si no me paro a responderlos ; )

    Bromas aparte, no se me ocurre nada mejor para comenzar que dedicarle la primera entrada al padre de C++, Bjarne Stroustrup. Un danés que ahora enseña ciencias de la computación en la Universidad A&M de Texas pero que se ha pasado la vida trabajando en los laboratorios Bell de AT&T en USA en donde, allá por 1980, creó el primer prototipo de C++ llamado “C con clases” y que todavía no era un compilador sino que, por medio del preprocesador, traducía el código a C para poder ser compilado. Posteriormente creó el primer compilador de C++ llamado CFront aunque también seguía generando código C de salida.
    Por cierto, el CFront fue programado con el “C con clases”… tiene su punto el asunto; C++ creando a C++. Ala! ya teneis un nuevo koan tipo huevo-gallina.
    El resto ya es historia conocida.

    Bjarne Stroustrup
    Bjarne Stroustrup

    Hace 10 años comenzó a circular entre los programadores de C++ una supuesta entrevista suya que nos dejó, estaba claro que tenía que ser una coña pero hasta tal punto llegó la discusión que para confirmarlo y cerrar de una vez el asunto le envié un e-mail y a los 3 minutos justos me responde con:

    Hola,

    Claro, es una broma, y de no muy buen gusto por cierto. Por favor visita siempre mi web personal en donde pongo las entrevistas que me van haciendo.
    (…)

    Ésta es una de las perlas de aquella mítica y falsa entrevista:

    Well, one day, when I was sitting in my office, I thought of this little scheme, which would redress the balance a little. I thought ‘I wonder what would happen, if there were a language so complicated, so difficult to learn, that nobody would ever be able to swamp the market with programmers?’
    Actually, I got some of the ideas from X10, you know, X windows. That was such a bitch of a graphics system, that it only just ran on those Sun 3/60 things. They had all the ingredients for what I wanted. A really ridiculously complex syntax, obscure functions, and pseudo-OO structure. Even now, nobody writes raw X-windows code. Motif is the only way to go if you want to retain your sanity.

    —————————————————–

    Bueno, un día, cuando estaba sentado en mi oficina, pensé sobre este pequeño sistema que compensaría la balanza un poco. Pensé ‘Me pregunto ¿qué pasaría si hubiese un lenguaje tan complicado, tan difícil de aprender, que nadie pudiera saturar el mercado de programadores nunca más?’
    En realidad cogí algunas ideas del X10, ya sabes, el X-windows. Era un sistema gráfico tan cabrón que sólo se podía ejecutar en aquellos Sun 3/60. Tenían todos los ingredientes que quería. Un sistema con una sintaxis tan ridículamente compleja, funciones oscuras, y arquitectura pseudo orientada a objetos. Incluso ahora nadie programa directamente código para X-windows. Utilizar Motif es la única manera si no quieres volverte loco.

    Si nunca habíais oído hablar de esta entrevista y aún no la habeis leído ya va siendo hora… os vais a hartar de reir un buen rato.

    Bueno, vamos al tema, aquí os dejo con una conferencia que dio hace un par de años sobre el futuro nuevo estándar C++0x que reemplazará al actual C++03 (ISO/IEC 14882):

    PD: Como veis estoy cogiendo un vicio insano con los muñequitos amarillos, los alérgicos/as manténganse a distancia prudencial, no me hago responsable de posibles efectos secundarios de una larga exposición a estos bichos amigos de PI…

    Probando…

    February 20th, 2009 admin No comments

    Probando…

    123

    Categories: Uncategorized Tags: