Generatore pseudocasuale in linguaggio Assembly

Question

Ho bisogno di un algoritmo di generazione di numeri pseudocasuali per un programma assembler assegnato in un corso e preferirei un algoritmo semplice.Tuttavia, non posso utilizzare una libreria esterna.

Qual è un buon e semplice algoritmo per la generazione di numeri pseudocasuali per l'assemblaggio?

Answer 1

Il metodo più semplice è semplicemente scegliere due grandi numeri primi relativi a e b, quindi continuare a moltiplicare il numero casuale per a e aggiungere b.Utilizza l'operatore modulo per mantenere i bit bassi come numero casuale e mantenere il valore completo per l'iterazione successiva.

Questo algoritmo è noto come generatore congruenziale lineare.

Answer 2

Volume 2 di L'arte della programmazione informatica contiene molte informazioni sulla generazione di numeri pseudocasuali.Gli algoritmi sono dimostrati in assembler, quindi puoi vedere tu stesso quali sono i più semplici in assembler.

Se puoi collegarti a una libreria esterna o a un file oggetto, questa sarebbe la soluzione migliore.Quindi potresti collegarti, ad esempio, Mersenne Twister.

Tieni presente che la maggior parte dei generatori di numeri pseudocasuali lo sono non sicuro per la crittografia, quindi se hai bisogno di una generazione sicura di numeri casuali, devi guardare oltre gli algoritmi di base (e probabilmente dovresti attingere alle API crittografiche specifiche del sistema operativo).

Answer 3

Codice semplice per test, non utilizzare con Crypto

Da Test del software del computer, pagina 138

Con la matematica a 32 bit, non è necessaria l'operazione MOD 2^32

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

Answer 4

Bene, poiché non ho visto un riferimento al buon vecchio registro a scorrimento con feedback lineare, pubblico alcuni codici C basati su SSE intrinseco.Solo per completezza.Ho scritto quella cosa un paio di mesi fa per affinare nuovamente le mie capacità SSE.

#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));
}

Tradurre questo codice in assembler è banale.Basta sostituire gli elementi intrinseci con le istruzioni SSE reali e aggiungere un ciclo attorno ad essi.

A proposito, la sequenza generata da questo codice si ripete dopo 4.61169E+18 numeri.È molto di più di quello che otterrai tramite il metodo prime e l'aritmetica a 32 bit.Se srotolato è anche più veloce.

Answer 5

@jjrv
Quello che stai descrivendo è in realtà un generatore congrenziale lineare.I bit più casuali sono i bit più alti.Per ottenere un numero da 0..N-1 moltiplicare il valore completo per N (32 bit per 32 bit ottenendo 64 bit) e utilizzare i 32 bit alti.

Non dovresti usare semplicemente un numero qualsiasi per UN (il moltiplicatore per progredire da un valore completo a quello successivo), i numeri raccomandati in Knuth (Tabella 1 sezione 3.3.4 TAOCP vol 2 1981) sono 1812433253, 1566083941, 69069 e 1664525.

Puoi semplicemente scegliere qualsiasi numero dispari per B.(l'addizione).

Answer 6

Perché non utilizzare una libreria esterna???Quella ruota è stata inventata centinaia di volte, quindi perché rifarla?

Se devi implementare tu stesso un RNG, devi produrre numeri su richiesta, ad es.stai implementando una funzione rand() - o hai bisogno di produrre flussi di numeri casuali - ad es.per testare la memoria?

Hai bisogno di un RNG che abbia la forza della criptovaluta?Quanto tempo deve passare prima che si ripeta?Devi garantire in modo assoluto e positivo la distribuzione uniforme di tutti i bit?

Ecco un semplice trucco che ho usato diversi anni fa.Stavo lavorando in modalità embedded e avevo bisogno di testare la RAM all'accensione e volevo un codice davvero piccolo e veloce e uno stato minimo, e ho fatto questo:

• Inizia con una costante arbitraria di 4 byte per il tuo seed.
• Calcola il CRC a 32 bit di quei 4 byte.Questo ti dà i successivi 4 byte
• Reinserisci questi 4 byte nell'algoritmo CRC32, come se fossero stati aggiunti.Il CRC32 di quegli 8 byte è il valore successivo.
• Ripeti quanto vuoi.

Questo richiede pochissimo codice (anche se è necessaria una tabella per la funzione crc32) e ha pochissimo stato, ma il flusso di output pseudorandom ha un tempo di ciclo molto lungo prima di ripetersi.Inoltre, non richiede SSE sul processore.E supponendo che tu abbia la funzione CRC32 a portata di mano, è banale da implementare.

Answer 7

Utilizzando masm615 per il compilatore:

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 

Answer 8

probabilmente puoi anche emulare il registro mobile con elementi somma XOR tra bit separati, che ti darà una sequenza di numeri pseudo-casuale.

Answer 9

I PRNG congruenziali lineari (X = AX + C mod M) potrebbero essere buoni da assegnare per un corso di assembler poiché i tuoi studenti dovranno occuparsi di bit di riporto per risultati AX intermedi superiori a 2 ^ 31 e calcolare un modulo.Se sei uno studente, sono abbastanza semplici da implementare in assembler e potrebbero essere ciò che il docente aveva in mente.