Números quase aleatórios e uma lição aprendida…

Você já teve que usar o conceito de “aleatório” em um de seus códigos? Já usou o par de funções srand() e rand(), disponíveis em stdlib.h? O que vou descrever abaixo foram lições aprendidas sobre o funcionamento dessas rotinas. Esses conhecimentos foram obtidos de 2 fontes: The Art of Computer Programming (TAOCP, para simplificar) de Donald E. Knuth, capítulo 3 do 2º volume (Seminumerical Algorithms). A outra lição foi aprendida graças ao um projeto muito interessante (aqui) – o autor me apontou um fato interessante (que Knuth também aponta) sobre a “aleatoriedade” dos números aleatórios!

Eis um método de gerar UM número aleatório!

Não existe tal coisa como UM número aleatório e a piada acima demonstra isso. Quando falamos de números (plural) aleatórios estamos falando de um conjunto de números cuja distribuição é, em teoria, imprevisível. Ou seja, não há como saber qual será o próximo número a partir dos anteriores obtidos…

Isso, infelizmente, é muito difícil de fazer num ambiente determinístico. Tudo o que podemos fazer é aceitar algum grau de previsibilidade, “fazendo de conta” que os resultados obtidos são aleatórios. É o que acontece com as funções srand() e rand(), da biblioteca padrão de C. Essas funções usam o que se conhece, na matemática, por congruência linear:

Xnovo = (A·Xvelho + C) % M

Cada vez que você chama rand(), a equação acima é avaliada e você obtém um valor Xnovo que parece ser aleatório. Os valores de A, C e M são cuidadosamente escolhidos pelo desenvolvedor do compilador para que diversas chamadas à função não gerem números parecidos (de novo, parecendo aleatórios).

A função srand(), que fornece uma “semente” (seed) para rand(), apenas ajusta o valor de Xvelho inciial. É interessante obter essa semente de algum lugar que não seja muito previsível. Uma semente razoável pode ser obtida assim:

void seedPRNG(void)
{
  struct timeval tv;

  gettimeofday(&tv, NULL);
  srand((unsigned int)tv.tv_usec);
}

PRNG é a sigla para Pseudo Random Number Generator. Ênfase em “pseudo“!

O autor do projeto que citei lá no início me indicou um fato interessante: A geração de números “aleatórios” através do método da congruência linear tende a gerar números onde os primeiros bits não são tão aleatórios assim. No TAOCP, Knuth nos mostra a prova matemática disso. No projeto citado a solução para esse problema foi escalonar (no sentido de “mudar a escala”) o número obtido por rand():

#define __RND(max) \
  (uint32_t)( (double)(max) * ((double)rand() / ((double)RAND_MAX + 1.0)) )

Que é uma solução interessante, porém, na minha opinião, tem dois problemas:

a) O valor devolvido por rand() é definido como um inteiro entre 0 e RAND_MAX. E, sabendo que RAND_MAX é definido como um (231 – 1), o escalonamento jamais resultará num valor entre 0 e 1. Se rand() devolver seu valor máximo, teremos algo como ((max) * (1 – 2-31)) que, de forma alguma será igual ao valor de max, já que conversão de double para int simplesmente extirpa a parte fracionária. Quer dizer. o macro acima devolve um valor x, onde 0 ≤ x < max. É claro que podemos adicionar 1 ao resultado, mas ai o valor zero jamais será obtido.

Uma solução para esse problema é modificar o escalonamento:

#define __RND(max) \
  (uint32_t) ((double)(max) * ((double)rand() / (double)RAND_MAX))

Mas, pode ser que voltemos ao problema original da baixa “aleatoriedade”. Essa modificação vale um estudo…

b) Em minha opinião, usar ponto-flutuante para ignorar bits inferiores é um exagero. Suponha que queiramos obter um inteiro de 8 bits que seja “aleatório”. As duas soluções abaixo retornam “quase” o mesmo resultado:

/* Adicinado 1.0 porque essa é a implementação no t50 */
#define __8BITS_RND_fp() \
  (uint8_t)(1.0 + (255.0 * ( (double)rand() / ((double)RAND_MAX + 1.0) )))
#define __8BITS_RND_sh() \
  (uint8_t)(( rand() >> 23 ) & 0xff )

A primeira função jamais retornará zero. A segunda, por sua vez, usa a faixa toda ([0,255]) e com a vantagem de não usar aritmética de ponto-flutuante. O motivo pelo shift de 23 bits (ao invés de 24) é que RAND_MAX sempre terá seu bit 31 igual a 0 (o que não é nada aleatório, né?). Então estou deslocando 31 bits menos os 8 que eu quero.

De fato, dando uma olhada no código gerado pelas duas rotinas, compilados com máxima otimização do compilador com alvo para a arquitetura Core2 Duo:

