AOP_Tom2 (1021737), страница 23
Текст из файла (страница 23)
Во время перебора вектор У всегда будет равен к~У~ + . + хромо поскольку /(хм..., л~) = У У. Так как /( — кы..., — х,) = /(хы..., х,), будем проверять только векторы, первая ненулевая компонента которых положительна. Метод, по существу, состоит в том, что.при подсчетах (хм..., ач) рассматривается как цифры в изменяющейся системе счисления со смешанным основанием (2г~ + 1, ..., 2л, + 1); см. раздел 4.1.) Б8. [Опережение зы] Если хь = зь, перейти к шагу Я10. Иначе - — увеличить хь на 1 и присвоить У ,'— У+ 1/ы Б9.
[Опережение й.] Присвоить и ь- й+ 1. Затем, если и < т, присвоить хь е- -зы У е- У вЂ” 2зьоь и повторить шаг 89. Но, если и > г, присвоить а +- пип(в, 1' 1'). Б10. [Уменыпение к.] Присвоить и ~ — 1г — 1. Если й > 1, возвратиться к шагу Я8. Иначе .— выход и~ —— ,/в; перебор заканчивается, и возврат к шагу Я4. ! Практически алгоритм Я применяется, скажем, для Т = 5 или 6.
Обычно он работает достаточно хорошо, когда Т = 7 или 8, но может быть ужасно медленным при Т > 9, поскольку при переборе время его работы увеличивается как Зт. (Если минимальное значение иг достигается в различных точках, то в результате перебора будут найдены все точки. Следовательно, обычно находим, что все хь = 1 для большого !. Как замечено выше, значения 878 вообще непригодны для практического применения, когда ! большое.) Приведенный ниже пример поможет лучше понять алгоритм В.
Рассмотрим линейную конгруэнтную последовательность, определенную таким образом: оп = 10!о а = 3141592621, с = 1, Ло —— О. (32) Шести циклов алгоритма Евклида на шагах Я2 и БЗ достаточно для доказательства того, что минимальное ненулевое значение хэ + хэ эс хг + 314159262122 = О (по модулю 10'о) достигается при хг = 67654,хэ = 226. Следовательно, двумерная точность этого генератора равна = 4 67664'': 226' 67664.27748.
Переходя к размерности 3, найдем минимальное ненулевое значение хг + хэ + хэ~, такое, что хг + 3141592621хг + 3141592621~хо = О (по модУлю 10'о), (33) На шаге Б4 увеличиваются матрицы -67654 -226 088 /-191 -44190611 25649!8569 1 (7 = †441906 191 О) 7 !' = -226 67654 1307181134) . 5793866 ЗЗ 1 О О 1ОООООООООО Первая итерация шага Я5 с д = 1 для 8' = 2 и 77 = 4 для з = 3 заменяет нх матрицами /-21082801 97 4'1 /-191 -44190611 2564918569'! Ьг = — 44190б11 19! О , !7 Эб 442бвэбб 1287737438 5793866 ЗЗ 1 764 176762444 -259674276 (Первая строка 172 на самом деле получается длиннее в этом преобразовании, несмотря на то что строки матрицы 1г' должны стать короче.) Следующие 14 итераций шага Я5 дают (7', дг,дг,478) = (2, — 2, з, О), (3, О, 3,*), (1, 4, -10, -1), (2, -1, э, -6), (3, -1, О, *), (1, *, О 7 2), (2, О, э, -1), (3, 3, 4, з ), (1., 4 7 0, О), (2,— 5,4, О), (3,1,0,*), (174,— 3,— 1), (2,0,4,0), (З,О,О,э).
Сейчас процесс преобразования окончен, но строки матриц стали значительно короче: /-1479 616 -277786 / -888874 601246 -2994234 1 (77 = -3022 104 918 , Ъ" = -2809871 438109 1593689 . (34) -227 -983 -130 -854296 -9749816 †17077 Найденные пределы (хг, хю хэ) на шаге 87 оказываются равными (0,0, 1), поэтому (78 будет самым коротким решением (33). В результате получим , = 77227* 4 68з'4-786' 7677.27688. Для того чтобы найти эту величину, достаточно было лишь нескольких итераций, хотя условие (33) выглядит, на первый взгляд, устрашающим.
Наши вычи<щения показали, что все точки (17„,(/„4.8,(/„.62), произведенные генератором случайных чисел (32) лежат около семейства параллельных плоскостей, отклоняясь на 0.001 единия, но нет такой системы параллельных плоскостей, которые отличались бы больше чем на 0.001 единиц. Перебор значений на шагах 88 — 810 редко приводит к значению э.
Один такой случай, найденный в 1982 году Р. Карлиным (В. Сагйпй) и Е. Левин (Е. Ьетспе)» произошел при а = 464680339, т = 222 и 2 = 5; другой случай произошел, когда автор вычислял иг для строки 21 табл. 1, приведенной ниже в этом разделе. Е. Рейтинги различных генераторов. До сих пор нельзя сказать, будет ли данный генератор случайных чисел на самом деле удовлетворять спектральному критерию.
Успех этого испытания зависит от приложений, так как одни приложения предъявляют более высокие требования, чем другие. Если мы получим, что ис > 22э1» для 2 < 2 < 6, то будет ли этого достаточно для большинства случаен (хотя автор должен признаться, что выбрал критерий отчасти потому, что 30 делится на 2, 3, 5 и 6). В некоторых случаях хороню бы иметь правило для определения, удовлетворяет ли датчик критерию, относительно независимое от т, чтобы можно было сказать, что некоторый множитель хорош либо плох по отношению к другим множителям для заданного т, не проверяя остальных.
Разумной мерой, заслуживающей быть показателем для определения, насколько хорош заданный генератор, мог бы быть обьем эллипсоида в 2-мерном пространстве, определенный соотношением (хст — хга †.. — хса ) +хг+ +х» < и,, С вЂ” 12,2 2 2 так как этот объем стремится к вероятности того, что точка с ненулевыми 44елмми координатами.(хс,..., хс), которая соответствует решению (15), находится в эллипсоиде. Поэтому предлагаем вычислить этот объем, а именно — показать, что он равен С/2 С 7» ис 35 (1/2)! т ' ( ) н рассматривать его как меру эффективности множителя а для заданного т. В этой формуле (-)! = (-) (- — 1) ...
( †)4/х для нечетных Ь (36) Таким образом, для размерностей, меньших или равных шести, эта мера имеет следующие значения: И2 — яиг/т~ 1»з — заиг/т~ 1»4 2я с»4»т~ г 4 2 1 2 4» Можно сказать, что множитель а удовлетворяет спектральному критерию, если 1»с равно 0.1 или болыпе для 2 < 1 < 6, и "проходит его, как на зеленый свет", если 1»» > 1 для всех этих Ь Малое значение р, указывает, что, вероятно, перед нами— весьма неудачный множитель, так как очень мало решеток будут иметь точки с целыми координатами столь близко к началу координат. С другой стороны, большое значение 1»» показывает, что найден необычайно хороший множитель для данного т, но это ие означает, что случайные числа являются необходимо очень хорошими, так как гп может быть слипжом малым. Только истинное значение иг определяет степень случайности, В табл. 1 показано, какие величины могут появляться в обычных последовательностях.
В каждой строке таблицы рассматривается какой-либо фиксированный генеРатоР, и длЯ него пРиведены значениЯ иге, Ай и "число двоичных РазРЯдов точности" 18иг. В строках 1 — 4 перечислены генераторы, изображенные на рис. 2 и 5 из раздела 3.3.1. Генераторы в строках 1 и 2 имеют слишком малый множитель; диаграмма, подобная изображенной на рис. В, при малых а будет близка к вертикальной "полосе". Ужасный генератор в строке 3 имеет хорошее дэ, но очень плохие ггэ и де. Подобно всем генераторам с потенциалом 2, он имеет иэ — — 46 и и4 = 2 (см. упр.
3). В строке 4 приведен "случайный" множитель. Этот генератор достаточно хорошо удовлетворяет эмпирическим критериям случайности, но его значения рэ,..., ггэ не очень большие. На самом деле значение дэ указывает, что генератор не удовлетворяет нашему критерию. В строке 5 приведен генератор, представленный на рис. В.
Он удовлетворяет спектральному критерию с высокой степенью надежности, когда рассматривать ггэ — де, но, конечно, пг настолько малб, чта числа с трудом могут быть названы случайными; значения ыг ужасно малы. В строке 6 приведен генератор, обсуждавшийся вьппе, в (32). В строке 7 представлен подобный пример, имеющий ненормально малое значение дэ. В строке 8 приведен неслучайный множитель для того же модуля т; все его частичные отношения равны 1, 2 или 3. Такие множители были предложены И.
Борошем (1. ВогоэЬ) и Г. Нейдерейтером (Н. %ег1егге!гег), поскольку суммы Дедекинда э этом случае особенно малы и дают хорошие результаты при проверке двумерным критерием серий (см. раздел З.З.З и упр. 30). Для генератора строки 8 имеется только одно частичное отношение '3'1 не существует множителей, конгрузнтных 1 па модулю 20, частичные отношения которых относительно 10'е равны тольк6 1 или 2. Генератор, прннеденный в строке и, имеет другой множитель, который специальна ныбрен с плохими намерениями, как предложил Вотерман (Жасегшап). Он гарантирует достаточно большое значение рэ (см. упр.
11). Строка 10 интересна, поскольку указанный в ней генератор имеет большое значение дэ при очень малом значении ггэ (см. упр. 8). Строка 11 табл. 1 — это воспоминание о старых добрых временах: данный генератор когда-то широко использовался, после того как ега предложила О. Таусски (О.
Таиээ1гу) в начале 50-х годов. На компьютеры, для которых модуль равнялся примерно 2э', начали утрачивать популярность в конце 60-х и почти полностью пропали в 80-е годы, когда получили распространение машины с 32-разрядной арифметикой. Так, сравнительно малые размеры компьютерного слова были заменены сравнительно большими заботами. В строке 12 содержится, увы, генератор, который действительно использовался на таких машинах в последнее десятилетие (90-е годы) в научных компьютерных центрах мира. Его истинное имя — йАИР0 (похоже на егапдоше — "случайный".
— Прим. ред.), и этага достаточно, чтобы вызвать испуг в глазах и спазмы в желудке у многих ученых, специализирующихся на компьютерах! Действительно, генератор определен следующим образом: Ле нечетное, Л„ег — — (65539Х„) шгк1 2з'. (37) Таблица 1 ВЫБОРОЧНЫЕ РЕЗУЛЬТАТЫ ПРИМЕНЕНИЯ СПЕКТРАЛЬНОГО КРИТЕРИЯ мз 2 Строка В упр. 20 показано, что 220 — подходящий модуль для спектрального критерия. Так как 9Մ— 6Х„.,! + Х„чг = 0 (по модулю 23'), генератор не удовлетворяет большинству трехмерных критериев случайности и его никогда не следовало бы использовать. Почти любой множитель = 5 (по модулю 8) был бы лучше.
(Любопытный факт относительно КАИЩ.отмеченный Госпером (Соврет)! состоит в том, что мв —— мз = мб = мт = мв = !'0 = н7116. Следовательно., )40 равно эффективному значению 11.98.) Строки 13 и 14 — это множители Вороша-Нидеррейтера (Вогез)2-Мег)еггейсг) и Вотермана ( 1110!еггпап) для модуля 23'.
В строках 16 и 23 расположены генераторы Лаво (1 анапх) и Йенсена (3апввепв); параметры этих генераторов были найдены на компьютере, чтобы получить хороший множитель в смысле спектрального критерия, для которого рг принимает очень большое значение.
В строке 22 находится генератор с множителем, используемым при с = 0 и т = 2; он содержится в биб- , 4В. лиотеке компьютера Сгау Х-МР. В строке 26 содержится генератор, предложенный Хайнесом (Наупев) (его превосходный множитель 6364136223846793005 настолько велик, что не поместился в столбце таблицы!). Генератор строки 15 предложен Дж. Марсалья (С. Ма!бай!!а) в качестве "кандидата на наилучший множитель", 1 2 1 4 5 б 7 8 9 1О 1.1 12 !3 !4 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 23 22+1 2!в+! 3141592653 137 3141592621 3141592221 4219755981 4160984121 224 ! 213 ! 5 513 216 ! 1812433253 156608394! 69069 1664525 314159269 62089911 16807 48271 40692 44485709377909 31167285 См. (38) См.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
