Geradores de números pseudo-aleatórios

O gerador de números pseudo-aleatórios mais usado no universo digital é o famoso método da congruencia linear, descrito no livro Numerical Recipes e adotado em diversas linguagens (dentre elas C, Delphi etc). Isso se deve, é claro, a sua imensa simplicidade de implementação:


X[n+1] = (a * X[n] + c) mod m
Onde:
a = 1664525
c = 1013904223
m = 2^32


Porém, tal gerador é comprovadamente ineficiente para criptografia ou simulações estatísticas, notadamente quando se precisa aplicar o método de Monte Carlo.

Existem diversos geradores disponíveis no mercado, dentre eles destaca-se o Mersenne Twister. Porém, embora globalmente aceito como o de melhor custo computacional versus beneficio estatístico disponível atualmente, é bastante complicado de se implementar para a maioria dos pobres mortais.

Uma alternativa interessante que descobri alguns anos atrás é um automato celular chamado pelo seu descobridor (Stephen Wolfram) como Regra 30.

Wolfram fez um verdadeiro estudo sobre esse automato, mas especificamente sobre a capacidade de ser usado como um gerador de bits pseudo-aleatórios, passando por diversos testes estatísticos.

O matemático propõe o algorítmo, inclusive, como fortemente apto a ser utilizado em criptografia.

Controvérsias a parte, a verdade é que a teoria por trás da Regra 30 é bastante simples. O algoritmo consiste em aplicar algumas operações lógicas entre os bits do número processado (algo muito parecido ao método LFSR), tal como a seguir:


bit[n]´ = bit[n-1] xor (bit[n] or bit[n+1])


Podemos implementar facilmente tal algoritmo em linguagem C usando três inteiros representando os bits envolvidos no método, e um quarto que guardará o resultado da operação aplicado a todos os bits, como a seguir:


int rule30rnd() {
static unsigned int a = 0x00FF00FF; // bit[n-1]
static unsigned int b = 0x9ABCDEF0; // bit[n]
static unsigned int c = 0xFF00FF00; // bit[n+1]
unsigned int d;
d = a ^ (b | c);
a = (d >> 1) | (d << 31); // bit[n-1] = result rotate right
b = d; // bit[n] = result bits
c = (d << 1) | (d >> 31); // bit[n+1] = result rotate left
return d;
}


No código acima tratamos o problema das bordas – comum nos automatos estudados pelo Wolfram, que teoricamente crescem infinitamente para os lados, mas fisicamente são limitados por uma memória finita – com rotações nos dois inteiros (bit[n-1] e bit[n+1]).

Para modificar a semente de geração, basta alterar o valor de qualquer um dos três inteiros principais.

É importante notar, porém, que a qualidade de geração é bastante influenciada pelos valores inteiros escolhidos como iniciais.

Nesse contexto, Wolfram propõe a escolha de valores que sejam o mais aleatórios possíveis como semente, além de sempre fazer alguns ciclos de geração (de tamanho variável, descartando o resultado) no inicio do programa, antes de utilizar de fato os valores gerados.