AOP_Tom2 (1021737), страница 20
Текст из файла (страница 20)
Например, на рис. 8 показано множество точек в типичных случаях малых размерностей 2 и 3 для генератора с а(х) = (137х + 187) шос1 256. (4) Конечно, генератор с периодом длиной 256 едва ли будет случайным, но 256 достаточно мало, чтобы можно было начертить диаграммы и достичь некоторого понимания ситуации, прежде чем перейти к большим т, представляющим практический интерес. Возможно, наиболее поразительным в схеме коробочек на рис. 8, (а) есть то. что их можно покрыть достаточно малым числом параллельных линий.
На самом деле существует много различных семей параллельных линий, проходящих через все точки. Например, семейство, содержащее 20 приблизительно вертикальных линий, пройдет через все точки; семейство, содержащее 21 параллельную линию,. наклоненную примерно под углом 30', также пройдет через все эти точки. Вообще говоря, подобное явление наблюдается в старых садах, посаженных по некоторой системе. Тот же генератор, рассмотренный в трех измерениях, дает 256 точек в кубе, полученных путем присоединения компонентов "второго порядка' з(в(х) ) к каждой из 256 точек (х, в(х)) на плоскости рнс. 8, (а), как показано на рис.
8, (Ъ). Представим себе, что эта 3-В-кристаллическая структура построена, как физическая модель, а именно — как куб, который мы можем вертеть в руках, как хотим, при этом можно заметить, что существуют различные семейства параллельных плоскостей, которые проходят через все данные точки. По словам Уоллеса Живена (%а)1асе 61уепз), случайность чисел проявляется "главным образом, на плоскостях".
На первый взгляд может показаться, что такое систематическое поведение является настолько неслучайным,что конгруэнтные генераторы совершенно несостоятельны. Однако, если задуматься и вспомнить, что на практике т будет существенно больше, можно прийти к лучшему пониманию этого явления. Регулярную структуру на рис. й, а именно "зернистость", можно увидеть, если понаблюдать за случайными числами через мощный микроскоп. Если рассмотреть настоящие случайные числа между 0 и 1 и так округлить либо урезать их с ограниченной точностью, чтобы каждое из них было равно целому числу, умноженному на 1/и для некоторого заданного чиста и, то Ф-мерные точки, полученные по правилу (1), будут иметь весьма регулярный характер (еслн смотреть на них под микроскопом).
Пусть 1/иэ — максимальное расстояние между линиями всех семейств параллельных линий, которые проходят через двумерные точки ((х/т, а(х)/гп) ). Назовем иэ двумерной гпочностъю генератора случайных чисел, так как пары последовательных чисел имеют хорошую структуру, которая особенно хороша относительно им Аналогично пусть 1/иэ — - максимальное расстояние между плоскостями из семейств параллельных плоскостей, проходящих через все точки ((х/т, а(я)/ш, а(а(л))/гп)); назовем из точностью в трех измерениях.
1-мерная точность к~ равна величине, обратной минимальному расстоянию между гиперплоскостями из семейств параллельных (1 — 1)-мерных гиперплоскостей, проходящих через все точки ((т/т, а(х)/тп, ..., ай 0(х)/т) ). Существенная разница между периодическими последовательностями н настоящими последовательностями, члены которых "урезаны" до кратных 1/и чисел, состоит в том, что точность настоящих случайных последовательностей одна и та же во всех размерностях, а точность периодических последовательностей убывает, когда 8 растет. На самом деле, так как в 1-мерном кубе находится только т точек. когда т — длина периода, мы не можем получить 1-мерную точность, ббльшую, чем примерно ш'д. 14огда нас интересует, будут ли 1 последовательных значений независимы, компьютерный генератор случайных чисел будет вести себя, в сущности, так, как будто это настоящие случайные числа, и будет урезать их до 1б ю двоичных разрядов, где и, убывает с возрастанием к На практике подобное изменение точности нас вполне устраивает.
Не будем настаивать на том, чтобы 10-мерная точность была равна 2зэ в гом смысле, что все (2зт)'в возможные 10-мерные строки (С"„,бк+м..., б' +э) должны быть равновероятны на 32-разрядной машине. Для таких болыпнх значений 1 необходимо только, чтобы несколько старших разрядов (П„П, ы, Г ~.~-~) вели себя так, как если бы они были независимыми случайными величинами.
С другой стороны, когда для приложений нужен генератор случайных чисел, обегпечивающий получение последовательности, очень близкой к случайной, простые конгруэнтные генераторы для этого ие подходят. Вместо них нужно использовать генератор с длинным периодом, даже если на самом деле необходимо генерировать только малую часть периода.
Если длину периода возвести в квадрат, то, по существу, будет возведена в квадрат и точность в больших измерениях, т. е. эффективное число точных разрядов удвоится. Спектральный критерий основан на значении ис для малых й скажем, 2 < 1 < 6. Размерности 2, 3 н 4, кажется, адекватны для определения важных недостатков в последовательности. Но так как здесь рассматривается целый период, разумно в некоторой степени быть осторожными н перейти к другому измерению (или двум).
С другой сторонь<, значения и~ при 1 > 10, кажется, не имеют практического значения. (И это хорошо, поскольку было бы очень трудно вычислить точность км когда 1 > 10.) Существует не вполне ясная зависимость между спектральным критерием н критерием серий. Например, частный случай критерия серий для целого периода, рассмотренный в упр. 3.3.3 — 19, подсчитывает число ячеек в каждом из 64 подквадратов (см. рис. 8, (а)). Основная разница состоит в том, что спектральный критерий вращает точки до тех пор, пока не определит наименее благоприятную ориентацию.
Ниже в этом разделе мы еще возвратимся к критерию серий. Может показаться, что достаточно применить спектральный критерий только для одного довольно большого значения б Если генератор пройдет проверку критерием с тремя измерениями, то кажется правдоподобным, что он пройдет проверку и 2-О-критерием; следовательно, эту проверку можно не делать. Такие рассуждения ошибочны, поскольку не учтено то, что мы требуем более жестких ограничений при более низких размерностях. Подобная ситуация наблюдается при использовании критерия серИй. Рассмотрим генератор, у которого почти то же количество точек попадает в каждый подкуб единичного куба, когда единичный куб разделен на 64 подкуба размера -' х -' х -'. Тот же генератор ..ожет дать полностью пуспюй подквадрат единичного квадрата, когда единичный квадрат делится на 64 подквадрата размера — х э.
Таким образом, средние значения при низких измерениях 1 ! увеличиваются и для каждого измерения требуется отдельная проверка. Не всегда выполняется неравенство и~ ( гп'7', хотя гпьп будет верхней гранью для прямоугольной решетки. Например, оказывается, что из = з/274 ) з/256 на рис. В, поскольку приблизительно шестиугольная структура объединяет т точек так, что возможно строго прямоугольное упорядочение.
Чтобы построить алгоритм, который эффективно подсчитывает ио следует более глубоко разобраться в необходимой для этого математической теории. Поэтому читатель, которого не интересуют математические обоснования, может перейти сразу к части О этого раздела, в которой спектральный критерий будет представлен как "общий" метод, сопровождаемый некоторыми примерами. Однако для математического обоснования спектрального критерия необходимо знать только элементарные преобразования векторов.
Некоторые авторы предлагают использовать минимальное число Л, параллельных линий или гиперплоскостей, проходящих через все точки, вместо максимального расстояния 1/ю между ними. Однако число Х, не кажется таким важным, как понятие точности, определенное вьшш, поскольку оно имеет смещение, зависящее от величины отклонения этих линий или гиперплоскостей от координатных осей куба.
Например, приблизительно 20 вертикальных линий, проходящих через все точки на рис. 8, (а), дают действительно 1/~/328 единиц в соответствии с формулой (14), которая приводилась ниже: (им из) = (18, — 2). Поэтому можно ошибочно принять, что точность равна ~/328 или, возможно, даже 20. Истинная точность, равная з/274, реализуется только для большого семейства из 21 линии с наклоном 7/15; другое семейство из 24 линий с наклоном -11/И также имеет большие расстояния между линиями, чем семейство из 20 ливий, поскольку 1/з/290 > 1/~/328.
Способ, с помощью которого семейства линий располагаются относительно границ единичного гиперкуба, кажется, не является каким-либо особенно "чистым" или значащим критерием. Однако те, кто предпочитают считать гиперплоскости, могут подсчитывать Хо используя метод, весьма похожий на тот, с помощью которого мы будем подсчитывать и1 (см. упр. 16).
ьВ. Дальнейшее исследование критерии. Анализ основного множества (2) начнем с наблюдения 1 ) /аух+ (1+ а+. + ау ~)с'1 ~ шод1. От "модуля 1" можно избавиться, выполнив операцию, с помощью которой множество удлиняется периодически, и сделав бесконечное множество копий исходною 1-размерного гиперкуба во всех направлениях. Это дает множество ~ух э(х) ай О(х) ~ — + 1см — + йг ° °, + йг) ) целое х, йг, )сг,..., )с~ ~ т т ' т ух ах аг-гх = (Уе+ ~ — +Вы — + Юг,..., +1з) ~ целое х,йг,йг,...,Ц), т т т Уе — — — (О, с, (1+а)с, ..., (1+а+ +а' г)с) 1 (б) является вектором констант.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
