Esclarecimento sobre números aleatórios
5 maio 2017, 10:53 • Pedro Tomás
De forma a esclarecer várias questões relativamente à geração de números "pseudo-aleatórios" dá-se o seguinte esclarecimento:
Os algoritmos de geração de números pseudo-aleatórios não geram números verdadeiramente aleatórios. Na verdade não são mais do que processos deterministicos para gerar sequencias de números aparentemente aleatórios (p. ex. considerem uma sequencia como o lançamento repetitivo de um dado). Contudo, a sequencia gerada por este tipo de algoritmos é especial. Em particular, deverá ter um passo de repetição muito longo (i.e., de forma análoga a um "contador", deverá demorar muitas iterações até a sequencia se começar a repetir) e não deverá aparentar ter qualquer padrão (por comparação, novamente no lançamento de um dado, a sequencia de saida não deverá apresentar qualquer padrão, caso contrário estamos na presença de um dado viciado, ou de um processo de lançamento do dado viciado).
Em geral existem muitos algoritmos de geração de números aleatórios, cujo principio é o de uma máquina de estados. Assim, este tipo de algoritmos baseia-se na utilização de uma estrutura de dados para guardar o estado da sequencia (Si-1) após o ultimo número aleatório gerado (Ni-1). De cada vez que a função é chamada, o que o algoritmo faz é actualizar o estado da sequencia (Si-1→Si) e usar este estado para gerar um número aleatório (Si→Ni). Assim, da próxima iteração (i+1) que o algoritmo for corrido, como o estado utilizado é diferente (Si+1≠Si), o número aleatório gerado (Ni+1) é diferente do anterior (Ni). Note-se que com o objectivo de simplificar o enunciado, foi disponibilizado um algoritmo de geração de números aleatórios muito simples, onde o estado Si é igual ao número aleatório Ni (i.e., Si≡Ni). Assim sendo, utiliza-se o número aleatório anterior (Ni-1) para gerar o próximo número aleatório (Ni). No laboratório, define-se assim uma variável em memória (ex: RANDOM_STATE), inicializada com um ponto inicial N0 (seed). De cada vez que for preciso gerar um número aleatório, esta variável RANDOM_STATE deverá ser usada para obter o próximo número aleatório, sendo a mesma variável actualizada de forma a guardar o estado da sequencia. Naturalmente, a rotina de geração de números aleatórios poderá devolver o número aleatório gerado por registo ou pela pilha, ou, em alternativa, pode-se simplesmente ler a variável RANDOM_STATE para obter o último número aleatório gerado.
Naturalmente, e dado que se usa um processo deterministico, a aparente aleatoridade está na geração e desconhecimento do ponto inicial (S0), geralmente denominado de semente (seed). Em sistemas onde existe um relógio com elevada precisão, o que se faz é usar o valor do tempo (ex: nanosegundos) para determinar o ponto inicial da sequencia. Por exemplo, em C, é necessário chamar a rotina srand() para inicializar o algoritmo com a semente, antes da utilização da função de geração de números rand(). Ao utilizar a rotina srand(), obtem-se um valor inicial desconhecido, pelo que a sequencia de números gerada parece aleatória.
No laboratório não existe um relógio de elevada precisão. Contudo, os alunos podem tirar partido do tempo que o utilizador demora a pressionar numa tecla (para começar o jogo) para obter o valor da semente (N0).