Это база: Зачем нужна математика в повседневной жизни

На практике поток битов из генератора псевдослучайных чисел объединяется с другими данными, которых требует GPS, – такой метод называется модуляцией. Спутник передает данные с относительно невысокой скоростью: 50 бит в секунду. Он соединяет этот сигнал с куда более быстрым потоком битов из генератора псевдослучайных чисел, скорость которого более миллиона чипов в секунду. Чип здесь – примерно то же, что и бит, но значения он принимает +1 или –1, а не 0 или 1. Физически это прямоугольный импульс с амплитудой либо +1, либо –1. «Модуляция» означает, что первоначальная строка данных умножается на значение чипа в каждое мгновение. Поскольку все другие данные меняются, по сравнению с этим, очень медленно, методика «сдвинуть и совместить» по-прежнему работает достаточно хорошо, но иногда сигналы совпадают полностью, а иногда они оказываются противоположными по знаку. Если воспользоваться статистическим методом корреляции, то получится, что вам нужно просто сдвигать сигналы друг относительно друга, пока их корреляция не станет достаточно высокой.

Мало того, GPS проделывает то же самое и с другим псевдослучайным числом, модулирующим сигнал на вдесятеро большей скорости. Более медленный сигнал называется «код грубого определения местоположения объектов» и предназначен для гражданского использования. Более быстрый – «точный код» – зарезервирован для военных. Он, кроме того, зашифрован и повторяется не чаще чем раз в семь суток.

Генераторы псевдослучайных чисел, как правило, основаны на абстрактной алгебре, такой как многочлены над конечными полями, или на теории чисел, такой как целые числа по некоторому модулю. Простой пример последнего – линейный конгруэнтный генератор. Выберем модуль m, два числа a и b (mod m) и начальное число x₁ (mod m). Затем определим последовательные числа x₂, x₃, x₄ и т. д., вычисляемые по формуле

x_n+1 = ax_n + b (mod m),

где a играет роль постоянного множителя текущего числа x_n, а b сдвигает полученное значение на постоянную величину. Это дает следующее число последовательности, после чего операция повторяется. Например, если m = 17, a = 3, b = 5 и x₁ = 1, то мы получаем последовательность

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

которая затем повторяется бесконечно. Никаких явных закономерностей, заметных глазу, здесь нет. На практике, разумеется, m намного больше. Существуют математические условия, которые гарантируют, что последовательность повторяется очень и очень редко и при этом удовлетворяет разумным статистическим тестам на случайность. Например, после превращения выходной последовательности в двоичную, каждое число (по модулю m) должно появляться в ней с равной частотой в среднем. То же можно сказать и о каждой строке из нулей и единиц заданной длины, вплоть до некоторого разумного размера.

Линейные конгруэнтные генераторы слишком просты, чтобы быть надежными, поэтому были разработаны более сложные варианты. В качестве примера можно назвать вихрь Мерсенна, который придумал Макото Мацумото в 1997 году. Такой генератор наверняка есть у многих из вас, потому что он используется в десятках стандартных программных пакетов, в том числе в Microsoft Excel. В вихре Мерсенна сочетаются простые числа, благодаря которым математика упрощается, и симпатичные двоичные выражения, упрощающие вычисления. Простое число Мерсенна – это число вида 2^p – 1 (где p – простое число), такое как 31 = 2⁵–1 или 131 071 = 2¹⁷–1. Простые числа Мерсенна встречаются редко, и мы даже не знаем, бесконечно ли их количество. В январе 2021 года было известно ровно 51 простое число Мерсенна, самое большое из которых равно 2^82 589 933–1.

В двоичном виде два простых числа Мерсенна выглядят так:

31 = 11111

131 071 = 11111111111111111

и представляют собой 5 и 17 единиц соответственно. Это позволяет цифровому компьютеру легко оперировать ими при вычислениях. Вихрь Мерсенна основан на каком-нибудь очень большом простом числе Мерсенна, обычно 2^19 937–1, и он заменяет числа в сравнениях матрицами над полем с элементами 0 и 1. Этот метод удовлетворяет тестам для подстрок длиной вплоть до 623 бит.