Блог пользователя _dangerous_

rand() в с++
Автор _dangerous_, 14 лет назад, По-русски

На днях возник такой вопрос: как реализуется функция rand() в с++? попутно и srand().

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

нашел такой вариант реализации

но 1) верен ли он? 2) что такое 1103515245m? точнее, что такое m?

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
14 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Верность проверяем просто вычисляя рандом этим алгоритмом и родным: ответ — нет (как минимум на моем гну) Префикс m не компилируется (опять же на моем гну), как и отсутствие плюса (или что там должно быть??) перед 2768 :)

→ Ответить
»
14 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Где-то может и так. А вообще — по разному.

→ Ответить
»
14 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

тут есть код, только там без m http://goo.gl/nPbEJ

→ Ответить
»
14 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

Например, так: stdlib/random_r.c в GNU C Library. А в стандарте POSIX можно найти более простой пример, который предлагается к использованию.

→ Ответить
»
14 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Стандарт вроде бы ничего не говорит про реализацию, предъявлены только некоторые формальные требования, так что вопрос не совсем корректен, надо спрашивать "как реализован rand() в моем компиляторе".

А если в общем, то на этот вопрос все-таки можно ответить — rand() в c++ реализован плохо. Практически везде, насколько мне известно.

→ Ответить
  • »
    »
    14 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +2 Проголосовать: не нравится

    А чем он плох?

    → Ответить
    • »
      »
      »
      14 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +5 Проголосовать: не нравится

      Ну, начиная хотя бы с того, что числа получаются не случайные. =) Это не шутка, сгенерировать достаточно "равномерную" и "независимую" псевдослучайную выборку очень сложно. На википедии хорошо про это написано.

      Мне даже кто-то рассказываел баечку про то, что в каком-то из компиляторов (возможно, не сишном) ГСЧ никогда не выкидывал ноль, в принципе.

      По сути вопроса конкретных тестов привести не готов, просто из собственного опыта говорю. Предлагаю поверить на слово или проверить самому. =)

      → Ответить
    • »
      »
      »
      14 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится +5 Проголосовать: не нравится

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

      UPD Придумался пример. Пусть у нас seed просто увеличивается на 1, а генератор возвращает sha-хэш (или его часть) от seed. Тогда в общем случае мы не можем по последовательности хэшей сказать, что будет дальше.

      → Ответить
  • »
    »
    14 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      14 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Да, для этого хватает, конечно.

      Хотя вот у некоторых компиляторов rand() не выкидывает числа больше 2^15 — 1. Неприятно во время какого-нибудь контеста это обнаружить, наверное.

      → Ответить
»
14 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

http://www.velocityreviews.com/forums/t435632-rand-implementation.html

→ Ответить
»
14 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +18 Проголосовать: не нравится 
void _srand(int x) {
    seed = x;
}

int _rand(){
    return (((seed = seed * 214013L + 2531011L) >> 16) & 0x7fff);
}

int main(){
    srand(123);
    _srand(123);
    for (int i = 0; i < 10;i++) printf("%d ", rand());
    puts("");
    for (int i = 0; i < 10;i++) printf("%d ", _rand());
    puts("");
}

Совпадает :) Код любезно взят из visual studio. При отладке нужно просто зайти вглубь rand и там почти тоже самое написано. Так как стандартом rand походу не закреплен — на linux может и не совпасть. Кто проверит — отпишитесь ниже пожалста :)

Полный код для лентяев

→ Ответить
»
14 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Линейный конгруэнтный метод Более качественные генераторы есть в Boost: http://www.boost.org/doc/libs/1_49_0/doc/html/boost_random/reference.html#boost_random.reference.generators

→ Ответить