Оригинальный источник случайного алгоритма `(seed * 9301 + 49297)% 233280`?

9

Если вы ищете примеры создания засеянного (псевдо) генератора случайных чисел, вы столкнетесь с подобными вещами (конкретный пример http://indiegamr.com/generate-repeatable-random-numbers-in-js/ ):

// the initial seed
Math.seed = 6;

// in order to work 'Math.seed' must NOT be undefined,
// so in any case, you HAVE to provide a Math.seed
Math.seededRandom = function(max, min) {
    max = max || 1;
    min = min || 0;

    Math.seed = (Math.seed * 9301 + 49297) % 233280;
    var rnd = Math.seed / 233280;

    return min + rnd * (max - min);
}

Эти конкретные числа (9301, 49297, 233280) и алгоритм используются снова и снова, но ни у кого, кажется, нет определенной ссылки для этого. Кто изобрел этот алгоритм и протестировал дистрибутив? Есть ли бумага или что-то, чтобы процитировать?

jlarson
источник
5
это линейный конгруэнтный генератор, но с довольно небольшим периодом (всего 233 тыс., в то время как 32-битное int позволяет иметь 4-миллиардный период
трещотка
1
Люди часто копируют код непосредственно из книг, поэтому он, вероятно, где-то из старой книги и был скопирован несколько раз. Это также кажется ограничивающим случаем. Возможно, полезно: heydari.persiangig.com/Ebooks/Applied_Crypto-Ch11-ch20.pdf/… ict.griffith.edu.au/anthony/info/C/RandomNumbers
barrycarter
2
Каким бы ни было происхождение, это ужасные значения, которые можно использовать для расчета семени.
3
@jlarson комментарий не достаточно длинный, но есть две проблемы под рукой. Во-первых, как намекал на хрипотца, по модулю максимальный период: количество уникальных чисел, прежде чем генератор повторяется. Фактический период может быть меньше. Во-вторых, два других числа (в основном, мультипликаторы) должны быть относительно простыми по отношению к числу по модулю, чтобы обеспечить более длительный период. В идеале число по модулю - это наибольшее простое число, которое меньше максимального положительного целого числа, которое соответствует типу данных, а два других числа также являются большими простыми числами.
1
Это короткая, короткая версия того, почему эти цифры ужасны, учитывая, что это побочное обсуждение, и добавление фактического ответа не подходит для этого вопроса. Я рекомендую побродить по Википедии и, возможно, по математике или информатике для получения дополнительной информации, хотя технически алгоритмы псевдослучайных чисел также обсуждаются в Программистах.

Ответы:

7

Быстрый поиск в Google Книгах показывает, что эти числа (9301, 49297, 233280) были использованы в ряде ссылок:

  • Численные рецепты на Фортране 77
  • Введение в численные методы в C ++
  • Ресурс CGI Developer: веб-программирование на TCL и PERL
  • Эффективный Фортран 77 для инженеров и ученых
  • Разработка JavaScript
  • Все на С
  • Примеры Java в двух словах
  • Получисленные алгоритмы
  • Введение в механику

Самым старым из них являются компьютерные методы математических вычислений 1977 года Джорджа Элмера Форсайта, Майкла А. Малкольма, Кливе Б. Молера (Прентис-Холл), хотя Google не показывает, где текст использовался в книге, поэтому его невозможно проверить.

Самое раннее, показывающее текст - « Числовые рецепты на Паскале» (первое издание): «Искусство научных вычислений» , том 1, издательство Press, Teukolsky, Vetterling and Flannery в полностраничной таблице «Константы для портативных генераторов случайных чисел». Эти конкретные числа даны с переполнением в 2 ^ 31.

Серия книг « Числовые рецепты » пользуется огромной популярностью и печатается с 1986 года.

Хьюго
источник
1
Ничего себе, если ответа здесь нет, я не знаю, где он будет. Спасибо .. // Я надеялся, что смогу указать на какое-то конкретное исследование, почему эти числа особенные, но этого достаточно. 9301 - это произведение двух простых чисел (71x131), 49297 - это простое число - я чувствую, что это должно быть актуально. 233280 не простое число - оно равно 2x2x2x2x2x2x3x3x3x3x3x3x5 (или 2 ^ 6 * 3 ^ 5 * 5)
jlarson