segunda-feira, 5 de maio de 2014

Número aleatório por xor-shift

Apresento a sub-rotina de geração de número pseudoaleatório que foi usada na minha parte do demo Mission Highly Improbable


Anteriormente mostrei a sub-rotina de Phantom Club para a mesma finalidade, porém a qualidade da sequência gerada não é das melhores.

Uma sequência de números aleatórios não deveria ser previsível nem repetitiva. Números pseudoaleatórios são geradas por aplicações de operações matemáticas e, apesar de aparentemente um valor gerando não ter relação com o anterior, a sequência tende a se repetir depois de um certo período. Tais geradores são também determinísticos, isto é, a sequência de números é reprodutível.

O gerador de números pseudoaleatórios que usei no demo foi elaborada por Patrik Rak:

rnd     ld  hl,0xA280   ; yw -> zt
        ld  de,0xC0DE   ; xz -> yw
        ld  (rnd+4),hl  ; x = y, z = w
        ld  a,l         ; w = w ^ ( w << 3 )
        add a,a
        add a,a
        add a,a
        xor l
        ld  l,a
        ld  a,d         ; t = x ^ (x << 1)
        add a,a
        xor d
        ld  h,a
        rra             ; t = t ^ (t >> 1) ^ w
        xor h
        xor l
        ld  h,e         ; y = z
        ld  l,a         ; w = t
        ld  (rnd+1),hl
        ret

Um valor pseudoaleatório de 8 bits é retornado no registrador A ou L. Seu algoritmo é baseado em operações xor-shift com semente de 32 bits, de forma que a sequência passa a se repetir após um período de 232−1 vezes. O resultado é até melhor que a função RND do BASIC. Outro ponto favorável é que o código é curto e de execução bastante rápida. Mais detalhes técnicos desta algoritmo pode ser encontrado aqui.

O arquivo fonte contendo o assembly acima pode ser baixado aqui.

7 comentários:

  1. Tô achando estranho esse código. Teoricamente, guarda-se estado em rnd+1, rnd+2, rnd+4 e rnd+5. Mas a cada chamada da função, jogam-se constantes em rnd+4 e rnd+5. Alem disso, o registrador E recebe 0xDE na segunda linha, não é mais alterado e no final, via registrador H, é jogado em rnd+2. Ou seja, só sobram 8 bits de estado verdadeiro.

    ResponderExcluir
    Respostas
    1. O código está bastante otimizado e portanto difícil de ler, ainda mais por ser auto-modificável.

      Mas de fato são 32 bits de estado. No início, o registrador E contém a variável z que logo em seguida é sobreposta pelo registrador L (variável w, o número aleatório anterior). Ao fim, o valor de E é passado para registrador H (variável y) e, na próxima execução, H sobrepõe o registrador D (variável x). As variáveis x, w e t estão diretamente ligadas no cálculo do número aleatório e assim, o 32 bits estão interligados entre si.

      Mas o melhor é ver o respectivo thread do Word of Spectrum.

      Excluir
  2. Muito interessante esse tópico, essa é uma questão que me intriga a muito tempo: a impossibilidade de gerar um número verdadeiramente aleatório em microcomputadores. Imagino que este problema possa ser facilmente resolvido já a partir do surgimento dos primeiros micros de 16 bits com sensores de leitura de tensão e temperatura incorporados às motherboards, já que estes sensores permitem a entrada de leituras analógicas e instantaneas de eventos exteriores e aleatórios imprevisíveis e verdadeiramente aleatórios (digitos menos significativos das leituras de temperatura e tensão) para a partir daí gerar algum número verdadeiramente aleatório já que estes valores derivariam de leituras analógicas que em tese são totalmente aleatórias, mas por outro lado teria-se o problema de que o código teria de ser feito exclusivamente para cada modelo de bios de cada fabricante de motherboards (Asus, Rockstar, etc.). Já no ZX Spectrum/TK90X imagino que um modo de gerar um número genuinamente randômico seria através da de algum algorítimo baseado na leitura instantânea da porta K7, desde que houvesse alguma fonte de áudio alimentando continuamente esta porta, como por exemplo um fita k7 com software ou mesmo música. Claro que na prática a geração de números pseudo-randômicos acaba sendo bastante eficiente com o uso de algorítimos engenhosos como este que você abordou mas em todo caso seria interessante conhecer um método de geração de número verdadeiramente aleatórios e portanto imprevisíveis , diferente do que ocorre com a função RND que, até pode gerar grandes intervalos sem repetição de algum número mas quase sempre com as mesmas "figurinhas carimbadas" se alternando em cada série numérica. Será que "viajei demais na maionese"?? rsrsr
    Abraços,
    Jaime

    ResponderExcluir
    Respostas
    1. Não sei até que ponto grandezas físicas como temperatura e tensão são aleatórias, especialmente em condições reais de operação. Temo que haja um grande bias nos valores obtidos desta forma. Eventos realmente aleatórios em nível de microeletrônica (não macroscópico como dados ou moedas) teriam como base a Mecânica Quântica, no assim chamado efeito túnel (exemplos: corrente de fuga em diodo inversamente polarizado, decaimento radioativo de núcleo atômicos). Mesmo assim, qualquer perturbação introduzido pelo equipamento poderia tendenciar os resultados. Temo que dispositivos realmente randômicos seriam proibitivos.

      Já os algoritmos pseudoaleatórios seria um bom compromisso entre baixo custo e razoável grau de aleatoridade.

      Excluir
  3. Pesquisando mais sobre o tema tomei conhecimento que em algumas linguagens disponíveis para microprocessadores da família x86 a função RND ou RAND busca a semente na leitura instantânea de algum dígito menos significativo do CLOCK da máquina. acredito que esta técnica poderia também ser utilizada nos microcomputadores baseados no Z80 para se conseguir números randômicos ao invés dos pseudo-randômicos, o que acham disso?
    Jaime

    ResponderExcluir
    Respostas
    1. Como respondi acima, mesmo o uso do clock não quer dizer que os valores sejam realmente aleatórios, isto é, não previsível por funções matemáticas.

      No caso do Z80, o registrador R tem comportamento semelhante, porém bastante limitado por ter somente 7 bits. A instrução RAND ou RANDOMIZE do TK/Spectrum usa o número de interrupções deste o último reset como semente.

      Excluir
  4. Mais uma vez agradeço as explicações, só posso agradecer e elogiar a sua disposição em compartilhar seu conhecimento com os outros! É muito bom trocar informações com pessoas que entendem realmente de uma área, como é o seu caso; como eu disse esta questão dos números pseudo-aleatórios me intriga há alguns anos e, certa vez comentei com uma professora universitária (acho que ela era formada em ciências da computação ou matemática computacional) essa questão de computadores não poderem gerar números verdadeiramente aleatórios e ela me olhou com uma cara de espanto, entregando que não sabia deste fato.....rsrs...fiquei até desconcertado por ela e não insisti no assunto....rsrsrs
    Por isto eu agradeço a valiosa aula sobre o tema que gentilmente você proporcionou não só a mim mas a todos que tinham dúvidas sobre este tema!
    grande abraço!
    Jaime

    ResponderExcluir

Seu comentário é bem vindo, mas peço que use este espaço adequadamente.