Função rand/random [RESOLVIDO]

1. Função rand/random [RESOLVIDO]

Samuel Leonardo
SamL

(usa XUbuntu)

Enviado em 09/05/2016 - 00:34h

Estava vendo a doc desses funções (man 3 rand) e vi lá que mostraram como se faz uma função semelhante. Fiquei curioso e pensei: como alguém consegue pensar nisso? Então, queria saber que tipo de estudo foi feito para se chegar à função rand/random. Alguém conhece um material que explique que conhecimento foi usado para se criar tais funções? Mesmo sendo pseudo aleatório o valor gerado, ainda assim acho muito interessante como algo assim funciona e tem tantas aplicações.


  


2. MELHOR RESPOSTA

Paulo
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 “abcdc3po” 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.





Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts