Se la dimensione di un set supera il periodo di un PRNG, è vero che alcune combinazioni potrebbero non essere in grado di essere generate? [duplicare]

Question

Se la dimensione di un set supera il periodo di un PRNG, è vero che alcune combinazioni potrebbero non essere in grado di essere generate? [duplicare]

#1 da (3 voti)
#2 da (2 voti)

1

Dato che le dimensioni di alcuni set (esempio, 52! (circa 2 ²²⁶ o 8 * 10 ⁶⁷), il numero di modi per mescolare un mazzo normale di carte) supera il periodo di più Pseudorandom Number Generators (PRNG), è vero che alcune combinazioni potrebbero non essere in grado di generare dal PRNG?

Importa se tenta di permutare l'array, o se sceglie gli elementi uno per uno? Che cosa succede se hai seminato periodicamente il generatore?

EDIT: non un duplicato. Non vedo come il duplicato proposto risponda alla domanda: È vero che alcune sequenze non possono essere generate, non importa come usi l'RNG (incluso il re-seeding) ?

random

posta gecko 01.12.2015 - 17:27

fonte

2 risposte

Leggi altre domande sui tag random

Quale modello di progettazione scegliere quando si supportano più strumenti analitici? Qual è la relazione "registrata" in un diagramma di classe? [chiuso]

score 3 · Answer 1

Bene ... si. Se la lunghezza del ciclo di un'uscita periodica di un processo è inferiore al numero di valori possibili nel tipo di dati, alcuni valori del tipo di dati non verranno mai generati. Infatti, i numeri combinatori sono enormi , sono molto più grandi della maggior parte dei tipi di dati, quindi la maggior parte possibili risultati non verranno mai generati.

Ma non è quello per cui usiamo gli RNG. Non siamo interessati a un processo che permuta semplicemente l'insieme di tutti i valori possibili. Vogliamo uno che riproduca un processo naturale, imprevedibile, in cui noi (o un avversario che lavora contro di noi) non possiamo discernere alcun modello da sfruttare. Per molte attività, gli RNG periodici forniscono esattamente questo. Il fatto che saltino alcuni (o la maggior parte dei) valori è irrilevante finché non puoi facilmente prevedere quali di essi saltano.

score 2 · Answer 2

Per avere la possibilità di generare tutte le sequenze è necessario utilizzare almeno log2 (n) bit di entropia. Per 52! questo è 226 bit di entropia.

Ciò significa che è necessario eseguire il reseeding del PRNG in modo che tutti i 226 bit vengano utilizzati. E anche in questo caso non puoi essere completamente sicuro che non ci sia una potenziale collisione che ti ha derubato di un possibile output.

Anche se nella maggior parte dei giochi di carte non viene utilizzato l'intero mazzo, si risparmiano alcuni bit in questo modo.

Nella maggior parte dei casi la sfida più grande è ottenere quei bit casuali.