Algoritmo RANDU

RANDU é um algoritmo gerador de números aleatórios que foi muito usado nos mainframes das décadas de 60 e 70. Ele é definido pela fórmula:

Plot (x,y,z) criado no MATLAB usando RANDU para gerar 100002 valores

$V_{j+1}\equiv (65539V_{j})\mod 2^{31}$

com $V_{0}$ ímpar.

Ele é considerado um dos piores algoritmos geradores de números pseudo-aleatórios já criado. Ele falha notavelmente no teste espectral para dimensões maiores que 2.

A razão que levou à escolha destes valores em particular é que os cálculos acima podiam ser feitas rapidamente em computadores que representam os números como valores de 32 bits. Para mostrar o problema que há com estes valores, considere o seguinte cálculo onde cada termo terá seu valor mod $2^{31}$ extraído. Podemos começar a escrever a relação escrevendo:

$x_{k+2}=2^{16}+3x_{k+1}=(2^{16}+3)^{2}x_{k}$

que se torna, após expandir o fator quadrático:

$x_{k+2}=(2^{32}+6\cdot 2^{16}+9)x_{k}=[6\cdot (2^{16}+3)-9]x_{k}$

o que nos permite ver a enorme correlação que existe entre os termos:

$x_{k+2}=6x_{k+1}-9x_{k}$

Por causa desta correlação, pontos gerados aleatoriamente em um espaço tridimensional se concentram em um pequeno número de planos (15). Outro defeito deste algoritmo é que ele gera sempre números ímpares. Por causa do frequente uso do RANDU, muitos resultados de cálculos feitos por computadores na década de 60 e 70 devem ser vistos com cautela.

Exemplos do algoritmo

Em C

 unsigned int _seed;
 
 void inicializa_randu(int i){ /*Inicializa a semente*/
   _seed=i;
 }
 
 int randu(void){
   _seed=(_seed*65539)%(2147483648); /*Cálculo do valor*/
   return _seed;
 }

Referências

• Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd edition (Addison-Wesley, Boston, 1998).
• Press, William H., et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing, 2nd edition. ISBN 0-521-43064-X.