; 8BITS_RND_sh 
call rand
sar eax,23      ; Essas duas instruções executam em 2 ciclos de máquina.
and eax,0xff

Enquanto a rotina usando ponto flutuante:

; __8BIT_RND_fp
call  rand
mov DWORD PTR [esp+4], OFFSET FLAT:.LC3
mov DWORD PTR [esp+28], eax
fnstcw  WORD PTR [esp+26]
fild  DWORD PTR [esp+28]              ; [esp+28] = x
movzx eax, WORD PTR [esp+26]
fmul  DWORD PTR .LC0                  ; .LC0 = 255.0
mov ah, 12
fmul  DWORD PTR .LC1                  ; .LC1 = 1/(RAND_MAX+1)
mov WORD PTR [esp+24], ax
fadd  DWORD PTR .LC2                  ; .LC2 = 1.0
mov DWORD PTR [esp], 1
fldcw WORD PTR [esp+24]
fistp QWORD PTR [esp+16]              ; o resultado!
fldcw WORD PTR [esp+26]

Como indiquei no “forum” do projeto, usar SSE também não melhora muita coisa:

call  rand
movapd  xmm2, XMMWORD PTR .LC3
cvtsi2sd  xmm0, eax
movapd  xmm3, xmm2
mulsd xmm0, QWORD PTR .LC0
mov DWORD PTR [esp+4], OFFSET FLAT:.LC4
mulsd xmm0, QWORD PTR .LC1
mov DWORD PTR [esp], 1
addsd xmm0, QWORD PTR .LC2
xorpd xmm1, xmm1
movsd xmm1, xmm0
cmplepd xmm2, xmm1
andpd xmm3, xmm2
pslld xmm2, 31
subpd xmm1, xmm3
cvttpd2dq xmm1, xmm1
pxor  xmm1, xmm2
movd  eax, xmm1     ; EAX conterá o resultado final.

Usar SSE evita o uso da pilha do “coprocessador” que, em teoria, acelera um pouco as rotinas em ponto-flutuante. No entanto, nesse caso, a rotina em SSE é tão ruim quanto a equivalente, usando o “coprocesador”.

Conclusão:

Fica claro para qualquer um que a rotina em ponto-flutuante é mais lenta, não retorna valores em toda a faixa desejada e ainda é bem maior que a equivalente, usando um shift e um and

Um dos melhores métodos de geração de números aleatórios! ;)

Mesmo assim, estamos à mercê do gerador por congruência linear. Existem alternativas algébricas melhores?

Dê uma olhada no algoritmo Mersenne Twister. Ainda é determinístico, é claro, mas passa em diversos testes de “aleatoriedade” que o método acima não passa…

Anúncios

4 comentários sobre “Números quase aleatórios e uma lição aprendida…

  1. Sempre me perguntei porque não existe (se existe eu não conheço) um circuito analógico, com um gerador de sinais analógicos com um conversor ad na outra ponta. Se existisse um, seria só ler a semente na janelinha de um latch e alimentar um registro, RRand qq no processador.
    Será que a implementação disto seria tão complexa, lenta, fraudável…

    1. Existir, existe… só que existem alguns problemas. Por exemplo: No caso de defeito do circuito, a detecção seria muito difícil (como determinar se a “aleatoriedade” não é mais tão aleatória, por caus de um defeito?)… Knuth cita alguns casos, um deles hilário, de um circuito que lê a flutuação de corrente num diodo aquecido somado a uma música de rap (“white and black noise”).
      A Intel tem um chipset para esse propósito e já li, em algum lugar, que ela pretende incorporar essa funcionalidade em seus processadores (afinal, todo processador, hoje em dia, tem detecção de calor incorporado, para o caso do “cooler” falhar!)…

      Soluções em hardware existem, mas, primariamente, não são implementadas pelo motivo que citei acima. Assim, resta-nos os métodos determinísticos, algébricos, os chamados pseudo random numbers generators.

      1. Eu imaginei – quando disse fraudável – este cenário.
        Mas, pense, um software problemático também pode levar ao mesmo ponto. Assim, supondo que “mexamos” na unidade geradora – num cenário hipotético onde não exista checksums de código – o “defeito” poderia levar ao mesma situação “desapercebida”. Toda solução leva a um novo problema…
        O que pensei é que em vez de se ficar lutando com algorítimos, ter um circuito detector de “raios cósmicos”, “ruido de fundo”, oscilação de pulsares, etc, dada as facilidades tecnológicas atuais, fosse mais interessante do que ficar “jogando dados”. E pelo jeito, a intel, como vc citou, deve estar providenciando isto. E me parece bem lógico que assim deva ser.
        Thx pelo esclarecimento.

      2. Ao que parece, os chipsets da Intel já possuem esse recurso… Os devices /dev/random e /dev/urandom parecem usar esse chipset… Estou pesquisando…. Qdo tiver algo mais palpável sobre isso, posto por aqui…

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s