Генератор псевдослучайных чисел RandAs предназначен для использования в системе программирования Turbo Pascal
или Borland Pascal в программах, работающих в реальном режиме DOS.
Существуют 6 модулей датчика RandAs, перечисленных в заголовке приведённой далее таблицы. Каждый модуль
содержит 2 независимых генератора псевдослучайных чисел, которые далее будут обозначаться As и MM.
Генератор As использует линейный конгруэнтный метод, описанный в упомянутой выше статье и подробно изученный
в книге [1]. Параметры этого датчика можно найти в нижеследующей таблице.
Генератор MM основан на линейном конгруэнтном методе с теми же параметрами, что и As. Числа, вырабатываемые
датчиком MM, выбираются из таблицы, содержащей 64, 128 или 256 чисел; на место выбранного числа в таблицу
записывается очередной элемент линейной конгруэнтной последовательности. Какие-либо корреляции между
величиной числа и его местом в таблице отсутствуют. В книге [1] этот метод называется методом Макларена -
Марсальи. В том варианте, который описан в книге, для выбора числа из таблицы используется вторая линейная
конгруэнтная последовательность. В датчике RandAs вторая последовательность не используется. Вместо этого
используются два различных байта двух чисел - байт 4 предыдущего выходного числа и байт 5 (до приведения по
модулю ) очередного
элемента линейной конгруэнтной последовательности (байты числа нумеруются, начиная с младшего:
).
Эти байты комбинируются побитной операцией XOR.
Подробное описание функций и процедур, входящих в датчик, можно найти в инструкции к нему (скачать можно
здесь - всего 19.6 kb). Здесь же сделаем только маленькое замечание о
функциях RandAs(M) и RandMM(M). Они выдают целое число, принадлежащее отрезку
. При этом принимаются
специальные меры, чтобы обеспечить одинаковые частоты появления всех значений. Некоторая проблема
(несущественная при небольших значениях
) возникает в тех случаях,
когда не делится на
. Функции RandAs(M) и
RandMM(M) просто пропускают "лишние" элементы линейной конгруэнтной последовательности. Количество
таких "лишних" элементов последовательности на всём периоде равно остатку от деления
на
.
Заметим также, что функции RandAs(M) и RandMM(M) никогда не выдают выходное значение датчика As или MM
полностью. Максимум, что Вы можете получить - это старшие 32 разряда, если зададите
, в виде числа
типа LongInt (к сожалению, Turbo Pascal и Borland Pascal почему-то не предусматривают типа DWord, который
был бы здесь более уместен, чем LongInt). Вообще, эти функции избегают использования младших разрядов,
которые могут быть "недостаточно случайными", хотя для датчика MM эта проблема не так актуальна.
Результаты спектрального теста
Результаты, приведённые в таблице, относятся к датчику As. Предполагается, что числа, вырабатываемые этим
датчиком, используются подряд (без пропусков) группами по
штук. Рассматриваются
два варианта:
- первые числа
групп являются последовательными элементами линейной конгруэнтной последовательности, вырабатываемой
датчиком As (на практике так делать не следует, так как последовательные группы будут иметь общие элементы;
гораздо лучше после выработки очередной группы пропустить необходимое число элементов последовательности,
чтобы получить ,
взаимно простое с ; на
результаты спектрального теста это не влияет, так как важна только величина наибольшего общего делителя
);
- группы идут
подряд, без пропусков.
Определения величин
можно найти в статье "Датчики псевдослучайных чисел". Число
- это
количество двоичных цифр, которые можно считать случайными при таком использовании линейного конгруэнтного
метода. В частности, как показано в книге [1], величина
характеризует
"плотность" расположения точек в
-мерном кубе (точнее,
это есть расстояние между параллельными плоскостями, в которых лежат точки
).
Сказанное остаётся справедливым и для групп более общего вида, рассмотренных в статье
"Датчики псевдослучайных чисел".
Параметры
Rnd51Fnc, Rnd52Fnc, Rnd54Fnc
Rnd61Fnc, Rnd62Fnc, Rnd64Fnc
Модуль m
240=1099511627776
248=281474976710656
Множитель a
381788655933
19073486328125
Приращение c
232354146751
59605982046655
Мощность
20
24
N
Параметры
n=1
n=N
n=1
n=N
2
d=НОД(n,m)
1
2
1
2
sj, 1≤j≤2
-413719, -650269
-532496, 491856
8220993, -366677
-8220993, 366677
ν2
770722.5073410014
724896.0716902803
8229166.296070216
8229166.296070216
d2=log2ν2
19.555851996907162
19.467414645281973
22.972314846696424
22.972314846696424
C2
1.6972512211031083
3.0028354501610264
0.7558258797037793
1.5116517594075587
3
d=НОД(n,m)
1
1
1
1
sj, 1≤j≤3
-3512, 7250, -3266
-3512, 7250, -3266
5610, -6986, -28424
5610, -6986, -28424
ν3
8692.721092960479
8692.721092960479
29802.685650793286
29802.685650793286
d3=log2ν3
13.085592140967737
13.085592140967737
14.863154723676427
14.863154723676427
C3
2.5023958959222456
2.5023958959222456
0.39392634225661144
0.39392634225661144
4
d=НОД(n,m)
1
4
1
4
sj, 1≤j≤4
-261, -22, 674, -387
332, 289, 225, -170
-182, -3113, -2071, -382
-1536, -489, -959, 1292
ν4
820.1524248577211
522.7523314151741
3762.825799847769
2277.578099648835
d4=log2ν4
9.679748248469703
9.029983780857602
11.877600785996385
11.15328481049807
C4
2.0307114437738107
1.340645108909954
3.5146850192121866
1.8870484974858768
5
d=НОД(n,m)
1
1
1
1
sj, 1≤j≤5
-19, 82, 55, 60, 14
-19, 82, 55, 60, 14
-174, 531, -3, -98, 44
-174, 531, -3, -98, 44
ν5
117.92370414806346
117.92370414806346
569.0219679414847
569.0219679414847
d5=log2ν5
6.881709937096044
6.881709937096044
9.152340540774864
9.152340540774864
C5
0.10917022600571252
0.10917022600571252
1.1155880357458705
1.1155880357458705
6
d=НОД(n,m)
1
2
1
2
sj, 1≤j≤6
-25, -20, -3, 17, 13, -2
25, 20, 3, -17, -13, 2
-68, -69, 9, -77, 103, 166
-68, -69, 9, -77, 103, 166
ν6
38.67815921162743
38.67815921162743
231.43033509028155
231.43033509028155
d6=log2ν6
5.273447229943818
5.273447229943818
7.8544341701058356
7.8544341701058356
C6
0.015735962853972378
0.031471925707944756
2.820851869901944
5.641703739803888
7
d=НОД(n,m)
1
1
1
1
sj, 1≤j≤7
-25, -20, -3, 17, 13, -2, 0
-25, -20, -3, 17, 13, -2, 0
-30, -50, 31, -12, -12, -3, -32
-30, -50, 31, -12, -12, -3, -32
ν7
38.67815921162743
38.67815921162743
75.37904218017101
75.37904218017101
d7=log2ν7
5.273447229943818
5.273447229943818
6.2360915580947704
6.2360915580947704
C7
0.5564690986186962
0.5564690986186962
0.23211051364960306
0.23211051364960306
8
d=НОД(n,m)
1
8
1
8
sj, 1≤j≤8
-10, -2, 0, 13, 18, 17, 6, 6
5, 18, -2, -1, 2, -5, 0, 11
10, 21, -7, -27, 13, -27, 15, 14
-13, 0, 12, -4, -42, -3, 7, -5
ν8
30.95157508108432
22.44994432064365
51.36146415358503
46.647615158762406
d8=log2ν8
4.95194092286809
4.488639961749958
5.682614424625772
5.5437314206251695
C8
3.10921288505319
1.9054631542465212
0.698308972103366
2.586270870288504
В то время, когда автор выбирал параметры для датчика, в его распоряжении не было вычислительных средств для
реализации спектрального теста, поэтому параметры были выбраны хотя и в соответствии с рекомендациями Д.Кнута,
но всё-таки без учёта спектрального теста. Затем в распоряжении автора появился компьютер "Агат" с
языком программирования Рапира, который давал возможность работать с целыми числами "неограниченной"
величины. На этом компьютере был реализован спектральный тест, однако возможности экспериментирования были
достаточно ограничены из-за малого быстродействия компьютера. После обсчёта некоторого количества множителей
и сравнения величин
автор пришёл
к выводу, что первоначально выбранные значения параметров по меньшей мере не хуже остальных проверенных
вариантов, поэтому они сохраняются до сих пор.
Что касается величин
,
которые Д.Кнут считает менее важными, то для датчика As с периодом
они имеют также
неплохие значения, а для датчика с периодом
слишком малым
является только .
В настоящее время, пользуясь либо системами компьютерной математики, либо доступными библиотеками
арифметических процедур многократной точности, легко реализовать спектральный тест и подобрать существенно
лучшие значения множителя ,
и автор это проделал. Возможно, автор в обозримом будущем заменит параметры датчиков, однако никакие значения
параметров без существенного увеличения модуля
не приведут к радикальному
улучшению качества датчика As, основанного на линейном конгруэнтном методе. Если этот датчик недостаточно
хорош для Ваших целей, попробуйте вместо функций RandAs(M) и RandRe использовать RandMM(M), RandRM и RandEx.
Эти три функции используют датчик MM, основанный на методе Макларена - Марсальи, и, по уверениям Д.Кнута,
удовлетворяет практически любым статистическим тестам, применяемым для проверки датчиков псевдослучайных
чисел (впрочем, по наблюдениям автора, эмпирические тесты, описанные в книге [1], как правило, не обнаруживают
существенной разницы между различными датчиками, если только среди них нет очень плохих).
Литература
[1] Д.Кнут. Искусство программирования для ЭВМ. Том2. Получисленные алгоритмы. "Мир", Москва, 1977.
Если вопросов будет много, мы, возможно, сделаем на сайте раздел вопросов и ответов.
) очередного
элемента линейной конгруэнтной последовательности (байты числа нумеруются, начиная с младшего:
).
Эти байты комбинируются побитной операцией XOR.![[0,M]](PsRG/0M.gif){kind=small}
. При этом принимаются
специальные меры, чтобы обеспечить одинаковые частоты появления всех значений. Некоторая проблема
(несущественная при небольших значениях
) возникает в тех случаях,
когда 
. Функции RandAs(M) и
RandMM(M) просто пропускают "лишние" элементы линейной конгруэнтной последовательности. Количество
таких "лишних" элементов последовательности на всём периоде равно остатку от деления
, в виде числа
типа LongInt (к сожалению, Turbo Pascal и Borland Pascal почему-то не предусматривают типа DWord, который
был бы здесь более уместен, чем LongInt). Вообще, эти функции избегают использования младших разрядов,
которые могут быть "недостаточно случайными", хотя для датчика MM эта проблема не так актуальна.
штук. Рассматриваются
два варианта:
- первые числа
групп являются последовательными элементами линейной конгруэнтной последовательности, вырабатываемой
датчиком As (на практике так делать не следует, так как последовательные группы будут иметь общие элементы;
гораздо лучше после выработки очередной группы пропустить необходимое число элементов последовательности,
чтобы получить 
,
взаимно простое с 
);
- группы идут
подряд, без пропусков.
можно найти в статье "
- это
количество двоичных цифр, которые можно считать случайными при таком использовании линейного конгруэнтного
метода. В частности, как показано в книге [1], величина
характеризует
"плотность" расположения точек в
).
Сказанное остаётся справедливым и для групп более общего вида, рассмотренных в статье
"
и сравнения величин
автор пришёл
к выводу, что первоначально выбранные значения параметров по меньшей мере не хуже остальных проверенных
вариантов, поэтому они сохраняются до сих пор.
,
которые Д.Кнут считает менее важными, то для датчика As с периодом
они имеют также
неплохие значения, а для датчика с периодом
слишком малым
является только 
.