Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    А чем он плох?

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

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

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

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

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

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

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

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

        Точнее это свойство ГСЧ называется криптостойкостью.

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

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

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

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

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

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -13 Проголосовать: не нравится

        Я всегда считал, что числа до 15 бит на MS и 31 или 32 на линуксах, поэтому проблемы здесь не вижу. Нужно аккуратно использовать, иногда надо сгенерить число 64-битное, проблемы нет в том чтобы подвигать да поксорить.

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

        cerr << RAND_MAX << endl;

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

        Так сейчас в c++0x есть нормальные рандомы куча распределений) и они по моему более менее адекватно работают...

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

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

→ Ответить
»
12 лет назад, # |
← 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 может и не совпасть. Кто проверит — отпишитесь ниже пожалста :)

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

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

    магия) где вы это нашли?

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

    На gcc 4.4.3 не совпадает и даже не похоже — выдаёт какие-то подозрительно маленькие числа.

    UPD: "подозрительно маленькие" — видимо, вот причина

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

      Windows? У меня gnu 4.5.2 и visual studio 2010 на windows согласны. Тут вопрос в том пользуется ли твой компилятор услугами msvcrt.dll и какой версии.

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

        Нет, Linux Ubuntu 10.04, забыл самое главное указать :)

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

          А, ну тогда вопросов нет :)

          **_кроме одного, давно хотел спросить, прощу прощения, но.. тебя серьезно так звать?_**

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

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

→ Ответить