Почему 1103515245 используется в rand?

Я говорю о этом удивительно простой реализации rand() по стандарту C:

static unsigned long int next = 1;

int rand(void)  /* RAND_MAX assumed to be 32767. */
{
    next = next * 1103515245 + 12345;
    return (unsigned)(next/65536) % 32768;
}

Из этой статьи в Википедии мы знаем, что множитель a (в приведенном выше коде a = 1103515245) должен удовлетворять только двум условиям:

a - 1 делится на все простые множители m.
(В нашем случае m = 2^32 размер int, поэтому m имеет только один простой коэффициент = 2)
a - 1 является кратным 4, если m является кратным 4.
(32768 кратно 4 и 1103515244 тоже)

Почему они выбрали такой странный, трудно запоминающийся "человек, я сыт по горло этими случайными числами, напишу все", например 1103515245?

Возможно, есть некоторые разумные причины, что это число как-то лучше другого?

Например, почему бы не установить a = 20000000001? Это больше, прохладно и легче запомнить.

Ответ 1

Если вы используете LCG для рисования точек в d-мерном пространстве, они будут лежать не более (d! M) ^¹/_d гиперплоскостей. Это известный недостаток LCG.

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

"Спектральный тест" (название происходит от теории чисел) - это максимальное расстояние между последовательными гиперплоскостями, на которых лежат d-мерные распределения соединений. Вы хотите, чтобы он был как можно меньшим для максимально возможного количества тестов.

Смотрите эту статью для исторического обзора по теме. Обратите внимание, что указанный вами генератор упоминается в статье (как ANSIC) и определен как не очень хороший. Однако старшие 16 битов приемлемы, но многим приложениям потребуется более 32768 различных значений (как вы указали в комментариях, период действительно 2 ^ 31 - условия для полной периодичности в ссылке на Википедию, вероятно, необходимы только).

Исходный исходный код в документе ANSI не занимал старшие 16 битов, что приводило к очень плохому генератору, который легко использовать неправильно (rand() % n - это то, о чем люди впервые думают, чтобы нарисовать число от 0 до n, и это дает что-то очень неслучайное в этом случае).

Смотрите также обсуждение LCG в числовых рецептах. Цитирование:

Хуже того, многие ранние генераторы сделали особенно плохой выбор для m и a. Одна печально известная такая подпрограмма, RANDU, с = 65539 и m = 231, была широко распространена на мэйнфрейм-компьютерах IBM в течение многих лет и широко копировалась на другие системы. Один из нас, будучи аспирантом, вспоминает, как создавал "случайный" сюжет только с 11-ю плоскостями, и его консультант по программированию в компьютерных центрах говорил, что он неправильно использовал генератор случайных чисел: "Мы гарантируем, что каждое число индивидуально случайное, но мы не гарантируем что более одного из них является случайным ". Это отбросило наше высшее образование как минимум на год!

Ответ 2

Помните, что rand() является приближением равномерного распределения. Эти числа используются, потому что они были протестированы, чтобы показать, что они генерируют более равномерное распределение.

Учитывая множество пар целых чисел без знака в представимом диапазоне, я сомневаюсь, что кто-то попробовал их со всеми действительными семенами. Если вы считаете, что у вас есть лучший выбор параметров, просто попробуйте! У вас есть код, просто отформатируйте параметры LCG и выполните тесты. Создайте кучу чисел (скажем, 10 миллионов), вычислите гистограмму сгенерированных чисел и запишите, что посмотреть на распределение.

изменить Если вы заинтересованы в разработке генератора псевдослучайных чисел для использования в реальных приложениях, я рекомендую вам прочитать значительную литературу по этому вопросу. Указанный выше "совет" предлагается только показать, что выбор произвольных "больших, прохладных и более легких для запоминания" параметров LCG даст очень плохое распределение. /изменить

Кроме того, это функция библиотеки, и я никогда не видел программу, использующую стандартную библиотечную версию rand(), чтобы запомнить ее параметры LCG.

Ответ 3

Ранние вычисления, как правило, касались бит и байтов и играли трюки с регистрами, чтобы минимизировать байты кода (до того, как строки были в байтах)

Я нашел только один разумный ключ ниже:

Выход этого генератора не очень случайный. Если мы будем использовать генератор образцов, указанный выше, последовательность из 16 ключевых байтов будет очень неслучайной. Например, оказывается, что младший бит каждого последующего выхода rand() будет чередоваться (например, 0,1,0,1,0,1,...). Понимаете, почему? Низкий бит x * 1103515245 такой же, как и младший бит x, а затем добавление 12345 просто переворачивает нижний бит. Таким образом, низкий бит чередуется. Это сужает набор возможных ключей только на 2113 возможностей, намного меньше желаемого значения 2128.

http://inst.eecs.berkeley.edu/~cs161/fa08/Notes/random.pdf

И два разумных ответа:

Улучшение генератора случайных чисел (1976) через заливы, заливы Дарем, Картер, S D Durham

http://en.wikipedia.org/wiki/TRNG

Ответ 4

Это число кажется особенным, оно просто между двумя простыми числами: P.

Теперь поговорим серьезно, чтобы увидеть, если это хороший выбор, просто посмотрите на результат. Вы должны увидеть очень разные результаты, даже если щелкнуть один бит.

Кроме того, подумайте, насколько вы ожидаете предсказуемости... эта реализация ужасна, вы можете рассмотреть более надежную, но простую альтернативу, такую как FNV-1a.