Representación interna de un flotante

En este post vamos a hacer un pequeño experimento para desplegar la representación de un flotante, ya que a final de cuentas debe ser guardado como un conjunto de bits.

Primero, repasemos rápidamente uniones en C. En una unión todos sus miembros comparten la misma ubicación de memoria. Por ejemplo, en el siguiente programa, la unión contiene dos elementos, una estructura con cuatro enteros y un arreglo de cuatro enteros. Observen como inicializamos los valores de la estructura y posteriormente desplegamos esos valores usando los miembros del arreglo.

#include <stdio.h>

typedef struct {
  int byte1;
  int byte2;
  int byte3;
  int byte4;
} Mi_estructura;

typedef union {
  Mi_estructura estructura;
  int arreglo[4];
} Mi_union;

void main(void) {
  Mi_union u;
  int i;
  
  u.estructura.byte1 = 11;
  u.estructura.byte2 = 22;
  u.estructura.byte3 = 33;
  u.estructura.byte4 = 44;
  
  for(i = 0; i < 4; i++) {
    printf("%d\n",u.arreglo[i]);
  }
}

Este caso en específico puede ser útil cuando algunas partes del programa son más legibles usando los miembros de la estructura, por ejemplo al momento de asignar valores. Y otras veces es más eficiente usar un arreglo, como al querer copiar o desplegar los elementos.

Regresando al caso de un flotante. Usaremos una unión que contiene un float y un int, en la máquina que estoy usando ambos usan 4 bytes. Lo que haremos es modificar la unión usando el float y desplegar el contenido usando el int.

#include <stdio.h>

typedef union {
  int i;
  float f;
} Mi_union;

void main(void) {
  Mi_union u;
  printf("# bytes int: %zu\n",sizeof(int));
  printf("# bytes float: %zu\n",sizeof(float));
  
  u.f = 1234.5678f;
  printf("%.10f\n",u.f);
  printf("0x%x\n",u.i);
}

Podemos ver en la imagen anterior que el valor 1234.5678f es almacenado con el siguiente patrón de bits 0x449a522b. Este patrón sigue el estándar IEEE754, la siguiente página contiene una muy buena explicación.

Lo que haremos es extraer los bits de acuerdo a este formato y verificaremos que tengamos el valor 1234.5678f.

#include <stdio.h>

typedef union {
  unsigned int i;
  float f;
} Mi_union;

unsigned int extraer_bits(unsigned int valor, short inicio, 
                          short nbits);
void representacion_float(unsigned int valor);

void main(void) {
  Mi_union u;
  printf("# bytes int: %zu\n",sizeof(int));
  printf("# bytes float: %zu\n",sizeof(float));
  
  u.f = 1234.5678f;
  printf("%.10f\n",u.f);
  printf("0x%x\n",u.i);
  representacion_float(u.i);
}


void representacion_float(unsigned int valor){
  unsigned int signo = 0;
  unsigned int exponente_bias = 0;
  unsigned int exponente_unbias = 0;
  unsigned int mantisa = 0;
  unsigned int parte_entera = 0;
  unsigned int parte_decimal = 0;
  unsigned int parte_decimal_max = 0;
  
  signo = extraer_bits(valor, 31, 1);
  exponente_bias = extraer_bits(valor, 23, 8);
  exponente_unbias = exponente_bias - 127;
  mantisa = extraer_bits(valor, 0, 23);
  parte_decimal = extraer_bits(valor,0,23-exponente_unbias);
  parte_decimal_max = 1<<23-exponente_unbias;
  parte_entera = extraer_bits(valor,23-exponente_unbias,
                              exponente_unbias);
  // la parte entera tiene un bit 1 por default al inicio.
  parte_entera |= 1<<exponente_unbias;
  
  printf("Signo: %d\n", signo);
  printf("Exponente (bias): 0x%x (%d)\n", exponente_bias, 
                                          exponente_bias);
  printf("Exponente (unbias): %d\n", exponente_unbias);
  printf("Mantisa: 0x%x\n", mantisa);
  printf("Parte entera: 0x%x (%d)\n", parte_entera, 
                                      parte_entera);
  printf("Parte fraccional: 0x%x (%d) de 0x%x (%d)\n", 
    parte_decimal, parte_decimal, 
    parte_decimal_max, parte_decimal_max);
}


