Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 33
Текст из файла (страница 33)
Получим Ь вЂ” ар ьз Ь~ — ар' ьз О (по модулю т) и Ьр' — Ь'р = кт (30) где знак "минус" выбирается для У, только если СГ ) О. $4. [Опережение г.[ Если 1 = Т, алгоритм завершается. (Иначе нужно увеличить 1 на 1. В этой точке (/ и У являются матрицами размера 1 х г, удовлетворяющими (28) и (29), и нх необходимо увеличить, присоединяя подходящие новые столбцы и строки.) Присвоить г +- 1+ 1 и г +- (аг) шоб пт, Присвоить Ц новую строку (-г,0,0,...,0,1) из 1 элементов и присвоить иа +- 0 для 1 < ! < й Присвоить У новую строку (0,0,0,...,0,т).
Окончательно для 1 < ( < 1 присвоить д +- округленное(емг/ш), еи +- ипг — дт и Ц +- Ц + Д(/ь (Здесь "округленное (х)" определено как ближайшее целое к х, например [х+ 1/21. Мы, по сУществУ, пРисваиваем ен +- оп г и непосРедственно пРименаем преобразование (23) с у = г, потому что числа [енг[ настолько велики, что их нужно сразу уменьшить.) Окончательно присвоить э < — пнп(е, са ° сч), к +- г и у <- 1. (На следующем шаге у обозначает индекс текущей строки для преобразования (23), а й — последний такой индекс, когда преобразование укоротит по крайней мере один нз векторов кь) $5. [Преобразовать.) Для 1 < ! < Ф выполнить следующие операции: если ( ф у и 2 [У,. 11[ > 11 ° Уу, то присвоить д +- округление(У,.
Уу / Уу ° Уу), У, <- У1 — дру, (/1 < — (/~ + д(/н в +- пцп(а, (/~ ° (7~) и Й <- у. (Пропускаем преобразование, когда 2[У~ 11[ точно равно У 1'"", в упр. 19 показано, что эта предосторожность удерживает алгоритм от зацикливания. $6. [Опережение Д Если у = 1, присвоить у +- 1; иначе присвоить у <- у + 1.
Если у ~ к, вернуться к шагу $5. (Если ( = к, проходим ! — 1 последовательных циклов без преобразований, так как процесс преобразования "застрял".) $7. [Подготовка поиска.] (Сейчас абсолютный минимум будет установлен путем исчерпывающего поиска по всем (хы...,хс), удовлетворяющим условию (21) леммы А.) Присвоить Х 1: — У ~- (О,...,О), присвоить й +- ! и присвоить (31) для1<у <б (Проверим все Х = (хм...,хс) с [я [ < х1 для 1 < у < 1.
Обычно [х [ < 1, но Л. Киллннгбек (Е. С. К!(!цщЬеск) заметил в 1999 году, что большие значения появляются около 0.00001 раз для всех множителей, когда т = 2~~. Во время перебора вектор У всегда будет равен х1(/1 + + х~Ц, поскольку /(яы..., я~) = У. У. Так как /( — хы..., — хю) = /(ям..., х,), будем проверять только векторы, первая ненулевая компонента которых положительна. Метод, по существу, состоит в том, что.при подсчетах (хм..., хс) рассматривается как цифры в изменяющейся системе счисления со смешанным основанием (2с1 + 1, ..., 2х~ + 1); см.
раздел 4.1.) $8. [Опережение хь.[ Если хь = хы перейти и шагу $10. Иначе — увеличить яь на 1 и присвоить У +- У + (/ы $9. [Опережение к.! Присвоить й й+1. Затем, если й < 1, присвоить ха+- -гы У+- У-2гь(/ь иповторитьшаг$9. Но,еслий > 1, присвоить э < — ппп(а, У.У). $10. [Уменьшение Ц Присвоить к ~- й — 1. Если й > 1„возвратиться к шагу $8. Иначе — выход и~ = /э; перебор заканчивается, и возврат к шагу $4. 3 Практически алгоритм $ применяется, скажем, для Т = 5 или б. Обычно он работает достаточно хорошо, когда Т = 7 или 8, но может быть ужасно медленным при Т > 9, поскольку при переборе время его работы увеличивается как 3~.
(Если минимальное значение 272 достигается в различных точках, то в результате перебора будут найдены все точки. Следовательно, обычно находим, что все хэ = 1 лля большого 1. Как замечено выше, значения 972 вообще непригодны для практического применения, когда 1 большое.) Приведенный ниже пример поможет лучше понять алгоритм Б. Рассмотрим линейную конгруэнтную последовательность, определенную таким образом: гл = 10'о, а = 3141392621, с = 1, Хе = О. (32) Шести циклов алгоритма Евклида на шагах Б2 и БЗ достаточно для доказательства того, что минимальное ненулевое значение яэ9 + хзэ с х1 + 3141592621яэ = 0 (по модулю 10'е) достигается при х2 = 67654, хэ = 226. Следовательно, двумерная точность этого генератора равна 9 = '67634 4 226 67634.277И.
Переходя к размерности 3, найдем минимальное ненулевое значение х9 + ХЭ ~+ я~э, такое, что Х2 + 3141592621хэ + 3141592621эяэ Ьэ О (по модулю 109Е). (зз) На шаге Б4 увеличиваются матрицы -67654 — 226 0'1 /-191 -44190611 256491856991 П = -44190611 191 О), '67 = ~ †2 67654 1307181134), 5793866 33 1 0 0 10000000000 Первая итерация шага Бб с д = 1 для 9 = 2 и д = 4 для 3 = 3 заменяет нх матрицами /-21082801 97 4'1 /-191 -44190611 2564918569 1 Ь7 †441906 191 0 , 17 ~ 35 44258265 9257787485 5793866 33 1 764 176762444 -259674276 (Первая строка У1 на самом деле получается длиннее в этом преобразовании, несмотря на то что строки матрицы У должны стать короче.) следующие 14 итераций шага Б5 дают (у, 472,472, дз) = (2, — 2,:9, О), (3, О, 3, 2), (1,*,-10,-1), (2, -1,*,-6), (3, -1,07*), (1,*,0,2), (2,0,3,-1), (3,3,4,0), (1,*,070), (2,-о,6,0), (3,1,0,*), (1,9,-3,-1), (2,0,~,0), (З,О,О,е).
Сейчас процесс преобразования окончен, но строки матриц стали значительно короче: /- 1479 616 -2777'1 / -888874 601246 -2994234'1 (4' = -3022 104 918 , $' = -2809871 438109 1593689 . (34) -227 -983 -130 -854296 -9749816 -1707736 Найденные пределы (эы ээ, хэ) на шаге Б7 оказываются равными (070,1), поэтому 42э будет самым коротким решением (ЗЗ).
В результате получим и = 07227 4 99У 4- 2М 7027.22039. Для того чтобы найти эту величину, достаточно было лишь нескольких итераций., хотя условие (ЗЗ) выглядит, на первый взг;9яд, устрашающим. Наши вычисления показали, что все точки (У„,У„~.1,(7„+з), произведенные генератором случайных чисел (32) лежат около семейства параллельных плоскостей, отклоняясь на 0.001 единиц, но нет такой системы параллельных плоскостей, которые отличалнсь бы больше чем на 0.001 единиц.
Перебор значений на шагах 68 — 810 редко приводит к значению а. Один такой случай, найденный в 1982 году Р. Кардиным (Е. Саг!шб) и Е. ~Чевин (Е, ьетше), произошел при а = 464680339, т = 2зэ н ! = 5; другой случай произошел когда автор вычислял иээ для строки 21 табл. 1, приведенной ниже в этом разделе. Е, Рейтинги различных генераторов. До сих пор нельзя сказать, будет ли данный генератор случайных чисел на самом деле удовлетворять спектральному критерию.
Успех этого испытания зависит от приложений, так как одни приложения предъявляют более высокие требования, чем другие. Если мы получим, что и~ > 2зер для 2 < 1 < 6, то будет ли этого достаточно для большинства случаю (хотя автор должен признаться, что выбрал критерий отчасти потому, что 30 делится на 2., 3,. 5 и 6). В некоторых случаях хорошо бы иметь правило для определения, удовлетворяет ли датчик критерию, относительно независимое от гп, чтобы можно было сказать, что некоторый множитель хорош либо плох по отношению к другим множителям для заданного т, не проверяя остальных. Разумной мерой, заслуживающей быть показателем для определения, насколько хорош заданный генератор, мог бы быть объем зллипсоида в Ф-мерном пространстве, определенный соотношением (х~ш — хта — . — я~а ) +яэ+ +я, < и,, ~1 э з з э так как этот объем стремится к вероятности того, что точка с ненулевыми целыми координатами.
(ям..., х,), которая соответствует решению (15), находится в эллипсонде. Поэтому предлагаем вычислить этот объем, а именно — показать, что он !жвен яФ/3 Ф "'= Ю) ш' (35) и рассматривать его как меру эффективности множителя а для заданного гп. В этой формуле (-) ! = (-) (- — 1) ... (-) э/я для нечетных Ф. (36) Таким образом, для размерностей, меньших нли равных шести, эта мера имеет следующие значения: иэ = Iгп, Рз = 5~ "эlгп Д4 = '™ ~ ' т з — 1 з 4г дэ ыя ивй~~ Ив 5™6 lш' в т з 1зе Можно сказать, что множитель а удовлетворяет спектральному критерию, если рг равно 0.1 или больше для 2 < 1 < б, и "проходит его, как на зеленый свет", если гч > 1 для всех этих К Малое значение и, указывает, что, вероятно, перед нами— весьма неудачный множитель, так как очень мало решеток будут иметь точки с целыми координатами столь близко к началу координат.
С другой стороны, большое значение р, показывает, что найден необычайно хороший множитель для данного ш, но зто не означает. что случайные чигла являютгя необходимо очень хорошими, так как ш может быть слишком малым. Только истинное значение и~ определяет степень случайности. В табл. 1 показано, какие величины могут появляться в обычных последовательностях, В каждой строке таблицы рассматривается какой-либо фиксированный генератор, и для него приведены значения и~, д~ и "число двоичных разрядов точностнв 18 им В строках 1-4 перечислены генераторы, кзображенные на рис.
2 и 5 из раздела 3.3.1. Генераторы в строках 1 и 2 имеют слишком малый множитель; диаграмма, подобная изображенной на рис. 8, при малых а будет близка к вертикальной "полосе". Ужасный генератор в строке 3 имеет хорошее рз, но очень плохие дз н ре. Подобно всем генераторам с потенциалом 2, он имеет иэ = и'6 и ие = 2 (см. упр. 3). В строке 4 приведен "случайный" множитель. Этот генератор достаточно хорошо удовлетворяет эмпирическим критериям случайности, но его значения рз,..., ре не очень большие. На самом деле значение дэ указывает, что генератор не удовлетворяет нашему критерию, В строке 5 приведен генератор, представленный на рис.
8. Он удовлетворяет спектральному критерию с высокой степенью надежности, когда рассматривать дз — де, но, конечно, ш настолько малб, что числа с трудом могут быть названы случайными; значения и~ ужасно малы. В строке 6 приведен генератор, обсуждавшийся выше, в (32). В строке 7 представлен подобный пример, имеющий ненормально малое значение рз. В строке 8 приведен неслучайный множитель для того же модуля т; все его частичные отношения равны 1, 2 или 3.
Такие множители были предложены И, Борошем (1. Вогоэй) и Г. Нейдерейтером (Н. Вйес)еггейег), поскольку суммы Дедекинда в этом случае особенно малы н дают хорошие результаты при проверке двумерным критерием серий (см. раздел 3.3.3 и упр. 30). Для генератора строки 8 имеется только одно частичное отношение '3', не существует множителей, конгруэнтных 1 по модулю 20, частичные отношения которых относительно 10'е равны толькб 1 или 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
