title in python plot

En Python Dictionaries, ¿cómo((j*5)+1)% 2** ciclo entre los 2** i

Question

Estoy investigando cómo Python implementa diccionarios. Una de las ecuaciones en la implementación del diccionario python relaciona el sondeo pseudoaleatorio para una ranura de diccionario vacía usando la ecuación

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

que se explica aquí .

He leído esta pregunta, ¿Cómo se implementan los diccionarios integrados de Python ? , y básicamente entiendo cómo se implementan los diccionarios.

Lo que no entiendo es por qué / cómo la ecuación:

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

recorre todos los restos de 2**i . Por ejemplo, si i = 3 para un tamaño inicial total de 8. j pasa por el ciclo:

0
1
6
7
4
5
2
3
0

si el tamaño inicial es 16, pasará por el ciclo:

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

Esto es muy útil para probar todos los espacios en el diccionario. Pero, ¿por qué funciona? ¿Por qué j = ((j*5)+1) funciona pero no j = ((j*6)+1) o j = ((j*3)+1) los cuales se atascan en ciclos más pequeños.

Espero obtener una comprensión más intuitiva de esto que la ecuación simplemente funciona y es por eso que lo usaron .

Answer 1

Este es el mismo principio que usan los generadores de números pseudoaleatorios, como Jasper insinuó, es decir, generadores congruenciales lineales . Un generador congruente lineal es una secuencia que sigue la relación X_(n+1) = (a * X_n + c) mod m . Desde la página wiki,

El período de un LCG general es como máximo m, y para algunas opciones de factor es mucho menor que eso. El LCG tendrá un período completo para todos los valores iniciales si y solo si:

1. c son relativamente primos.
2. a - 1 es divisible por todos los factores primos de m .
3. a - 1 es divisible por 4 si m es divisible por 4 .

Está claro ver que 5 es el más pequeño para satisfacer estos requisitos, es decir

1. 2 ^ i y 1 son relativamente primos.
2. 4 es divisible por 2.
3. 4 es divisible por 4.

También, curiosamente, 5 no es el único número que cumple estas condiciones. 9 también funcionará. Tomando m ser 16, usando j=(9*j+1)%16 rendimientos

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

La prueba para estas tres condiciones se puede encontrar en el documento original de Hull-Dobell en la página 5, junto con muchos otros teoremas relacionados con PRNG que también pueden ser de interés.