rand()有时会连续返回吗？

Question

我只是好奇,单线程程序可以连续两次调用获得相同的返回值rand()吗？

那么,这个断言会不会发生？

assert(rand() != rand());

Answer 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使用Visual Studio 2010在Windows上打印.

编辑:使用下面的版本检测2连续rand()调用返回相同值的所有序列.C仅指定rand()应返回"0到RAND_MAX范围内的伪随机整数",RAND_MAX应至少为32767.对PRNG的质量或其实现或其他细节(如是否连续2次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;
}

Answer 2

我做了我的研究

发现我的compiler(msvc10)的rand实现确实使用了线性同余生成器,就像其他c/c ++编译器一样

线性同余发生器

线性同余生成器使用递归方法.

ptd - > _ holdrand(n)永远不会等于ptd - > _ holdrand(n + 1),但mod结果将相等.

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()将作为我的直觉两次返回相同的值.

Answer 3

一个理想的随机rand()函数,如果被调用两次,每次都会返回相同的结果,概率为1.0 / RAND_MAX.

但rand()不是真正的随机数发生器.它是伪随机数发生器(PRNG),通常是线性同余类型.

连续呼叫时不得重复PRNG 的内部状态 ; 如果确实如此,rand()将永远陷入同一个数字.这可能发生在设计不佳的算法中,例如中间方法.

但是,一些(但不是全部)PRNG实现在其内部状态中具有比在其输出中更多的位.例如,java.util.Random使用48位内部状态,但仅包括其输出中最重要的32位.在这种情况下,(至少在理论上)可以连续两次获得相同的输出而不具有相同的内部状态.

Answer 4

一个好的随机数生成器有时应该连续两次返回相同的值.假设它返回正整数0 <= r <2 ^ 31.对于完美的随机数发生器,两个连续数字相同的可能性大约为20亿.在1000亿次通话中没有获得两个相同数字的机会大约是10 ^ 15中的一个.