In Python-Wörterbücher, wie funktioniert ((j * 5) +1)% 2 ** Ich durchlaufe alle 2 ** ich

Question

Ich forsche, wie Python Wörterbücher implementiert. Eine der Gleichungen in der Python Wörterbuch Implementierung bezieht sich die der Pseudozufalls für einen leeren Schlitz Wörterbuch Sondieren der Gleichung

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

die here erläutert.

Ich habe diese Frage gelesen, How are Python's Built In Dictionaries Implemented, und im Grunde verstehen, wie Wörterbücher implementiert werden.

Was ich nicht verstehe ist, warum/wie die Gleichung:

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

Zyklen durch alle Reste von 2**i. Zum Beispiel geht, wenn i = 3 für eine Gesamtausgangsgröße von 8 j durch den Zyklus:

0 
1 
6 
7 
4 
5 
2 
3 
0 

, wenn die Ausgangsgröße 16 ist, würde es durch den Zyklus gehen:

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

Dies ist sehr nützlich für die Untersuchung aller Slots im Wörterbuch. Aber warum funktioniert es? Warum funktioniert j = ((j*5)+1) funktioniert aber nicht j = ((j*6)+1) oder j = ((j*3)+1) die beide in kleineren Zyklen stecken bleiben.

Ich hoffe, ein intuitiveres Verständnis davon zu bekommen als die Gleichung funktioniert einfach und deshalb haben sie es verwendet.

Answer 1

Dies ist das gleiche Prinzip, das Pseudozufallszahlengeneratoren verwenden, wie Jasper andeutete, nämlich linear congruential generators. Ein linearer kongruenter Generator ist eine Sequenz, die der Beziehung X_(n+1) = (a * X_n + c) mod m folgt. Von der Wiki Seite,

Die Periode einer allgemeinen LCG ist höchstens m, und für einige Wahlen des Faktors viel weniger als das. Die LCG eine volle Periode für alle Seed-Werte haben, wenn und nur wenn:

1. m und c relativ prim sind.
2. a - 1 ist durch alle Primfaktoren von m teilbar.
3. a - 1 ist durch 4 teilbar, wenn m durch 4 teilbar ist.

Es ist klar zu sehen, dass 5 die kleinste a ist es, diese Anforderungen zu erfüllen, nämlich

1. 2^i und 1 sind relativ prim.
2. 4 teilbar durch 2.
3. 4 teilbar durch 4.

interessanterweise auch, 5 ist nicht die einzige Zahl, die diese Bedingungen erfüllt. 9 wird auch funktionieren.Unter m zu 16, mit j=(9*j+1)%16 Ausbeuten

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

Der Beweis für diese drei Bedingungen kann in the original Hull-Dobell paper auf Seite 5, zusammen mit einer Reihe anderer PRNG bezogenen Sätze gefunden werden, die auch von Interesse sein können.