В словарях Python как ( (j*5)+1) % 2**i проходит через все 2 ** i

Question

Я исследую, как Python реализует словари. Одно из уравнений в реализации словаря Python относится к псевдослучайному зондированию для пустого слота словаря с использованием уравнения

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

что объясняется здесь.

Я прочитал этот вопрос, как реализованы встроенные словари Python, и в основном понимаю, как реализованы словари.

То, что я не понимаю, почему / как уравнение:

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

циклы через все остатки 2**i, Например, если i = 3 для общего начального размера 8. j проходит через цикл:

0
1
6
7
4
5
2
3
0

если начальный размер равен 16, он прошел бы цикл:

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

Это очень полезно для проверки всех слотов в словаре. Но почему это работает? Почему j = ((j*5)+1) работать, но не j = ((j*6)+1) или же j = ((j*3)+1) оба из которых застряли в меньших циклах.

Я надеюсь получить более интуитивное понимание этого, чем уравнение просто работает, и поэтому они использовали его.

Answer 1

Это тот же принцип, который используют генераторы псевдослучайных чисел, как намекал Джаспер, а именно линейные конгруэнтные генераторы. Линейный конгруэнтный генератор - это последовательность, которая следует за соотношением X_(n+1) = (a * X_n + c) mod m, Со страницы вики

Период общего LCG составляет самое большее m, а для некоторых вариантов множителя намного меньше этого. У LCG будет полный период для всех начальных значений, если и только если:

1. m а также c относительно простые.
2. a - 1 делится на все основные факторы m,
3. a - 1 делится на 4, если m делится на 4,

Понятно, что 5 самый маленький a удовлетворить эти требования, а именно

1. 2^i и 1 относительно простые.
2. 4 делится на 2.
3. 4 делится на 4.

Также интересно, 5 не единственное число, которое удовлетворяет этим условиям. 9 тоже будет работать. принятие m быть 16, используя j=(9*j+1)%16 доходность

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

Доказательство этих трех условий можно найти в оригинальной статье Халла-Добелла на странице 5, а также в связке других теорем, связанных с ГСЧ, которые также могут представлять интерес.