Почему 1103515245 используется в ранде? - PullRequest
Новая
       10

Почему 1103515245 используется в ранде?

27 голосов
/ 20 декабря 2011

Я говорю о этом удивительно простой реализации 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) должен удовлетворять только 2 условиям:

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

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

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

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

Ответы [ 4 ]

36 голосов
/ 20 декабря 2011

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

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

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

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

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

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

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

6 голосов
/ 20 декабря 2011

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

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

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

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

2 голосов
/ 16 февраля 2012

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

Выход этого генератора не очень случайный.Если мы воспользуемся генератором выборок, перечисленным выше, то последовательность из 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), Бэйс, Дарем Бэйс, Картер, С.Д. Дарем

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

0 голосов
/ 20 декабря 2011

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

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

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

...