AOP_Tom2 (1021737), страница 33
Текст из файла (страница 33)
В упр. 30 доказывается, что длина периода последовательности, определенной в выражении (7), точно равна 2' '(2ы — 1), когда пз = 2'. На первый взгляд, рекуррентное соотношение (7) кажется не очень удобным для реализации на компьютере, но на самом деле существует эффективный путь генерирования этой последовательности с помощью циклической таблицы. Алгоритм А [Аддитивный генератор чисел).
В ячейки памяти У[1], У[2], у[55] записано множество значений Хьь, Льь, ..., Лп соответственно; у вначале равно 24, а )1 равно 55. При реализации этого ачгоритма на выходе последовательно получаем числа Хьь, Льь, А1. [Суммирование.] (Если на выходе мы оказываемся в точке Л„, то У[Я равно Л„-м, а г[я] равно Х„ьь.) Запишем У[я] < — (у[к! + г[Я)пюа2', тогда на выходе получим Цй]. А2. [Продвижение.] Уменьшим у и к на 1. Если у = О, то присвоим 7' <- 55; иначе, если я = О, присвоить й — 55.
$ Этот алгоритм на компьютере ИТХ имеет следующий вид. Программа А (Аддитиеный генератор чисел). Если предположить, что индексные регистры 5 и 6, содержащие у и й, не затрагиваются частью программы, в которой зта подпрограмма размещена, то следующий текст программы реализует алгоритм А и заносит результат в регистр А. 555 ~,5 500 Т, 5 1'ь + 13 (возможно переполнение) БТА Т,б -ь К;. ° 555 1 Ьгппж 0ЕС6 1 5 <- 5 — 1. 55Р в+2 ЕйТ5 55 Если д = О, присвоить д < — 55. 56Р в+2 ЕМТ6 55 Если 5 = О,присвоить 5 < — 55.
3 Этот генератор обычно работает быстрее других генераторов, обсуждавшихся ранее, так как он не требует никакого умножения. Кроме большой скорости выполнения этот алгоритм имеет самый длинный период'из тех, которые встречались ранее, за исключением периода из упр. 3.2.1.2-22. Более того, как заметил Ричард Брент (В1с!ьагг) Вгепь), его можно реализовать в режиме работы с плавающей запятой, избегая преобразований целых чисел в дробные числа и наоборот (см.
упр. 23). Поэтому можно доказать, что этот генератор является наилучшиль источником случайных чисел для достижения практических целей. Основная причина, по которой трудно искренне рекомендовать последовательности, подобные (7), состоит в том, что получена очень мало теоретических результатов, основываясь на которых, можно проверить.
имеет ли такая последовательность желаемые случайные свойства. Учитывая, как уже известно, что длинный период не всегда обеспечивает льелвемые свойства, Джон Рейзер (дайн йе1ьеь) (РЬ. 0. с!зеь1ь, Бьап1огс1 11п1хегь11у, 1977) показал, однако, что аддитивные последовательности, подобные (7), будут в высокой степени хорошо распределены для болыпих размерностей, если обеспечить выполнение определенных приемлемых условий (см.
упр. 26). Числа 24 и 55 в (7) обычно называют запаздыванием, а числа Х„, определенные в (7), — последовательностью Фибонпччи с запаздыванием. Причины, по которым запаздывания, подобные (24,55), работают хорошо, следуют из приведенных ниже теоретических результатов.
Конечно, до некоторой степени легче использовать большие запаздывания, когда в приложениях случается применять, скажем, группы из 55 чисел одновременно. Среди чисел, генерируемых (7), никогда не найдется Таблица 1 СМЕЩЕНИЯ, ПРИВОДЯЩИЕ К ДЛИННЫМ ПЕРИОДАМ ПО МОДУЛЮ 2 (24, 55) (37, 100) (83, 258) (273, 607) (576, 3217) (7083, 19937) (38, 89) (30, 127) (107, 378) (1029, 2281) (4187, 9689) (9739, 23209) Расгоиреииые варианты втой таблицы приводятся в работах Н. 21егсег апб Л ВППЬагс, спсогшапоп апг! Сопггос 18 (1968), 541-5о4, 14 (1969), 566-569, 15 (1969), 67-69; У. Кпгна апг1 М. Маицгпосо, маей. сошр, 56 (1991), 817-821; неппба, В!осе, апг1 согпрабпег, гпс..у, 54огс.
Рьус. сз (1992), 561-564, значений Л'„, лежащих строго между Х„24 и Х„аа (см. упр, 2). ?К.-М. Норманд (,!.-М. Хоппапс(), Г. Й. Герман (Н. 3. Негппапп) и М. Хаджар (М. Нацаг) обнаружили небольшое смещение в числах, генерируемых (7), когда им понадобилось 10" случайных чисеб для проводимых с высокой точностью обширных исследований метода Монте-Карло [з. Яса1!61!са! РЛув!сб 52 (1988), 441-446); но при больших значениях й смещение уменьшалось. В табл. 1 приведена несколько пар чисел (1, Л), для которых последовательность Л„= (Х„с + Х„с) тес(2' имеет период длиной 2' 1(21 — 1). Случая, когда (1,5) = (30,127), казалось бы, достаточно для большинства применений, особенно в сочетании с другими, увеличиваилпими случайность, методами, которые мы обсудим виже. Генератор случайных чисел во многом подобен сексу: когда он хорош — это прекрасно, когда он плох, все равно приятно (Джордж Марсалья, 1984).
Джордж Марсалья (Сотр. Яс!. аиг! Всас!81!сбг Бугпроя!ит оп 1Ле 1п1егуасе 16 (1984), 3--10) предложил заменить (7) на (7') Хв = (Л -ве Х -еа) шобпа, гг) 55, где ио кратно 4, а все числа от Ло до Лае нечотны, но сравнимы с 1 (по модулю 4). Тогда второстепенные младшие разряды имеют период 255 — 1, в то время как старшие двоичные разряды более тщательно перемешаны, чесс раньше, твк как они существенно зависят от всех разрядов Х„24 и Х„55. В упр. 31 показано, что длина периода последовательности (7') лишь незначительно меньше длины периода погледовательности (7).
Генераторы последовательности Фибоначчи с запаздыванием успешно применялись во многих ситуациях с 1958 года. Таким образом, открытие в 90-е годы того, что они фактически провалились на крайне простом, незамысловатом критерии случайности, явилось сионом (см, упр. 3,3.2-31). Как избежать таких иеприятностейг отбрасывая ненужные элементы последовательности, рассказыиается в конце этого раздела. Вместо рассмотрения исключительно алдитивных или исключительно мультипликативных последовательностей можно построить достаточно хороший генератор слУчайных чисел, нспользУЯ всевозможные линейные комбинаЦии Хо 1, ..., Х„а для малых й.
В этом глучае наилучший результат получается, когда модуль гп является большим проствьсс числом; например, т может быть выбрано так, чтобы оно было наибольшим простым числом, которое можно записать одним компьютерным словом (см. табл. 4.5.4 — 2). Когда т = р — простое число, то по теории конечных полей можно найти множители аг,..., ас., такие, что последовательность, определенцая соотношением Х„= (а~ Х„1+ .. + аъЛ„ь) шод р, (8) бУдет иметь пеРиод длиной Ръ — 1. Здесь Лш..., Хъ 1 могУт быть выбРаны пРоизвольпо, но так, чтобы все онн не были нулями. (Частный случай, когда Й = 1, соответствует мультипликативной конгруэнтной последовательности с уже известным простым модулем.) Константы ам..., аъ в (8) обладают подходящими свойствами тогда и только тогда, когда полинам /(х) = х — а,х — ..
— аъ ъ ъ-1 (9) является первообрвзным полиномом по модулю р, что выполняется тогда и только тогда, когда корень этого полинома есть первообразный элемент поля с ръ элементами (см. упр, 4.6.2-16). Конечно, для достижения практических целей недостаточно простого факта сйщесгпввванил подходящих констант ам ..., аъ, дающих период длиной р" — 1. Необходимо быть в состоянии найти их, ведь нельзя проверить все ръ возможностей, так как р имеет порядок длины слова компъютера. К счастью, есть точно уэ(рь — 1)/)с подходящих наборов (ам...,аъ), поэтому в известной степени существует хороший шанс натолкнуться на один из них после нескольких случайных попыток.
Но также следует уметь быстро определять, будет ли (9) первообразным полиномом по модулю р. Конечно, немыслимо генерировать до ръ — 1 элементов последовательности и ждать повторения! Методы проверки того, что полином будет первообразным по модулю р, обсуждались Аланеном (А!апеп) и Кнутом (Кппсй) в Яап1г11уа А26 (1964), 305-328. Можно использовать следующий критерий.
Пусть т = (р~ — 1)/(р — 1). 1) (-1)" 1аъ должен быть первообразным корнем по модулю р (см. раздел 3.2.1.2), й) Полипом х' должен быть сравним с ( — 1)" 'аъ по модулям /(х) и р. ш) Степень хг/э шоп'/(х) (здесь испадъзуетсй арифметика полиномов по модулю р) должна быть положительной для каждого г — простого делителя д. Эффективный способ вычисления полинома х" шой /(х) с использованием полиномиальной арифметики по модулю, заданному простым числом р, обсуждается в разделе 4.6.2. Для того чтобы довести до конца тест, необходимо знать разложение на простые множители числа г = (ръ — 1)/(р — 1), что и является ограничивающим фактором в вычислениях.
г можно разложить на множители в приемлемый отрезок времени, когда к = 2, 3 и, возможно, 4, но большие значения к усложняют вычисления, когда р большое. Даже при к = 2 число "значащих случайных цифр", которое достигается при й = 1, по существу, удваивается, так что большие значения й вряд ли понадобятся. Видоизмененный спектральный критерий (раздел 3.3.4) можно использовать для оценки последовательности чисел, генерируемых (8): см. упр. 3.3.4 — 24. Рассуждения. приведенные в этом разделе, показывают, что не следовало бы делать очевидный выбор (а~ = +1 или — 1), когда встречается такая форма первообразного полинома. Лучше выбрать большие, совершенно "случайные' значения а1....., аю удовлетворяк~шие условиям, в проверить выбор с помощью спектрального критерия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
