Wichmann – Hill - Wichmann–Hill

Wichmann – Hill это генератор псевдослучайных чисел предложенный в 1982 г. Брайан Вичманн и Дэвид Хилл.[1] Он состоит из трех линейные конгруэнтные генераторы с разными основной модулей, каждый из которых используется для получения равномерно распределены число от 0 до 1. Для получения результата они суммируются по модулю 1.[2]

Суммирование трех генераторов дает псевдослучайную последовательность с циклом, превышающим 6.95×1012.[3] В частности, модули равны 30269, 30307 и 30323, создавая периоды 30268, 30306 и 30322. Общий период равен наименьший общий множитель из них: 30268 × 30306 × 30322/4 = 6953607871644. Это было подтверждено перебор.[4][5]

Выполнение

Следующее псевдокод предназначен для реализации на машинах, способных к целочисленной арифметике до 5212632:

[r, s1, s2, s3] = функция(s1, s2, s3) является    // s1, s2, s3 должны быть случайными от 1 до 30 000. Используйте часы, если они есть.    s1 : = mod (171 × s1, 30269)    s2 : = mod (172 × s2, 30307)    s3 : = mod (170 × s3, 30323)    р : = мод (s1/30269.0 + s2/30307.0 + s3/30323.0, 1)

Для машин, ограниченных 16-битными целыми числами со знаком, следующий эквивалентный код использует только числа до 30323:

[r, s1, s2, s3] = функция(s1, s2, s3) является    // s1, s2, s3 должны быть случайными от 1 до 30 000. Используйте часы, если они есть.    s1 : = 171 × mod (s1, 177) - 2 × этаж (s1 / 177)    s2 : = 172 × mod (s2, 176) - 35 × этаж (s2 / 176)    s3 : = 170 × mod (s3, 178) - 63 × этаж (s3 / 178)    р : = мод (s1 / 30269 + s2 / 30307 + s3 / 30323, 1)

Начальные значения s1, s2 и s3 должны быть инициализированы ненулевыми значениями.

Рекомендации

  1. ^ Wichmann, Brian A .; Хилл, И. Дэвид (1982). «Алгоритм AS 183: эффективный и портативный генератор псевдослучайных чисел». Журнал Королевского статистического общества. Серия C (Прикладная статистика). 31 (2): 188–190. Дои:10.2307/2347988.
  2. ^ Маклеод, А. Ян (1985). «Замечание AS R58: Замечание об алгоритме AS 183. Эффективный и портативный генератор псевдослучайных чисел». Журнал Королевского статистического общества. Серия C (Прикладная статистика). 34 (2): 198–200. Дои:10.2307/2347378. Вичманн и Хилл (1982) утверждают, что их генератор RANDOM будет генерировать однородные псевдослучайные числа, которые строго больше нуля и меньше единицы. Однако в зависимости от точности станка из-за ошибки округления могут быть получены некоторые нулевые значения. Проблема возникает с с плавающей запятой одинарной точности когда округление к нулю.
  3. ^ Вичманн, Брайан; Хилл, Дэвид (1984). «Исправление: алгоритм AS 183: эффективный и портативный генератор псевдослучайных чисел». Журнал Королевского статистического общества. Серия C (Прикладная статистика). 33 (1): 123. Дои:10.2307/2347676.
  4. ^ Рикитаке, Кендзи. «Калькулятор внутреннего состояния алгоритма AS183 PRNG на языке C».
  5. ^ Цейсель, Х. (1986). «Замечание ASR 61: Замечание об алгоритме AS 183. Эффективный и портативный генератор псевдослучайных чисел». Журнал Королевского статистического общества. Серия C (Прикладная статистика). 35 (1): 98. Дои:10.2307/2347676. Вичманн и Хилл (1982) предложили псевдослучайный генератор, основанный на суммировании псевдослучайных чисел на основе суммирования псевдослучайных чисел, сгенерированных мультипликативными конгруэнтными методами. Это, однако, не более чем эффективный метод реализации мультипликативного конгруэнтного генератора с длиной цикла, намного превышающей максимальное целое число. С использованием Китайская теорема об остатках (см., например, Кнут, 1981 ) вы можете доказать, что получите те же результаты, используя только один мультипликативный конгруэнтный генератор Иксп+1 = α⋅Иксп по модулю м с α = 1655 54252 64690, м = 2781 71856 04309. Однако первоначальная версия все еще необходима, чтобы заставить генератор с такими длинными константами работать с обычной компьютерной арифметикой.