Geradores de números pseudo-aleatórios

Se você já precisou de valores aleatórios em seus códigos, já deve ter usado as funções srand() e rand() que constam no header stdlib.h, da libc… A função rand() tem um problema: Embora devolva um valor do tipo int, ela costuma retornar valores com 31 bits de tamanho apenas (o que faz sentido, já que int é um tipo sinalizado). Mas, pode ser que você precise de um valor unsigned int e, com rand() não dá para fazer!

A biblioteca libc especifica que o valor retornado por rand() deverá estar no intervalo fechado entre zero e RAND_MAX, onde o limite superior não é definido por especificação, mas basta dar uma olhada em stdlib.h para ver que é definido como 0x7fffffff. Já encontrei versões da glibc que implementam RAND_MAX com 15 bits, mesmo numa arquitetura de 32!

A solução é implementar nosso próprio gerador pseudo-aleatório por congruência linear. Ei-lo:

/* "Semente" default. */
static unsigned long _seed = 0xbabacadeadbeefUL;

/* Ajusta a "semente". */
void SRAND(unsigned long seed) { _seed = seed; }

/* Obtém o próximo valor. */
unsigned int RAND(void)
{ return (_seed = 0x41c64e6dUL * _seed + 12345UL) >> 32; }

Esse LCG (Linear Congruential Generator) usa valores de 64 bits, internamente, mas devolve apenas 32… Usar 64 bits não é problema, especialmente no modo x86-64. Mas essa rotina tem um problema: Ela faz uma multiplicação e uma adição inteiras. Multiplicações são especialmente lentas e, para complicar as coisas, um LCG é bastante dependente dos valores escolhidos para a função RAND().

Eis outro gerador mais interessante, que usa apenas operações lógicas XOR e adições: Chama-se xorshift128+:

/* Existem 2 seeds defaults aqui ou
   um único seed de 128 bits! */
static unsigned long s[2] = { 0x748bd5a53132bUL,
                              0x41c6e6d32143a1c7UL };

/* Só precisamos ajustar s[0]!
   O ideal seria ajustar os dois! */
void XSP_SRAND(unsigned long seed)
{ s[0] = seed; }

/* Faz a mágica aqui! */
unsigned long XSP_RAND(void)
{
  unsigned long s0 = s[1];
  unsigned long s1 = s[0];

  s[0] = s0;
  s1 ^= s1 << 23;
  s[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26);

  return s[1] + s0;
}

A rotina XSP_RAND() só realiza XORs, SHIFTS e uma adição final. E isso a faz, potencialmente, mais rápida… Minha medição mostra que a função rand() gasta uns 1800 ciclos e as outras duas, acima, uns 50.

XSP_RAND() tem lá suas vantagens: Ela trabalha com 128 bits (a “random seed” são dois unsigned long) e devolve um valor de 64 bits, onde a “faixa” dos valores aleatórios está realmente entre zero e 2^{64}-1, inclusive. Para obter um valor de 32 bits, tudo o que temos que fazer é pegar a parte superior (assim como fiz com RAND()).

Outra vantagem é que o algoritmo xorshift128+ é um pouco melhor que o LCG com relação à distribuição dos valores. Isso não é óbvio, de acordo com os mapas de distribuição de 100 mil amostras, com a mesma “semente”, das três rotinas, mostrado abaixo:

prng2

Essas não são imagens “pixeladas”! Esses mapas foram gerados por um programinha que fiz que preenche uma área de 512×512 com um fundo branco e apaga um pixel (preenche com zero ou “preto”) para cada ocorrência de um valor, escalonado-o para caber um array de 262144 posições.

Os gráficos mostram que, pelo menos, o algoritmo xorshift128+ é tão bom quanto rand(). Mas, como eu disse, ele gera valores em faixa maior, tem dispersão ligeiramente melhor e é mais rápido!

Deixe um comentário