Chiarimento del generatore di numeri pseudo casuali

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?

    
posta yannis 06.07.2011 - 06:53
fonte

2 risposte

2

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

    
risposta data 06.07.2011 - 07:00
fonte
0

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

    
risposta data 07.07.2011 - 06:18
fonte

Leggi altre domande sui tag