gerador pseudo-aleatórios em linguagem assembly

StackOverflow https://stackoverflow.com/questions/90184

  •  01-07-2019
  •  | 
  •  

Pergunta

Eu preciso de um algoritmo gerador de números pseudo-aleatórios para um programa assembler atribuído em um curso, e eu preferiria um algoritmo simples. No entanto, eu não posso usar uma biblioteca externa.

O que é uma boa, simples pseudo algoritmo gerador de números para a montagem?

Foi útil?

Solução

Fácil é escolher apenas dois primos relativos grandes a e b, em seguida, manter multiplicando o número aleatório por um e adicionando b. Use o operador módulo para manter os bits baixos como seu número aleatório e manter o valor integral para a próxima iteração.

Este algoritmo é conhecido como o linear congruente gerador .

Outras dicas

Volume 2 de The Art of Computer Programming tem um monte de informações sobre pseudo geração de números . Os algoritmos são demonstrados em assembler, para que você possa ver por si mesmo que são mais simples em assembler.

Se você pode conectar-se a uma biblioteca ou um objeto arquivo externo, porém, que seria a sua melhor aposta. Então você pode conectar-se a, por exemplo, Mersenne Twister .

Note que geradores de números mais pseudo-aleatórios são não seguro para criptografia, por isso, se você precisa garantir geração de números aleatórios, você precisa olhar para além dos algoritmos básicos (e provavelmente deve tocar em APIs de criptografia específicas-OS ).

código simples para o teste, não use com Crypto

A partir de Teste de Software Computer, página 138

Com é de 32 bits de matemática, você não precisa a operação MOD 2^32 

RNG = (69069*RNG + 69069) MOD 2^32

Bem - Desde que eu não tenha visto uma referência para o bom e velho deslocamento linear feedback Register eu postar algumas SSE intrínseco baseado C-Code. Apenas para completenes. Eu escrevi essa coisa de um par de meses atrás, para aguçar meus SSE-habilidades novamente. 

#include <emmintrin.h>

static __m128i LFSR;

void InitRandom (int Seed)
{
  LFSR = _mm_cvtsi32_si128 (Seed);
}

int GetRandom (int NumBits)
{
  __m128i seed = LFSR;
  __m128i one  = _mm_cvtsi32_si128(1);
  __m128i mask; 
  int i;

  for (i=0; i<NumBits; i++)
  {

    // generate xor of adjecting bits
    __m128i temp = _mm_xor_si128(seed, _mm_srli_epi64(seed,1));

    // generate xor of feedback bits 5,6 and 62,61
    __m128i NewBit = _mm_xor_si128( _mm_srli_epi64(temp,5),
                                    _mm_srli_epi64(temp,61));

    // Mask out single bit: 
    NewBit = _mm_and_si128 (NewBit, one);

    // Shift & insert new result bit:
    seed = _mm_or_si128 (NewBit, _mm_add_epi64 (seed,seed));
  }

  // Write back seed...
  LFSR = seed;

  // generate mask of NumBit ones.
  mask = _mm_srli_epi64 (_mm_cmpeq_epi8(seed, seed), 64-NumBits);

  // return random number:
  return _mm_cvtsi128_si32 (_mm_and_si128(seed,mask));
}

Traduzindo este código assembler é trivial. Basta substituir os intrínsecos com as instruções reais SSE e adicionar um loop em torno dele.

Aliás - a sequência de código esta genreates repete após 4.61169E + 18 números. Isso é muito mais do que você vai obter através do método principal e 32 bits aritmética. Se desenrolou é mais rápido também.

@jjrv
O que você está descrevendo é na verdade um gerador congrential linear. Os bits mais aleatórios são os bits mais altos. Para obter um número de 0..n-1 você multiplicar o valor total por N (32 bits por 32 bits, dando 64 bits) e usar as altas de 32 bits.

Você não deve apenas usar qualquer número de a (o multiplicador para progredindo de um valor total para o próximo), os números recomendado em Knuth (Tabela 1 secção 3.3.4 TAOCP vol 2 1981) são 1812433253 , 1566083941, 69069 e 1664525.

Você pode simplesmente escolher qualquer número ímpar de b . (Adição).

Por que não usar uma biblioteca externa ??? Que a roda foi inventada algumas centenas de vezes, então por que fazê-lo novamente?

Se você precisa implementar uma RNG mesmo, que você precisa para produzir números sobre a demanda - ou seja, você está implementando uma função rand () - ou que você precisa para produzir fluxos de números aleatórios - por exemplo, para testes de memória?

Você precisa de uma RNG que é cripto-força? Quanto tempo é que tem que percorrer antes que se repete? Você tem que absolutamente, positivamente garantir uma distribuição uniforme de todos os bits?

Aqui está truque simples que eu usei há vários anos. Eu estava trabalhando em incorporado e eu precisava RAM teste em power-up e eu queria código realmente pequeno, rápido e muito pouca estado, e eu fiz isso:

  • Comece com uma constante de 4 bytes arbitrário para a sua semente.
  • Calcule o CRC dos 4 bytes de 32 bits. Isso dá-lhe os próximos 4 bytes
  • Alimente volta esses 4 bytes para o algoritmo de CRC32, como se tivessem sido anexado. O CRC32 desses 8 bytes é o valor seguinte.
  • Repita o tempo que você quiser.

Isso leva muito pouco código (embora você precisa de uma tabela para a função crc32) e tem muito pouco estado, mas o fluxo de saída psuedorandom tem um tempo de ciclo muito longo antes de repetir. Além disso, ele não requer SSE no processador. E supondo que você tem a função CRC32 calhar, é trivial para implementar.

Usando masm615 ao compilador: 

delay_function macro
    mov cx,0ffffh
.repeat
    push cx
    mov cx,0f00h
    .repeat
        dec  cx
        .until cx==0
    pop cx
    dec cx
    .until cx==0
endm

random_num macro
   mov  cx,64    ;assum we want to get 64 random numbers
   mov  si,0

get_num:    
   push cx
   delay_function    ;since cpu clock is fast,so we use delay_function
   mov  ah,2ch  
   int  21h
   mov  ax,dx     ;get clock 1/100 sec
   div  num       ;assume we want to get a number from 0~num-1
   mov  arry[si],ah   ;save to array you set
   inc  si
   pop  cx
   loop get_num   ;here we finish the get_random number

Além disso, você provavelmente pode emular deslocando registo com elementos soma XOR entre pedaços separados, o que lhe dará pseudo-aleatório seqüência de números.

Linear congruential (X = AX + C mod M) PRNG do poderia ser uma boa para atribuir para um curso de montador como seus alunos terá que lidar com pedaços de transporte para resultados AX intermediários mais de 2 ^ 31 e computação um módulo. Se você é o aluno que eles são bastante simples de implementar em assembler e pode ser o que o professor tinha em mente.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top