Составители:
Рубрика:
67
По данным табл. 3.5, наибольшее значение периода d равно 4,
а плохой выбор a и x
0
значительно уменьшает этот период, в таблице
подчеркнуты повторяющиеся сегменты.
Для выбора генератора, обладающего наибольшим периодом, рас
смотрим несколько лемм.
Лемма 3.2. Если a и m — простые числа, всегда есть положитель
ное целое d, для которого x
0
= x
d
. Для простых чисел наибольшим
общим делителем (НОД) является единица.
Лемма 3.3. Если НОД (a, m) = 1, то тогда период последователь
ности (3.22) является наименьшим целым положительным числом
d, для которого
σ
d
((a – 1) x
0
+ c) = 0 (mod m), (3.25)
где σ
d
= 1 + a + a
2
+ …+ a
d–1
.
Необходимо отметить, что эти леммы действительны только для
случая, когда НОД равен 1, поэтому для гарантии надо выбирать
только такой генератор, у которого НОД равен 1.
Стремление увеличивать период является необходимым, но не
достаточным условием. При увеличении периода может произойти
ухудшение качества БСВ, поэтому их необходимо проверять на слу
чайность, что и рассмотрено в § 3.5.
В заключение параграфа рассмотрим тип генератора БСВ, приме
няемый в GPSS/H. В первой версии языка использован генератор
URN 27, работающий на сдвиговом принципе с обратной связью и
использующий выражение x
31
+ x
3
+ 1. Это выражение комбинирует
ся с последовательностью x
i
= 69069 x
i–1
mod 2
32
. Сдвиг вправо на 15
разрядов и влево на 17 обеспечивает получение 32разрядного числа
y
i
. Эти x
i
и y
i
складываются по правилам алгебры логики и создают
последовательность z
i
, так, например:
x
i
= 01001…01010
y
i
= 00101…10110
z
i
= 01100…11100
Этот генератор не проходил по некоторым тестам случайности, по
этому в более поздних версиях использован усовершенствованный ге
нератор, имеющий в качестве минимального 32разрядного числа (по
ложительный ноль и 31 значащий разряд) минимальное значение 1 и
максимальное 2 млрд 147 млн 483 тыс. 646 (2
31
– 2), а выражение
принимает вид x
i+1
= 742938285 x
i
mod 2147483647, при этом
x
0
= 266301881. Таким образом, период повторения этого генератора
весьма велик (более 2 млрд), что вполне достаточно для моделирова
ния сложных систем. Независимость потоков БСВ достигается тем,
Страницы
- « первая
- ‹ предыдущая
- …
- 65
- 66
- 67
- 68
- 69
- …
- следующая ›
- последняя »
