RANDU
Origem: Wikipédia, a enciclopédia livre.
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 V0 ímpar.
Ele é considerado um dos piores algoritmos geradores de números pseudo-aleatórios já criado. Ele falha notavelmentee no teste espectral para dimensões maiores que 2.
A razão que levou à escolha destes valores em particular é que as contas 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 231 extraído. Podemos começar a escrever a relação escrevendo:
- xk + 2 = 216 + 3xk + 1 = (216 + 3)2xk
que se torna, após expandir o fator quadrático:
![x_{k+2}=(2^{32}+6 \cdot2^{16} +9 )x_{k}=[6 \cdot (2^{16}+3)-9]x_{k}](../../../math/1/e/0/1e068b898b48099deda2b78ec4871ed3.png)
o que nos permite ver a enorme correlação que existe entre os termos:
- xk + 2 = 6xk + 1 − 9xk
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 freqüente uso do RANDU, muitos resultados de cálculos feitos por computadores na década de 60 e 70 devem ser vistos com cautela.
[editar] Exemplos do Algoritmo
[editar] 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;
}
[editar] 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.