unsigned int extraer_bits(unsigned int valor, short inicio, 
                 short nbits){
  unsigned int mascara = 0;
  short i = 0;
  // primero recorremos el bit inicial al bit 0
  valor >>= inicio;
  // obtener mascara de los bits que deseamos
  for(i = 0; i < nbits; i++){
    mascara <<= 1;
    mascara |= 1;
  }
  // enmascaramos los bits que deseamos
  return valor & mascara;
}

Noten que el código no es muy robusto, ya que para números muy grandes (es decir, exponentes muy grandes) no funciona. Pero ayuda a ilustrar la representación de un flotante.

El programa obtiene los bits correspondientes al signo, el exponente y la mantisa. Además usa el exponente para extraer de la mantisa la parte entera y fraccionaria. La parte fraccionaria la podemos interpretar ya sea viendo los bit y calculando el valor. Por ejemplo, 0x122b en binario es 1 0010 0010 1011, lo cual lo podemos evaluar como 2^−1+2^−4+2^−8+2^−10+2^−12+2^−13 = 0.567749023. Otra forma de verlo, es que el máximo valor de la parte fraccionaria más uno es 0x2000 ó 8192 decimal (es decir esto equivale al valor 1). Por lo que nuestra parte fraccionaria es 4651/8192=0.567749023. Noten, que el valor que obtuvimos es ligeramente menor al valor inicial, esto es a lo que llamamos errores de precisión.

Espero que les haya resultado interesante ver de una forma práctica como guardamos número flotantes.

Reiniciar peticiones de tweets

Tutorial de Grafos
Anterior        Índice        Siguiente

En este post volveremos a visitar el programa que obtiene la información de los hash tags. Agregué dos nuevas funcionalidades.

La primera mejora tiene que ver con qué pasa si queremos volver a ejecutar búsquedas y guárdalas en la misma carpeta de tweets de una ejecución anterior. Sin ninguna modificación al programa, lo que pasaría es que los nuevos archivos de salida se agregan sin problema aún cuando volvamos a visitar un mismo hash tag, ya que el nombre del archivo esta formado por un “timestamp” y el hash tag (por ejemplo: 1351987950#felicidad). Y tal vez ese sea un comportamiento deseado.

Sin embargo, decidí modificar el programa para evitar visitar hash tags que hayan sido visitados en ejecuciones anteriores. Esto es muy sencillo, ya que el nombre del archivo contiene el hash tag, por lo que sólo tuve que extraerlos y agregarlos al conjunto de hash tags visitados.

Un efecto secundario de este cambio es cuando nuestro hash tag inicial ya lo habíamos visitado anteriormente, el resultado es que el programa termina inmediatamente. Esto nos lleva a el segundo cambio, inicializar automáticamente la búsqueda cuando pasemos “##” como hash tag inicial en la línea de comandos.

En caso de que hayamos ejecutado el programa previamente, entonces tendremos un conjunto de archivos de los hash tags visitados. Los hash tags dentro de los archivos no necesariamente han sido visitados, por lo que inicializaré los hash tags a visitar con todos aquellos hash tags que no se visitaron en ejecuciones anteriores. El siguiente comando visitará otros 2,000 hash tags, tomando como base la información en "../tweets" de los hash tags visitados anteriormente.

python twitter_search.py "##" 100 5 2000 ../tweets

El código lo pueden encontrar en la siguiente liga.

Creo que por el momento el programa de extracción de datos está bastante completo, en el siguiente post veremos cómo construir nuestro grafo de hash tags con esta información.

Tutorial de Grafos
Anterior        Índice        Siguiente