Будет ли rand() иногда возвращаться так же последовательно?

Ответ 1

Если мы найдем один пример, где он находится, ответ на ваш вопрос будет "да".

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
  unsigned int i;
  for(i = 0; ; i++) {
    int r = rand();
    if (r == rand()) {
        printf("Oops. rand() = %d; i = %d\n", r, i);
        break;
    }
  }
  return 0;
}

печатает Oops. rand() = 3482; i = 32187 в Windows с Visual Studio 2010.

EDIT: Используйте приведенную ниже версию, чтобы обнаружить все последовательности, где 2 последовательных вызова rand() возвращают одно и то же значение. C указывает только, что rand() должен возвращать "псевдослучайные целые числа в диапазоне от 0 до RAND_MAX "и RAND_MAX должно быть не менее 32767. Нет никаких ограничений на качество PRNG или его реализация или другие детали, такие как два последовательных вызова rand() могут возвращать одинаковое значение.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
  unsigned int i;
  int r1 = rand();
  int r2 = rand();
  for(i = 0; ; i++) {
    if (r1 == r2) {
        printf("Oops. rand() = %d; i = %d\n", r1, i);
    }
    r1 = r2;
    r2 = rand();
  }
  return 0;
}

Ответ 2

Я сделал свое исследование

обнаружил, что реализация rand для моего компилятора (msvc10) использовала линейный конгруэнтный генератор, как и другой компилятор c/С++

Линейный конгруэнтный генератор

Линейный конгруэнтный генератор использует метод повторения.

ptd → _ holdrand (n) никогда не будет равен ptd → _ holdrand (n + 1), но результат мод будет равен.

реализация msvc

@nos показывает результат

return( ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) & 0x7fff );

ptd->_holdrand = 2375716238;
return 3482; (2375716238 >> 16) % 32768
ptd->_holdrand = 228240921;
return 3482; (228240921 >> 16) % 32768

окончательный ответ: rand() будет возвращать одно и то же значение дважды в несколько раз, как мой инстинкт.

Ответ 3

Идеально случайная функция rand(), если она вызывается дважды, будет возвращать один и тот же результат каждый раз с вероятностью 1.0 / RAND_MAX.

Но rand() не является истинным генератором случайных чисел. Это генератор псевдослучайных чисел (PRNG), как правило, линейного конгруэнтного типа .

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

Однако некоторые (но не все) реализации PRNG имеют больше битов в своем внутреннем состоянии, чем в своем выходе. Например, java.util.Random использует 48-битное внутреннее состояние, но включает только самые значительные 32 бита в своем выходе. В этом случае он (по крайней мере теоретически) может получить один и тот же выход два раза подряд без того же внутреннего состояния.

Ответ 4

Хороший генератор случайных чисел должен иногда возвращать одно и то же значение дважды подряд. Пусть говорят, что оно возвращает целые положительные числа 0 <= r < 2 ^ 31. Вероятность того, что два последовательных номера будут одинаковыми, будет около одного в два миллиарда для идеального генератора случайных чисел. Шанс не получить два последовательных номера, которые одинаковы в 100 млрд. Звонков, составляет примерно один из 10 ^ 15.