paulo1205
(usa Ubuntu)
Enviado em 09/05/2016 - 11:20h
O conhecimento necessário é de Aritmética, o ramo da Matemática voltado ao conhecimento dos números, sistemas de numeração e operações sobre eles. Em particular, se o método de que você está falando for o que consta na manpage de
rand(3), é preciso conhecer Aritmética Modular.
Mas não se esqueça de ler outro pedaço da manpage, na seção de notas, que diz o seguinte, a respeito de
rand().
However, on older rand() implementations, and on current implementations on different systems, the lower-order bits are much less random than the higher-order bits. Do not use this function in applications intended to be portable when good randomness is needed. (Use random(3) instead.)
A afirmação acima traz dois problemas. O mais evidente é que a sugestão de usar
random() limita a portabilidade do programa, uma vez que
random() só é definida no mundo POSIX. Mas o mais grave mesmo é o que está dito sobre a pouca aleatoriedade dos bits de mais baixa ordem, que fica ainda mais perigoso em algumas situações de uso corriqueiramente empregadas no dia-a-dia -- e que refletem justamente a falta de conhecimento sobre Aritmética de quem as utiliza.
Tenho certeza de que você já viu código com o aspecto abaixo, destinado a gerar um número aleatório entre
0 e
N-1.
unsigned var=rand()%N;
Se
rand() tem pouca aleatoriedade nos bits de baixa ordem, para um valor de
N suficientemente pequeno, existe uma grande chance de o período de repetição ser muito pequeno, o que significa que as mesmas sequências podem se repetir com razoável frequência.
De fato, eu mesmo já sofri com isso. Eu tinha feito um programa para geração de senhas aleatórias, usando
srand() e
rand(). Eu achava que tinha sido bastante cuidadoso e engenhoso na proteção contra geração de senhas repetidas, porque eu usava uma conta para a geração da semente inicial com
srand() que usava dados com baixíssima possibilidade de repetição. Até que, um dia, eu o usei para gerar uma senha para um cliente, e a senha gerada era absolutamente igual à minha própria senha (que tinha sido também gerada por ele).
Teria eu ganhado na loteria, ou meu programa estava quebrado? Eu fiz o seguinte teste, várias vezes (em lugar de “mypasswd”, obviamente, estava a senha que eu usava naquela época).
for a in {1..1000}; do ./random_passwd; done | grep mypasswd | wc -l
E o resultado, que deveria ser sempre 0, ora dava 3, ora dava 4; nunca menos de 3. Logo meu programa certamente estava quebrado. Um segundo teste ajudou a clarear isso ainda mais.
for a in {1..1000}; do ./random_passwd; done | sort -u | wc -l
Não lembro do resultado exato, mas era de pouco mais de trezentos, e não 1000, como deveria.
O problema de falta de aleatoriedade nada tinha a ver com a semente inicial. Para qualquer semente, a senha gerada era sempre um elemento de um conjunto finito de trezentas e poucas senhas (e eu nem lembro de ter visto se essas trezentas e poucas não tinham pedaços comuns, como, por exemplo, a senha “
c3por2d2” aparecer fragmentada como parte de duas outras senhas geradas consecutivamente, como “abcd
c3po” e “
r2d2efgh”).
Eu não tenho conhecimento de Aritmética suficiente para fazer uma análise qualitativa detalhada, capaz de provar que aplicar módulo ao valor retornado por
rand() é ruim. Vou me limitar a apenas um caso, tomando como premissa verdadeira a informação, dada pela própria documentação, de que os bits de mais baixa ordem têm pequena aleatoriedade: o uso de módulo será particularmente ruim quando o valor do módulo for uma potência de dois, porque obter o valor modular quando o módulo é uma potência de dois correspondente justamente a descartar sumariamente todos os bits de ordem maior que o igual ao bit dessa potência. Se eu mantenho os bits com pouca variação, e descarto sumariamente os que têm maior variação, então eu terei seguramente um resultado ruim.
No meu caso, eu “corrigi” o programa passando a ler dados de
/dev/urandom. Mas existe uma alternativa mais portável, que é a de transferir a aleatoriedade, supostamente boa (ou pelo menos melhor), dos bits de mais alta ordem para as ordens mais baixas. Isso se faz trocando o código mostrado acima pelo seguinte.
unsigned var=(double)rand()/(double)(RAND_MAX+1)*(double)N;
Obviamente, as conversões para
double e, depois, de volta para inteiro introduzem algum custo, se comparadas a operações exclusivamente sobre inteiros, mas esse custo, dependendo da aplicação, possivelmente é menor que o prejuízo de ter dados com baixíssima aleatoriedade.
