lunes, 15 de agosto de 2011

Generar números aleatorios en C

Usando la función rand() para obtener números aleatorios, la primera vez que lo ejecutas esta bien, pero lo ejecutas nuevamente te mostrara la misma serie de números generados anteriormente. Para solucionar esto usaremos la función srand() para cambiar la variable (semilla) en la que se basa rand() para generar los números aleatorios.
Para obtener números aleatorios eficazmente necesitamos una semilla que varia de un instante a otro, por eso usaremos el comando en ensamblador rdtsc, nos retornará el numero de ciclos del procesador desde el inicio.Esta solución funciona únicamente con procesadores x86.


El siguiente código genera 10 números aleatorios:

#include "stdio.h"
#include "stdlib.h"
#include "stdint.h"

__inline__ uint64_t rdtsc();

int main(int argc, char *argv[]) {

    int i;    
    srand(rdtsc());
    for(i=0; i<10; i++)
    {
         printf("%d\n", (int)(16.0 * (rand() / (RAND_MAX + 1.0))));
    }

  return 0;
}
__inline__ uint64_t rdtsc()
{ 
    uint32_t lo, hi;
    __asm__ __volatile__ ("xorl %%eax,%%eax \n cpuid" ::: "%rax", "%rbx", "%rcx", "%rdx");
    __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
    
   return (uint64_t)hi << 32 | lo;
}
Referencia: http://en.wikipedia.org/wiki/Time_Stamp_Counter#C.2B.2B

6 comentarios:

  1. Hey, algunos comentarios.

    Si compilas con la opción "-Wall" verás algunos warnings que pueden ser utiles. La función rdtsc no retorna ningún valor. Creo que si reemplazas la llamada en ensamblador por algo como "int y = 2;" el programa parecerá funcionar de todos modos. En la Wikipedia hay un ejemplo de como usar esto pero lo probé y no me funcionó, tal vez porque estoy en una máquina de 64 bits ahora.

    Dejando a un lado el ensamblador, algunas notas más:

    1) No es necesario (y creo que tampoco deseable) llamar srand antes de generar cada número. Lo haces al inicio.

    2) Uno cuando quiere algo simple usa algo como: srand(time(NULL)). El problema es que si dos programas comienzan durante el mismo segundo van a tener la misma semilla. A veces la gente le suma o le resta el resultado de getpid() pero eso tampoco es lo mejor para casos que no sean muy simples (y que usen procesos hijos porque al parecer en algunos sistemas se hace cache del getpid).

    3) Cuando necesites números aleatorios para algo serio es mejor usar un generador diferente al del sistema que es bastante malo. Para la mayoría de aplicaciones muy simples debe ser suficiente.

    4) Al usar módulo pierdes un poco de aleatoriedad, por ejemplo "1 + rand() % 14: no es bueno. Es mejor algo como:

    (int)(1.0 + 14.0 * (rand() / (RAND_MAX + 1.0)));

    La razón es que con módulo dejas de usar bits de aleatoriedad de la salida de rand().

    ResponderEliminar
  2. No conocía la opción -Wall es muy útil, ya he modificado algo del codigo. Se que es mas practico usar time(NULL), pero quería mostrar otra forma.La nota #4 también es nueva para mi, la he implementado en el codigo.

    Muchas gracias por tus comentarios, de verdad me ayudan mucho.Espero seguir leyéndolos a menudo.

    ResponderEliminar
  3. De nada. Me alegra ver a la gente usando internet para cosas buenas.

    En todo caso el programa todavía tiene un problema. Creo que funciona por accidente :-)

    Si compilas con optimización de compilador es probable que no funcione. Prueba compilando con -02 por ejemplo. Eso no es del todo malo si sabes que está pasando exactamente, muchos programas que usan ensamblador no pueden ser optimizados por el compilador (y la gente usa -O0 para eso).

    Mira la entrada de la wikipedia para rdtsc, ahí tienen un código más largo que no pude hacer funcionar.

    Si tienes tiempo una forma para mirar exactamente que está pasando es comparar las salidas de ensamblador que genera tu código.

    gcc -Wall -S programa.c -o salida1.asm
    gcc -Wall -O2 -S programa.c -o salida2.asm

    ResponderEliminar
  4. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  5. Lo he modificado, no me había fijado bien en la función (no retorndaba nada), usé como referencia el ejemplo de wikipedia de rdtsc y lo apliqué aquí, devuelve un uint64_t.
    Lo compilé con las indicaciones que me mostraste y no obtuve ningún warning como me pasaba anteriormente.
    ¿Que te parece?, ahora si devuelve el numero correspondiente al contador de ciclos del procesador.

    ResponderEliminar
  6. Se ve que funciona. Si uno imprime el valor retornado por la función ("%Lu") y ejecuta el programa con unos segundos de diferencia se puede verificar que la tasa de cambio por segundo es similar en diferentes corridas.

    Además ahora el programa si funciona igual cuando está optimizado con -O2.

    Si toca hacer algo similar para un programa más portable supongo que es mejor usar clock_gettime como dicen en la Wikipedia. Eso funciona en otros UNIX y además en otros procesadores.

    En todo caso es bueno el ejercicio de usar ensamblador desde GCC. A veces hace falta.

    ResponderEliminar