Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 30
Текст из файла (страница 30)
Спектральный критерий В этом разделе рассматривается особенно важный метод проверки качества линейных коигруэитных генераторов случайных чисел. Все хорошие генераторы проходят проверку спектральным критерием; все генераторы, известные сейчас как плохие, фактически провалились при этой проверке. Таким образом, спектральный критерий является наиболее мощным известным до сих пор критерием и заслуживает особого внимания. В процессе обсуждения будут выяснены те ограничения иа степени случайности, которые ие могут быть преодолены при использовании линейных коигруэнтных последовательностей и их обобщений. Спектральный критерий обладает свойствами как теоретических, так и эмпирических критериев, рассмотренных в предыдущих разделах.
Он похож и ив теоретические критерии, поскольку проверяет свойства последовательности иа полном периоде, и иа эмпирические критерии, поскольку для получения результата требует вычислеиий иа компьютере. А. Идеи, слулппцие обоснованием критерия. Наиболее важные испытания для проверки, насколько случайной будет последовательность, связаны со свойствами совместиых распределений г последовательных элементов последовательности, и спектральный критерий как раз и используется для проверки гипотез об этих распределениях. Если задаиа последовательность (У„) с периодом пг, то для построения критерия необходимо проанализировать множество всех гп точек в Ьмериом,пространстве.
Для простоты предположим, что задана ливейиая коигруэитиая последовательность (Хо,и,с,т) с максимальным периодом длиной т (так что с ф О) или что 1п — простое число и с = О, а период имеет длину гп — 1. В последнем случае прибавим точку (0,0,...,О) к множеству (1), чтобы всегда было ровио ш точек. Эта дополиительная точка почти ие влияет иа общую ситуацию, когда гп большое, и делает теорию более простой. При таком предположении (1) можно переписать следующим образом: ( — (х, в(х), в(в(х)), ..., в(' ~)(х)) ~ 0 < х ( пт~, где в(х) = (ах+с) шобпт (3) представляет собой элемент, следующий за х. Здесь рассматривается лишь множество всех таких точек в Г-мерном пространстве, а не порядок, в котором оии ва самом деле генерируются.
Но порядок генерирования отражен в зависимости меислу ОООО Оо О Оп ОП . ра Прап ао Прапор О ОООО ОООО ОО Ооо. апра Оа О Оа рооп Оп О О р О Оп О рО Оооо ОООО ОО !О ОО а ОО ап О апа оооо оооо Оп апа о О а а а а Га аппо порпора Опп аО Парр Опааопп П арпа Оооо Оа а аа О О О а О Оа ОООО аппо аа Опа а аа О "па аа а Оа папа а р !О..П а. а аа а аа. ' ао апОО ао О Оп п' ф Ф ффф а(в ф е1 фв Ф Ф ф Ф Ф '. ф фф а Ъ Ф % Ф ф Ф Ф Ф Ф ф Ф ф з(з(х)) х (а) Рис. 6.
(О) Двумерная решетка„ Образованная всеми парами после- довательных точек (Л„, Л„.~|), где (Ь) Х.е, = (137Х. + 187) 6256. (Ь) Трехмерная решетка трехмерных строк (Х,Х .~пХ~+з). компонентами векторов, и спектральный критерий изучает такую зависимость для различных размерностей ! со всеми точками вида (2). Например, на рис. 8 показано множество точек в типичных случаях малых размерностей 2 и 3 для генератора с (4) е(х) = (137я+ 187) шоб 256.
Конечно, генератор с периодом длиной 256 едва ли будет случайным. но 256 достаточно малб, чтобы можно было начертить диаграммы и достичь некоторого понимания ситуации, прежде чем перейти к большим т, предсщвляющиы практический интерес. Возможно, наиболее поразительным в схеме коробочек на рис. 8, (а) есть то, что их можно покрыть достаточно малым числом параллельных линий. На самом деле существует много различных семей параллельньгх линий, проходящих через все точки. Например, семейство, содержащее 20 приблизительно вертикальных линий, пройдет через все точки; семейство, содержащее 21 параллельную линию, наклоненную примерно под углом 30', также пройдет через все эти точки. Вообще говоря, подобное явление наблюдается в старых садах„посаженных но некоторой системе.
Тот же генератор, рассмотренный в трех измерениях, дает 256 точек в кубе, полученных путем присоединения компонентов "второго порядка" з(е(х)) к каждой из 256 точек (ф, е(х)) на плоскости рис. 8, (а), как показано на рис. 8, (Ь). Представим себе, что эта 3-11-кристаллическая структура построена, как физическая модель, а именно — как куб, который мы можем вертеть в руках, как хотим; при этом можно заметить, что существуют различные семейства параллельных плоскостей, которые проходят через все данные точки. По словам Уоллеса Жпвеиа (%а!!асе С4гепэ), случайность чисел проявляется "главным образом, на плоскостях".
На первый взгляд может показаться, что такое систематическое поведение является настолько неслучайным, что конгрузнтные генераторы совершенно несостоятельны. Однако, если задуматься и вспомнить, что на практике щ будет существенно больше, можно прийти к лучшему. пониманию этого явления. Регулярную структУрУ на рис. 8, а именно "зернистость", можно увидеть, если понаблюдать эа случайными числами через мощный микроскоп.
Если рассмотреть настоящие случайные числа между 0 и 1 и так округлить либо урезать их с ограниченной точностью, чтобы каждое из них было равно целому числу, умноженному на 1/к для некоторого заданного числа и, то 1-мерные точки, полученные по правилу (1), будут иметь весьма регулярный характер (если смотреть на ннх под микроскопом). Пусть 1/ит — максимальное расстояние между линиями всех семейств параллельных линий, которые проходят через двумерные точки ((х/т, е(х)/гп)).
Назовем иэ двумерной шочносшью генератора случайных чисел, так как пары последовательных чисел имеют хорошую структуру, которая особенно хороша относительно ит. Аналогично пусть 1/из — максимальное расстояние между плоскостями из семейств параллельных плоскостей, проходящих через все точки ((х/гп, я(х)/т, в(в(х))/т) ); назовем ив точностью в трех измерениях. 1-мерная точность и~ равна величине, обратной минимальному расстоянию между гиперплоскостями нз семейств параллельных (г — 1)-мерных гнперплоскостей, проходящих через все точки ((х/т, «(я)/т... вй 0(х)/т)11.
Сун~ественная разница между периодическими последовательностями и настоящими последовательностями, члены которых "урезаны" до кратных 1/и чисел, состоит в том, что точность настоящих случайных последовательностей одна и та же во всех размерностях, а точность периодических последовательностей убывает, когда 1 растет. На самом деле, так как в 1-мерном кубе находится только то точек, когда т — длина периода, мы не можем получить 1-мерную точность, ббльшую, чем примерно т' '.
Когда нвс интересуег, будут ли $ последовательных значений независимы, компьютерный генератор случайных чисел будет вести себя, в сущности, так, как будто зто настоящие случайные числа, и будет урезать их до 1б и~ двоичных разрядов, где и~ убывает с возрастанием б На практике подобное изменение точности нас вполне устраивает. Не будем настаивать на том, чтобы 10-мерная точность была равна 2зэ в том смысле, что все (2зэ)ю возможные 10 мерные строки (0' . б'„+м..., Кь+э) должны быть равновероятны на 32-рвзрядной машине. Для таких больших значе. ннй 1 необходимо только, чтобы несколько старших разрядов ((/ь. К + м, (/а+~-~ ) вели себя так, как если бы они были независимыми случайнымн величинами. С другой стороны, когда для приложений нужен генератор случайных чисел, обеспечивающий получение последовательности, очень близкой к случайной, простые конгруэитные генераторы для этого не подходят.
Вместо них нужно использовать генератор с длинным периодом, даже если на самом деле необходимо генерировать только малую часть периода. Если длину периода возвести в квадрат, то, по существу, будет воэнедена в квадрат и точность в больших измерениях, т. е. эффективное число точных разрядов удвоится. Спектральный критерий основан на значении ьт для малых 1, скажем, 2 < 1 ~ б. Размерности 2, 3 н 4„кажется, адекватны для определения важных недостатков в последовательности. Но так как здесь рассматривается целый период, разумно в некоторой степени быть осторожными н перейти к другому измерению (нли двум).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
