Псевдослучайные последовательности

В главе 6 мы уже встречались с последовательностью чисел Фибоначчи. Это бесконечная последовательность целых чисел, получаемая с помощью простого правила: каждый ее элемент является суммой двух предыдущих. Традиционно эта последовательность начинается с двух первых элементов, равных 0 и 1. К сожалению, последовательность чисел Фибоначчи, как уже упоминалось выше, имеет ряд арифметических свойств, делающих ее совсем не подходящей в качестве источника псевдослучайных чисел. Однако допустим, что мы изменили правило получения чисел на другое, например, такое: каждый элемент равен удвоенному предыдущему элементу, сложенному с элементом, стоящим перед ним. Будет ли такая последовательность лучше подходить для наших целей? Если начать с 0 и 1 в качестве двух первых элементов, то первые 10 элементов последовательности выглядят так:

0,1,2,5,12,29,70,169,408,985.

Несложно заметить, что элементы этой последовательности четные и нечетные попеременно, и это уже само по себе является достаточным основанием не рассматривать ее в качестве источника псевдослучайных чисел. Конечно, вовсе не обязательно начинать с 0 и 1, в качестве первых двух элементов можно выбрать любые числа, но данный недостаток является существенным, поэтому любая последовательность, полученная таким образом, нам не годится. После знакомства с массой свойств последовательности чисел Фибоначчи логично ожидать, что данная последовательность также обладает целым рядом математических свойств: например, каждый третий ее элемент делится на 5, а отношение соседних элементов довольно быстро приближается к фиксированному числу:

2,41421356...

то есть

(1+2).

(Подробнее об этом см. приложением M10).