In Python Dizionari, come fa ((j * 5) +1)% 2 ** I cicla tutto 2 ** i

Question

Sto cercando come Python implementa i dizionari. Una delle equazioni nell'attuazione dizionario pitone riguarda la pseudo casuale rivelamento per uno slot dizionario vuoto usando l'equazione

j = ((j*5) + 1) % 2**i 

che si spiega here.

Ho letto questa domanda, How are Python's Built In Dictionaries Implemented e fondamentalmente capisco come vengono implementati i dizionari.

Quello che non capisco è perché/come l'equazione:

j = ((j*5) + 1) % 2**i 

cicli attraverso tutti i resti di 2**i. Ad esempio, se i = 3 per un totale di partenza 8. j passa attraverso il ciclo:

0 
1 
6 
7 
4 
5 
2 
3 
0 

se la dimensione di partenza è di 16, sarebbe passare attraverso il ciclo:

0 1 6 15 12 13 2 11 8 9 14 7 4 5 10 3 0 

Questo è molto utile per sondare tutti gli slot nel dizionario. Ma perché funziona? Perché lo standard j = ((j*5)+1) funziona ma non è j = ((j*6)+1) o j = ((j*3)+1) che rimangono bloccati in cicli più piccoli.

Spero di ottenere una comprensione più intuitiva di questo rispetto l'equazione funziona ed è per questo hanno usato.

Answer 1

Questo è lo stesso principio utilizzato dai generatori di numeri pseudo casuali, come suggerito da Jasper, ovvero linear congruential generators. Un generatore congruenziale lineare è una sequenza che segue la relazione X_(n+1) = (a * X_n + c) mod m. Dalla pagina wiki,

Il periodo di un LCG generale è al massimo m, e per alcune scelte di fattore un molto meno di quello. La LCG avrà un periodo ricco per tutti i valori di inizializzazione se e solo se:

1. m e c sono primi.
2. a - 1 è divisibile per tutti i fattori primi di m.
3. a - 1 è divisibile per 4 se m è divisibile per 4.

E 'chiaro a vedere che 5 è il più piccolo a di soddisfare questi requisiti, vale a dire

1. 2^ie 1 sono primi.
2. 4 è divisibile per 2.
3. 4 è divisibile per 4.

anche interessante, 5 non è l'unico numero che soddisfa queste condizioni. 9 funzionerà anche.Prendendo m di essere 16, utilizzando i rendimenti j=(9*j+1)%16

0 1 10 11 4 5 14 15 8 9 2 3 12 13 6 7 

La prova per queste tre condizioni si possono trovare in the original Hull-Dobell paper a pagina 5, insieme ad un gruppo di altri teoremi PRNG-correlati che possono anche essere di interesse.