Алгоритмы неформально. Инструкция для начинающих питонистов - [43]

overlap = overlapping_sums(list_random(211111,111112,300007),12)

plt.hist(overlap, 20, facecolor = 'blue', alpha = 0.5)

plt.title('Results of the Overlapping Sums Test')

plt.xlabel('Sum of Elements of Overlapping Consecutive Sections of List')

plt.ylabel('Frequency of Sum')

plt.show()

Новый случайный список создается с помощью вызова list_ran­dom(211111,111112,300007). Новый случайный список имеет достаточную длину для надежной работы теста пересекающихся сумм. Результатом выполнения кода является гистограмма, на которой представлены частоты наблюдаемых сумм. Если список действительно похож на случайный набор, то можно ожидать, что одни суммы будут большими, другие — маленькими, но большинство будет лежать поблизости от середины диапазона возможных значений. Именно это мы видим на гистограмме (рис. 5.2).

Рис. 5.2. Результат теста пересекающихся сумм для ЛКГ

Присмотревшись, можно заметить, что гистограмма имеет форму колокола. Как говорилось выше, список проходит тест пересекающихся сумм, если распределение набора напоминает колоколообразную кривую — конкретную кривую, важную с математической точки зрения (рис. 5.3).

Рис. 5.3. Колоколообразная кривая, или гауссова кривая нормального распределения (источник: Wikimedia Commons)

Колоколообразная кривая, как и золотое сечение, нередко встречается в совершенно неожиданных местах — как в математике, так и в реальном мире. В данном случае близкое сходство между результатами теста перекрывающихся сумм и колоколообразной кривой интерпретируется как доказательство того, что ГПСЧ близок к истинной случайности.

Знание математической теории случайности пригодится вам при разработке генераторов случайных чисел. Тем не менее почти того же результата можно добиться, просто придерживаясь житейских представлений о том, как выигрывать в рулетку.

Регистры сдвига с линейной обратной связью

ЛКГ легко реализуются, но их возможностей недостаточно для всех вариантов применения ГПСЧ; опытный игрок в рулетку моментально взломает ЛКГ. Рассмотрим более совершенную и надежную разновидность алгоритмов — регистры сдвига с линейной обратной связью (РСЛС), служащие отправной точкой для углубленного изучения алгоритмов ГПСЧ.

РСЛС проектировались с учетом особенностей компьютерной архитектуры. На самом низком уровне данные в компьютерах хранятся в виде последовательностей 0 и 1 (битов). Одна из возможных строк из десяти битов изображена на рис. 5.4.

Рис. 5.4. Строка из десяти битов

Начнем с этих битов и перейдем к простому алгоритму РСЛС. Начнем с вычисления простой суммы подмножества битов — например, четвертого, шестого, восьмого и десятого бита (также можно выбрать другие подмножества). В данном случае эта сумма равна 3. В архитектуре компьютеров могут храниться только 0 и 1, поэтому мы вычисляем результат sum mod 2 и получаем итоговую сумму 1. Затем правый крайний бит удаляется, а все оставшиеся сдвигаются на 1 позицию вправо (рис. 5.5).

Рис. 5.5. Биты после удаления и сдвига

После удаления бита и сдвига всех остальных битов появляется пустая позиция, в которую нужно вставить новый бит. Им будет сумма, вычисленная ранее. После вставки появляется новое состояние битов (рис. 5.6).

Рис. 5.6. Биты после вставки вычисленной суммы

Бит, удаленный в правой части, берется как результат работы алгоритма — псевдослучайное число, которое должно генерироваться алгоритмом. А поскольку у нас появился новый набор из десяти битов, то можно снова выполнить алгоритм и получить новый псевдослучайный бит, как и прежде. Процесс можно повторять сколько угодно раз.

На языке Python регистр сдвига с линейной обратной связью реализуется достаточно просто. Вместо того чтобы напрямую перезаписывать отдельные биты на жестком диске, мы просто создадим список битов:

bits = [1,1,1]

Сумма битов в заданных позициях вычисляется в одной строке. Результат сохраняется в переменной xor_result, поскольку операция sum mod 2 также называется исключающим ИЛИ, или XOR (eXclusive OR). Если вы уже изучали формальную логику, то, вероятно, операция XOR вам уже встречалась — у нее есть как логическое определение, так и эквивалентное математическое определение; мы будем использовать математическое. Мы работаем с короткой битовой строкой, поэтому не суммируем четвертый, шестой, восьмой и десятый биты (так как они не существуют), а вместо этого суммируем второй и третий:

xor_result = (bits[1] + bits[2]) % 2

Затем извлекаем правый элемент bits с помощью удобной функции Python pop() и сохраняем результат в переменной output:

output = bits.pop()

Затем сумма вставляется в список функцией insert(). При этом указывается позиция 0, так как новый элемент должен находиться у левого края списка:

bits.insert(0,xor_result)

Объединим все части в одну функцию, которая возвращает два результата: псевдослучайный бит и новое состояние последовательности bits (листинг 5.9).

Листинг 5.9. Функция, реализующая РСЛС

def feedback_shift(bits):

    xor_result = (bits[1] + bits[2]) % 2

    output = bits.pop()

    bits.insert(0,xor_result)

    return(bits,output)

Как и в случае с ЛКГ, мы создадим функцию, которая генерирует список выходных битов: