Algoritmo RANDU

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

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:

com í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 extraído. Podemos começar a escrever a relação escrevendo:

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

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

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.