2.4. «Хорошие» псевдослучайные точки.

2.4.1 Последовательность Холтона.

Для построения этой последовательности необходимо определить числовые последовательности Фиксируем натуральное число

Определение. Если в -ичной системе счисления то снова в -ичной системе

Здесь все целые -ичные цифры, т. е. равны одному из значений . В десятичной системе последние две

формулы выглядят так:

Первые 10 значений приведены в табл. 1.

Таблица 1

Пусть — попарно взаимно простые числа. Последовательностью Холтона называется последовательность точек в с декартовыми координатами

Эти последовательности были построены Дж. Холтоном [131], получившим для них оценку (12). Все такие последовательности равномерно распределены в

На практике обычно в качестве выбирают первые простых чисел: и используют -мерные точки

2.4.2. -последовательность . Свойства -последовательностей подробно изучаются в [82]. Здесь мы укажем лишь алгоритм для расчета точек

образующих -последовательность. Программа расчета на ЭВМ БЭСМ-4 имеется в [86].

Определение. Если в двоичной системе счисления

то для всех

Здесь — двоичные цифры, каждая из которых равна 0 или 1. В десятичной системе

Числа можно найти по табл. 6 (стр. 297), которая позволяет вычислить более точек Q в кубе размерности п. 13. Звездочкой обозначена операция поразрядного сложения по модулю два в двоичной системе.

Более подробно, чтобы вычислить «сумму» , надо оба слагаемых записать в двоичной системе

тогда в двоичной системе

где или, другими словами, , если , если .

В системе команд любой ЭВМ имеется специальная команда, осуществляющая операцию Обычно ее называют командой сравнения. Она относится к числу логических команд и выполняется быстрее, чем арифметические команды. Вообще, для расчета по формуле (16) нужны лишь логические команды (произведение либо равно если либо равно нулю, если ).

Пример. Вычислить первые 10 точек Q в трехмерном По табл. 6 (стр. 297) находим нужные значения Они написаны в табл. 2.

Вычисления по формуле (16) сведены в табл 3.

Результаты в десятичной системе:

На рис. 67, в изображены точки в квадрате, а на рис 67, б — 16 «настоящих» случайных точек.

Замечание. Хотя табл. 6 на стр. 297 рассчитана на , ее можно иногда использовать при любых , даже . В качестве значений недостающих координат псевдослучайных точек можно выбирать обычные псевдослучайные числа у, так что, например,

Целесообразно вычислять по наиболее существенные переменные в а по все остальные. Если в действительности существенных координат немного, то такой способ расчета может ускорить сходимость (по сравнению с расчетом по формуле ). (Двумерные точки, у которых одна координата случайная, а вторая детерминированная использовались в [18].)

Таблица 2

Таблица 3

2.4.3. Общие требования. Если подходить к вопросу более строго, то от хороших псевдослучайных точек естественно потребовать, чтобы:

1° асимптотика D N или србыла наилучшей (или хотя бы близкой к наилучшей);

2° константы в (12) или в (13) были наилучшими (или хотя бы достаточно малыми);

3° значения или были небольшими уже при небольших

4° алгоритм расчета этих точек на ЭВМ был достаточно простым.

К сожалению, проверить все эти требования в настоящее время невозможно, так как наилучшие значения констант (13) неизвестны (а для неизвестен даже наилучший порядок роста).

Однако первому требованию в какой-то мере удовлетворяют точки и вполне — точки При небольших второму и третьему требованию удовлетворяют точки . Наконец, время расчета точек того же порядка, что время расчета стандартных псевдослучайных точек (если только имеется готовая таблица ). Для расчета точек Р нужны лишь простых чисел, но по сравнению со временем расчета время расчета Р примерно в раз больше.