Почему drand48() и его друзья устарели?

В конце концов, они кажутся лучше стандартной libc rand(). Я что-то пропустил?

(Я потратил некоторое время на поиски этого в Интернете, и единственный другой случай этого вопроса, который я смог найти, был в контексте предвзятости распределения и остался без ответа.)

Страницы руководств для rand() и drand48() также кажутся противоречащими друг другу. Первый рекомендует второй, а второй утверждает, что он устарел и следует использовать первый. (Хотя, честно говоря, у многих людей, которые понимают математику, лежащую в основе PRNG, есть проблемы с справочными страницами для этих функций, потому что они плохо сформулированы, а в некоторых случаях просто неверны.)

Тем не менее, я не могу найти оправдания статусу «устаревший».


person Dúthomhas    schedule 12.08.2014    source источник
comment
На справочной странице моей системы указано, что эти функции объявлены устаревшими в соответствии с SVID 3, в котором говорится, что вместо этого следует использовать rand(3). "nofollow noreferrer">SVID был опубликован в 1989 году. POSIX ничего не говорит о том, что они устарели, устарели или устарели. Я понятия не имею, почему SVID 3 объявил их устаревшими, поэтому это комментарий, а не ответ.   -  person Keith Thompson    schedule 12.08.2014
comment
SVID 4 документирует drand48 и его друзей и ничего не говорит о том, что они устарели.   -  person Keith Thompson    schedule 12.08.2014
comment
Это очень помогает. Благодарю вас!   -  person Dúthomhas    schedule 13.08.2014


Ответы (2)


На справочной странице моей системы (которая взята из проекта справочных страниц Linux) говорится:

Эти функции объявлены устаревшими согласно SVID 3, в котором указано, что вместо них следует использовать rand(3).

SVID 3 был опубликован в 1989 году.

SVID 4 (ссылка на 720-страничный PDF-файл), опубликовано в 1995 году документы drand48, erand48, lrand48, nrand48, mrand48, jrand48, srand48, seed48 и lcong48 и, как и POSIX, ничего не говорят о том, что они устарели.

POSIX по состоянию на 2013 год ничего не говорит о том, что они устарели, или устарел.

Я не нашел копию SVID 3, поэтому не знаю, почему он объявил эти функции устаревшими, но, видимо, позже это решение было пересмотрено. Заявление на странице руководства кажется устаревшей информацией. Я бы не беспокоился об этом.

Что касается того, какую функцию вы должны использовать, стандартная функция C rand() является наиболее переносимой (если вы не перекомпилируете другую функцию из исходного кода). Некоторые реализации rand() имеют низкое качество, младшие биты повторяются очень регулярно; другие немного лучше.

Если вам не нужны псевдослучайные числа высокого качества, вы также можете использовать rand() (заполненный вызовом srand() с разумным значением, например, srand(time(NULL)).

Если вам нужны высококачественные псевдослучайные числа, скорее всего, ни одна из этих функций недостаточно хороша, я бы не советовал использовать какую-либо из них, например, для криптографии. Вы можете использовать /dev/urandom или /dev/random, если ваша система это поддерживает. Я слышал хорошие отзывы о Mersenne Twister, но мне не хватает опыта, чтобы комментировать дальше.

(Кстати, если вы ищете в Google SVID, обратите внимание на Svið).

person Keith Thompson    schedule 13.08.2014
comment
Mersenne Twister — потрясающий PRNG, но он не подходит для криптографических целей. (Ее состояние наблюдаемо и, что более важно, предсказуемо после примерно 600+ итераций, что не так много.) /dev/urandom правильный выбор для TRNG на *nixen. Что касается rand(), лично я думаю, было ошибкой включать его только как минимальный PRNG - игрушку - поскольку теперь мы должны мириться с его вездесущностью. Еще раз спасибо за отличный ответ! - person Dúthomhas; 13.08.2014
comment
И это мой 2000-й ответ. - person Keith Thompson; 13.08.2014

Примечание о стандартах:

  • #P2# <блочная цитата> #P3#
  • #P4# <блочная цитата>
       Xn+1 = (aXn + c) mod m, where n >= 0
    
  • #P5# <блочная цитата> #P6#

Итак, в POSIX есть эти три генератора случайных чисел. Лучшим из них является random() или rand(), которые одинаковы в glibc (но, вероятно, не одинаковы в других системах). Генератор drand48() — это очень простой тип (линейно-конгруэнтный) с относительно небольшим количеством состояний (48 бит), поэтому его следует избегать. Ни один из обсуждаемых здесь генераторов случайных чисел не обязательно подходит, например, для Симуляция Монте-Карло, но drand48(), вероятно, намного хуже, чем rand() или random().

Какой из них я должен использовать?

Я бы всегда избегал drand48(), потому что это крошечный линейный конгруэнтный генератор с небольшим состоянием, и он доступен только в системах POSIX. В системах POSIX обычно доступен random(), и он лучше.

Обычно я избегаю rand(), потому что во многих системах это плохой генератор, часто линейный конгруэнтный генератор, который даже меньше, чем drand48(), а его младшие биты в некоторых системах цикличны. Если вам не нужны хорошие случайные числа, то подойдет rand().

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

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

person Dietrich Epp    schedule 12.08.2014
comment
rand() засеивается srand(), который принимает только одно unsigned int, что означает, что существует не более UINT_MAX+1 возможных начальных состояний. Ни стандарт C, ни POSIX ничего не говорят о random() и не говорят и не подразумевают, что rand() имеет 31 целое число (какого размера?) внутреннего состояния. Существуют реальные реализации rand() (в системах *BSD), в которых результат постоянно чередуется между четными и нечетными числами. Ваше утверждение, что rand() превосходит drand48(), не подтверждается и, насколько мне известно, не соответствует действительности. - person Keith Thompson; 12.08.2014
comment
@KeithThompson: я только утверждаю, что rand() лучше glibc. Если вам нужно больше начальных состояний, используйте random(). - person Dietrich Epp; 12.08.2014
comment
Я не уверен даже в том, что это правда (и вопрос был не о glibc). Количество битов состояния — не единственная мера качества PRNG. Если вам важно, какой из них имеет лучшее качество, вам, вероятно, не следует использовать ни один из них. - person Keith Thompson; 12.08.2014
comment
@KeithThompson: Это правда, но drand48() использует линейный конгруэнтный генератор, который, как известно, является особенно плохим алгоритмом для генерации случайных чисел. Мы вряд ли могли ожидать, что random() будет хуже. - person Dietrich Epp; 12.08.2014
comment
16 * ((2^31) - 1) не кажется большим, так как это 16 * 2147483647. Где-то опечатка? - person chux - Reinstate Monica; 13.08.2014
comment
@chux: Да, это может быть опечатка на странице руководства. Также возможно, что генератор не использует весь период, который может позволить его состояние. - person Dietrich Epp; 13.08.2014
comment
Это сочетание артефакта эпохи man-страниц и невежества со стороны авторов. По сравнению с до глупости простым ГПСЧ, таким как rand(), технически он больше. По сравнению с чем-то надежным, таким как Mersenne Twister, он бесконечно мал. Однако в случае с random(), поскольку алгоритм оставлен для реализации, фактический период может отличаться от текста на странице руководства. - person Dúthomhas; 13.08.2014
comment
@Dúthomhas: хотя rand() также остается открытым для реализации, как уже упоминалось, это всего лишь int rand() { return (int) random(); } в glibc. - person Dietrich Epp; 13.08.2014
comment
@Дитрих Эпп: Да, и абсолютное улучшение. Благодарю вас! - person Dúthomhas; 13.08.2014