Chiarimento del generatore di numeri pseudo casuali

Question

Chiarimento del generatore di numeri pseudo casuali

#1 da (2 voti)
#2 da (0 voti)

1

Mi viene chiesto di creare un generatore di numeri pseudo-casuali usando il seguente algoritmo:

The generator will generate every integer from 1 to N-1 exactly once

The algorithm for N=2^n

Initialize an integer R to be equal to 1 every time the tabling routine is called and then on each successive call for a random number:

set R=R*5

mask out all but the low-order n+2 bits of the product and place the result in R

set p=R/4

Che cosa significa l'algoritmo quando dice mascherare tutto tranne i bit di basso ordine n+2 del prodotto?

algorithms pseudocode

posta yannis 06.07.2011 - 04:53

fonte

2 risposte

Leggi altre domande sui tag algorithms pseudocode

Come creare un meccanismo di aggiornamento centralizzato per un CMS ospitato? git / svn Hook per progetti PHP / Zend

score 2 · Answer 1

per n = 1 maschera i 3 minimi bit

assumendo big endian avresti questo layout di bit

128 64  32  16  8   4   2   1
X   X   X   X   X   O   O   O

O sarebbe i bit che avresti voluto conservare e useresti l'operatore bit per bit e l'operatore con il valore 7 poiché hai bisogno dell'altezza di 4, 2 e 1 bit per mascherarli (AND bit a bit). myProduct &= 0x07; // force all bits except the 3 least to be 0

score 0 · Answer 2

Ecco un esempio funzionante, utilizzando l'interprete Python per aiutare con la conversione binaria

>>> bin(1234567)
'0b100101101011010000111'

Supponiamo n = 4, quindi ho bisogno di mascherare tutto tranne gli ultimi 6 bit. Quale dovrebbe dare

>>> n=4
>>> 0b000111
7

la pagina binaria di wikipedia ha alcune informazioni su bit a bit operazioni. Qui siamo interessati all'operazione AND

>>> 1234567 & 0b111111
7

Un modo per arrivare a questa maschera è calcolare il numero uno più grande (dal momento che è una potenza di 2) e sottrarre uno da esso

>>> (1<<n+2)-1
63
>>> bin(63)
'0b111111'

(1<<n+2)-1 può essere semplificato in (4<<n)-1 , ma in questo caso c'è un altro modo

>>> 1234567 % (4<<n)
7

Ho sostituito il bit AND ( & ) con modulo ( % ) che ha lo stesso effetto di mascherare i bit n + 2 più bassi

Il modulo

ha un po 'più lavoro per la CPU rispetto alle operazioni bit a bit, quindi se le migliori prestazioni sono essenziali, dovresti usare il metodo bit a bit