Generatore pseudocasuale in linguaggio Assembly
Domanda
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?
Soluzione
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.
Altri suggerimenti
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).
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
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.
@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).
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.
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
probabilmente puoi anche emulare il registro mobile con elementi somma XOR tra bit separati, che ti darà una sequenza di numeri pseudo-casuale.
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.