структуру на рис. 8, а именно "зернистость", можно увидеть, если понаблюдать за случайными числами через мощный микроскоп. Если рассмотреть настоящие случайные числа между О и 1 и так округлить либо урезать их с ограниченной точностью, чтобы каждое из них было равно целому числу, умноженному на l/v для некоторого заданного числа и, то f-мерные точки, полученные по правилу (1), будут иметь весьма регулярный характер (если смотреть на них под микроскопом).

Пусть l/i/2 - максимальное расстояние между линиями всех семейств параллельных линий, которые проходят через двумерные точки {(х/т, s(a;)/m)}. На-" зовем U2 двумерной точностью генератора случайных чисел, так как пары последовательных чисел имеют хорошую структуру, которая особенно хороша относительно 1/2. Аналогично пусть I/1/3 - максимальное расстояние между плоскостями из семейств параллельных плоскостей, проходящих через все точки {[х/т, s{x)/m, s(s(a;))/m)}; назовем V3 точностью в трех измерениях, f-мерная точность Ut равна величине, обратной минимальному расстоянию между гиперплоскостями из семейств параллельных {t - 1)-мерных гиперплоскостей, проходящих через все точки {{х/т, s{x)/m, s~{x)/m)}.

Существенная разница между периодическими последовательностями и настоящими последовательностями, члены которых "урезаны" до кратных l/v чисел, состоит в том, что точность настоящих случайных последовательностей одна и та же во всех размерностях, а точность периодических последовательностей убывает, когда t растет. На самом деле, так как в t-мерном кубе находится только m точек, когда т - длина периода, мы не можем получить f-мерную точность, большую, чем примерно т/*.

Когда нас интересует, будут ли t последовательных значений независимы, компьютерный генератор случайных чисел будет вести себя, в сущности, так, как будто это настоящие случайные числа, и будет урезать их до Ig Ut двоичных разрядов, где Ut убывает с возрастанием t. На практике подобное изменение точности нас вполне устраивает. Не буде.м настаивать на том, чтобы 10-мерная точность была равна 2 в том смысле, что все (2) возможные 10-мерные строки ((7„, C/„+i,..., „+9) должны быть равновероятны на 32-разрядной машине. Для таких больших значений t необходимо только, чтобы несколько старших разрядов ([/„, U„+i,..., Un+t-i) вели себя так, "как если бы они были независимыми случайными величинами.

С другой стороны, когда для приложений нужен генератор случайных чисел, обеспечивающий получение последовательности, очень близкой к случайной, простые конгруэнтные генераторы для этого не подходят. Вместо них нужно использовать генератор с длинным периодом, даже если на самом деле необходимо генерировать только малую часть периода. Если длину периода возвести в квадрат, то, по существу, будет возведена в квадрат и точность в больших измерениях, т. е. эффективное число точных разрядов удвоится.

Спектральный критерий основан на значении ut для малых t, скажем, 2 < i < 6. Размерности 2, 3 и 4, кажется, адекватны для определения важных недостатков в последовательности. Но так как здесь рассматривается целый период, разумно в некоторой степени быть осторожными и перейти к другому измерению (или двум). С другой стороны, значения ut при t > 10, кажется, не имеют практического значения. (И это хорошо, поскольку было бы очень трудно вычислить точность Ut, когда t > 10.)

Существует не вполне ясная зависимость между спектральным критерием и критерием серий. Например, частный случай критерия серий для целого периода, рассмотренный в упр. 3.3.3-19, подсчитывает число ячеек в каждом из 64 подквадра-тов (см. рис. 8, (а)). Основная разница состоит в том, что спектральный критерий вращает точки до тех пор, пока не определит наименее благоприятную ориентацию. Ниже в этом разделе мы еще возвратимся к критерию серий.

Может показаться, что достаточно применить спектральный критерий только для одного довольно большого значения t. Если генератор пройдет проверку критерием с тремя измерениями, то кажется правдоподобным, что он пройдет проверку и 2-В-критерием; следовательно, эту проверку можно не делать. Такие рассуждения ошибочны, поскольку не учтено то, что мы требуем более жестких ограничений при более низких размерностях. Подобная ситуация наблюдается при использовании критерия серий. Рассмотрим генератор, у которого почти то же количество точек попадает в каждый подкуб единичного куба, когда единичный куб разделен на 64 подкуба размера j х j х . Тот же генератор .южет дать полностью пустой подквадрат единичного квадрата, когда единичный квадрат делится на 64 подква-драта размера х . Таким образом, средние значения при низких измерениях увеличиваются и для каждого измерения требуется отдельная проверка.

Не всегда выполняется неравенство щ < m/ хотя m/ будет верхней гранью для прямоугольной решетки. Например, оказывается, что 2 = л/274 > л/256 на рис. 8, поскольку приблизительно шестиугольная структура объединяет т точек так, что возможно строго прямоугольное упорядочение.

Чтобы построить алгоритм, который эффективно подсчитывает щ, следует более глубоко разобраться в необходимой для этого математической теории. Поэтому читатель, которого не интересуют математические обоснования, может перейти сразу к части D этого раздела, в которой спектральный критерий будет представлен как "общий" метод, сопровождаемый некоторыми примерами. Однако для математического обоснования спектрального критерия необходимо знать только элементарные преобразования векторов.

Некоторые авторы предлагают использовать минимальное число Nt параллельных линий или гиперплоскостей, проходящих через все точки, вместо максимального расстояния l/t/t между ними. Однако число Nt не кажется таким важным, как понятие точности, определенное выше, поскольку оно имеет смещение, зависящее от величины отклонения этих линий или гиперплоскостей от координатных осей куба. Например, приблизительно 20 вертикальных линий, проходящих через все точки на рис. 8, (а), дают действительно 1/\/328 единиц в соответствии с формулой (14), которая приводилась ниже: (мМг) = (18,-2). Поэтому можно ошибочно принять, что точность равна \/328 или, возможно, даже 20. Истинная точность, равная \/274, реализуется только для большого семейства из 21 линии с наклоном 7/15; другое семейство из 24 линий с наклоном -11/13 также имеет большие расстояния между линиями, чем семейство из 20 линий, поскольку 1/\/290 > 1/л/328. Способ, с помощью которого семейства линий располагаются относительно границ единичного гиперкуба, кажется, не является каким-либо особенно "чистым" или значащим критерием. Однако те, кто предпочитают считать гиперплоскости, могут подсчитывать Л, используя метод, весьма похожий на тот, с помощью которого мы будем подсчитывать щ (см. упр. 16).

*В. Дальнейшее исследование критерия. Анализ основного множества (2) начнем с наблюдения

/aJ. + (l + a + - + ai-i)e4 т \ тп I

От "модуля 1" можно избавиться, выполнив операцию, с помощью которой множество удлиняется периодически, и сделав бесконечное множество копий исходного f-размерного гиперкуба во всех направлениях. Это дает множество

их , s(x) , s-Ux) , \ , , ,1

- + ь-+ 2, • • •,-- + h 1 целое fci, Лг,...,

{(x (хх а""х \ 1

Vo-t- --t-A;i, - -t-A;2,...,--\-кЛ целое fci, Лг,/ct >, \тп тп тп j )

Vo = {0,c, (1 + а)с, ...,(1+а + --- + а-2)с) (6)

является вектором констант. Переменная A;i избыточна в этом представлении L, потому что можно менять {x,ki,k2, ...,kt) на, {x + kim, О, к2 - aki, ..., kt - a*~ki), доводя A;i до нуля без потери общности. Поэтому получим сравнительно простую формулу:

L = {Vo + J/1 Vi -I- j/гУг + --- + ytVt\ целые j/i,j/г, • ,Vt}, (7)

И =(l,a,a...,a-l); (8)

Уг = (0,1,0,...,0), Уз = (0,0,1,...,0), У = (0,0,0,...,!). (9)

Точки {xi,X2, ,xt) L, удовлетворяющие неравенству О < xj < 1 для всех j, являются именно т точками исходного множества (2).

Заметим, что приращение с появляется только в Vq и влияние Vq заключается в сдвиге всех элементов L без изменения их относительных расстояний. Следовательно, с никоим образом не влияет на спектральный критерий и в качестве хорошего предположения можно взять Уо = (0,0,...,0) при вычислении ft- Когда Уо - нулевой вектор, имеем точечную структуру

Lo = {yiVi + угУг + • • -t- уМ \ целые yi, j/г, • •, Vt} (Ю)

и нашей целью является изучение расстояний между смежными {t - 1)-мерными гиперплоскостями в семействе параллельных гиперплоскостей, покрывающих все точки Lo-

Семейство параллельных {t - 1)-мерных гиперплоскостей можно определить следующим образом. Пусть ненулевой вектор U = (ui,...,Ue) перпендикулярен всем гиперплоскостям; тогда множеством точек на определенной гиперплоскости является множество

{{xi,...,xt) I xiui +--- + xtut = q}, (11)

где q - различные константы для каждой гиперплоскости семейства. Другими словами, каждая гиперплоскость - это множество всех векторов X, для которых