Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 35
Текст из файла (страница 35)
В строке 28 представлен более типичный генератор, основанный на методе вычитания с заимствованием Хч (Хч-1е Хи-ы Сп) шог) 2 ~ Си+1 (Хп-1е с Хч-24 + Сч]~ но модифицированный так, что при генерировании 389 элементов последовательности используются только первые (или последние) 24. Этот генератор называется 11АХИ1Х и предложен Мартином Дюшером (Маг1ш Ьйэслег) после того, как он прошел проверку такими строгими критериями, которые забраковали предыдущие генераторы (см, Сошрпгег РЬуэ/сз Солипшнсабопз 79 (1994), 100-НО). Подобная последовательность С +л = (Л„м <Л» зз+ С»1, Л» = (Л»-зз Л»-4з — С») шод (2 — 5), такая, что нз 400 генерируемых чисел выбираются 43, прнвцдена в строке 29.
Она обсуждается в ответе к упр. 3.2.1.2-22. В обоих случаях элементы таблицы соответствуют спектральному критерию, примененному к числам Х», которые имеют высокую точность, вместо того, чтобы соответствовать индивидуальным "цифрам" Л», но большие значения /л показывают, что процесс генерирования 389 нлн 400 случайных чисел для отбора 24 нлн 43 — эта идеальный путь устранения смещения благодаря крайней простоте схемы генерирования.
Теоретические вархиве грани для рм которые не могут быть превышены для любого т, приведены сразу под табл, 1. Известно, что для каждой решетки, на еднннцу объема которой приходится т точек, выполняется неравенство гч <7,'" '/', где и принимает соответствующие значения (4 /3)1/з 21/з 21/з 23/3 (64 ~3)1/6 43/г (41) для $ = 2, ..., 8.
(См. упр. 9 н книги Дж. В. С. Касселя (Л. %, Я. Саззе1з, 1пгго<)исйап го з)зе Сеошеггу аГЖитЬегз (Вегйп: Бргшйег, 1959), 332); Дж. Х. Конвей н Н. Дж. А. Славя (3. Н. Сопиау апд Н. 3. А. 8)аале, БрЬеге Рас(алйз, Ьазйсез апд Сгоирз (Неи ЪЪгйп Бргп18ег, 1988), 20).) Этн грани достигаются для решеток, парожденньгх векторамн с произвольными действительными координатами. Например, оптимальная решетка для з = 2 будет шестнугольной, порождается она векторамн длиной 2/л/3ш, образующими две стороны равностороннего треугольника. Для размерности 3 оптнмальная решетка порождена векторами 1'и Ъз, 1~з, которые могут иметь внд (о, о, -о), (о, -о, о), (-и, о, о), где о и 1/' л/4гл.
Д, К. Кнллннгбек провел исчерпывающие исследования множнтелей а аэ1шо64, когда ш = 2зз. Он показал, что для множителя о = 2650845021 справедливы равенства кз~ = 4938969760, изд = 2646962, изз — — 68342, из~ = 8778 н и«ц = 1506. Таким образом, он превосходнт другие множители, приведенные в таблице для этого модуля.
Действительно, замечательные значения рь (3 61,4 20, 5 37,8 85, 4 11) превышают все значения рз, /лз, /лз н /лз для всех модулей таблицы. «Г. Связь с критерием серий. В ряде значительных работ, опубликованных в 70-е годы, Гаральд Нндеррейтер (НагаЫ %ебегге1гег) показал, как провцднть ксследовання З-мерных векторов (1) с помощью экспоненцнальных сумм, Одним нз основных результатов его теории было следующее: он показал, что генератор случайных чисел проходит проверку с помощью критерия серий для нескольких измерений, если этот генератор выдерживает проверку спектральным критерием, даже когда вместо полного периода рассматрнваегся большая ега часть. Кратко рассмотрим этот интересный метод для лннейной конгруэнтной последовательности (Хо,о,с,гп) с длиной периода ти. Первое (в дальнейшем — необходимое) понятие — разброс в $ измерениях, т, е.
величина, которую определим квк максимум разности между средины числом н реальным числом бмерных векторов (о:„,х„+1,...,х„.у! 1), попадающих а гипер- прямоугольную область, по всем таким областям. Точнее, если (х„) — последова- тельность целых чисел в области 0 < х„< т, определим (О число (х„,..., х„+1,) в Л для О < и < Х объем Л Р)у П1ОХ Ф т' где Л вЂ” области вида Л = ((Р1," и!) 1 а! < Р! < О1, .
", а! < Р! < д!); (йй) Е ! (и1-у!)и1-у--у(и,-у~)и~ у( т 1 если (х1~ ° ° ~х!) = 1Р11 ° 1Р!)1 ( О, если (х),..., х!) ~ (Р1 „..., Р!). О<т,,...и, <!и Поэтому число векторов (х„,...,х„.и! 1) в Л для О < и < Х, когда область Л определена в (43), может быть выражено следующим образом: 1 йи иь+ Еи +~-!и~ '~~;~и ~~;~, -(у1ЮЧ- +у,!и) т! — Е оба<О! Оби!,...,и~ <!и а! <ю <О! а~ к<у~<А Когда в этой сумме и, = = и! = О, то она равна 11!/т1, умноженному на объем Л.
Следователы)о, 1)м можно выразить, как максимум по Л выражения (!) 1 „и и!+<» уи„+~-!и~ 'и и~ -(у1и!+- -~-у,и~) !у'гп! — .'С о<О<и о<и!,...,и, <и! а!<у!<(1! а,<у~<(й (Ю, .,ию)Е(О,...,О) Поскольку комплексные числа удовлетворяют неравенствам )(О + 4 < (в!) + (4 и (шу~ = (1о~ (х(, справедливы ссютношения Юл() < шах —, 1 Ы (У!и'+ +У ) 9(Н ° Н)) О<и!,...,ию<и1 а!<у!<!У! абебу!<А (и!,...,и,)й(О,...,О) 1 < — ~~"' шах т' и О<и!,...,и„<!и (и!,...,и,)м(о...,,о) -(у1и +--уу,и~) (, и ) :С а~<у~<о~ а1<у~<А Лн), ",н!)Р(н),",н)), о<и!,..., < (и!...и!)ф(О...О) здесь ау и)11 — целые числа из областей О < а < Д) < т для 1 < ( < б Объем Л., очевидно, равен ()11 — а1)...
())! — а!). Чтобы найти разброс Й, °, окинем взглядом 1) все эти множества Л и найдем такое, у которого самое большее илн самое меньшее ЧИСЛО ТОЧЕК ВИДа (Хи,..., Х„У! 1). Верхняя грань разброса может быть найдена с помощью экспоненциальных сумм. Пусть О! = ез"! — первообразный т-й корень из единицы, Если (х1,..., х!) н (Р1,..., Р!) — два вектора с компонентами из области О < х„Р < т, то справедливо равенство где ( ) а„аг+ «+г„тг гггг 1 1,", г а<гг<м д~ ~ ) — Шак ~ г),» „,-Ьгю+--~-Фгаг) 1 и нг' ггг<тг<аг гггбггг<гг =шах — ~~г ы "'ю ...— И Л и й можно упростить в дальнейшем для того, чтобы получить хорошую верхнюю грань длн Пч .
Справедливо равенство (г1 1 ~ 1 „-агг -агг1 га " 1ш ы "-1 1 пг/ыгг — Ц гпв(п(хи/пг)' гг<гг<д где и ф О и сумма < 1, когда и = О, Следователыю, (45) Дим...,и~) < г(иг,,иг), 1 г(иг,...,и,) = П (46) « Кроме того, когда (х„) порождена по модулю ш линейной конгрузнтной последовательностью, справедливы равенства Х„иг+ ° +Х4 Ы гиг =Хггиг+(аХ„+С)ил+ ° ° +(аг гХ„+С(а' т+ ° ° +1))иг — ( 1+низ+ -.+а иг)ха+)г(иг...,,иг), где )г(иы...,иг) не зависит от и.
Значит, у(иы...,иг) = —, ~~г ы'гг"'-'"'г'", а<а<и (47) где Ч(и„..., иг) = и1 + аиз + ° ° ° + а' 1ио (48) Здесь устанавливается связь со спектральным критерием. Покажем, что сумма д(иг г..., и~) будет маленькой, если только не выполняется г7(им..., и~) ез О (по модулю пг); другими словами, вклад суммы (44) определяется, в основном, решением (15). Кроме того, в упр. 27 показано, что г(иг,..., иг) будет малым, когда (иы...,иг) является "большим" решением (15). Следовательно, разброс Ю~',~ будет малым, когда (15) имеет только '"большие" решения, а именно— когда пройдена проверка спектральным критерием.
Осталось определить количественные аналоги зтих качественных утверждений, чтобы осуществлять точные вычисления, Сначала рассмотрим величину д(иы...,ис), Когда Х = пт, так что сумма (47) берется по всему периоду, у(иы..., и~) = О, кроме случая, когда (им..., и~) удовлетворяет уравнению (15). Поэтому разброс ограничен сверху суммой г(иы..., и~), взятой по всем ненулевым решениям (15), Теперь рассмотрим, что произойдет с такой же, как (47), суммой, когда Ю меньше гп и д(иы...,п~) не кратно тп.
Справедливы равенства 1 „,-ьь ~~,„~,+уз 1 1 Х Х т эбь«и эбь<Ф обь<т о<у< ч -х Е (- К ""')' обе< о<и<и где ~,~Ф~+~+1ь (50) о<1< Сейчас Ям = ы"'~Яьэ, поэтому !Ям! = !оьэ! для всех 1, и можно вычислить это общее значение, выполнив зкспоненциальное суммирование: (бьо!' = — ~~~; !Ям!' о<г< 1 ~~~гн+уь ~~~ ' ~,~-*'и-и ПВ О«1(п~ 051<т э<~<та 1 О-ОА ~~ ~ ч ы-х,ы о<!а<ею о<1<л~ 11 Оь ~~~ ~ „~я~ '-Цюы ~-(а~ '-Ое/(а-О из = — 'Е а<в<~ ~<1< о<~< Пусть в — минимальное число среди чисел, для которых а' вз 1 (по модулю пз), и пусть з' = (а' — 1) с/(о — 1) щи га. Тогда з — это делитель ш (см. лемму 3.2.1.2Р) и х„+, — = х„+ уз' (по модулю гл).
Сумма по 1 равна нулю, за исключением случая, когда,~ — 1 кратно з, поэтому получим, что Ао! = гл 0<1< т/а Справедливо равенство з' = д'з, где д' н гл — взаимно простые (см. упр. 3.2.1.2-21), поэтому оказывается, что )( О, если х+ д' й О (по модулю гп/э), '1 т/~~в, если х+ д' п О (по модулю гл/з). Используя эти равенства в (49) и вспомнив неравенство (45), можно показать, что (52) где сумма берется по О < й < ш, такнм, что 5+ о' эз О (по мщулюгп/э).
Если воспользоваться упр. 25, чтобы оценить оставшуюся сумму, то получится, что (53) — ы*" < — — 1пв+О~ —,). Те же грани могут быть использованы, чтобы оценить |Х ' Яе<„<п ыэ*" ) для любого е ф 0 (по модулю т), так как можно заменить т делителем гп, В действительности верхняя грань будет даже меньше, когда о имеет общий делитель с гп, твк как э и гп/~/э, вообще говоря, становятся меньше (см. упр. 26).
Мы доказали, что часть у(иы, ц~) нашей верхней грани разброса (44) мала, когда Х достаточно большое н когда (иы..., цс) не удовлетворяет (15). В упр. 27 доказывается, что часть /(цм..., сч) нашей верхней грани мала, когда сумма берется по всем не равным нулю векторам (и„..., ос), удовлетворяющим (15), и такнм, что этн векторы достаточно далеки от (О,...,0).
Объединив результаты, получим следующую теорему Нндеррейтера (%еоегге1сег). Теорема Р1. Пусть (Х„) — линейная конгруэнтная последовательность (Хе, а, с, ш) с периодом длиной т и пусть в — наименьшее положительное число, такое, что а' гя 1 (по модулю гп). Тогда 1-мерный разброс Рм относительно первых Ю значенпй О) (Х„), кэк определено в (42), удовлетворяет равенствам Ю э Рц1 = О((1ойгп)'г ). (55) Здесь г ®, — максямэльное значение величины г(нэ,..., ос), определенной в (46), которая взята но всем удовлетворяюшим уравнению (15) ненулевым целым векторам (нэ~ ° ~ нс) Доказательсшео. Первые два члена 0 в (54) определяются векторами (иы..., н~) иэ (44), не удовлетворяющими (15), так как в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
