Will rand() sometimes return the same consecutively?

Question

I'm just curious, can a single-threaded program ever get the same return value for two consecutive calls to rand()?

So, will this assertion ever fire?

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

Answer 1

If we can find one example where it does, the answer to your question is "yes".

#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;
}

prints Oops. rand() = 3482; i = 32187 on Windows with Visual Studio 2010.

EDIT: Use the version below to detect all sequences where 2 consecutive rand() calls return the same value. C only specifies that rand() should return "pseudo-random integers in the range 0 to RAND_MAX" and RAND_MAX should be at least 32767. There are no constraints on the quality of the PRNG, or it's implementation, or other details such as whether 2 consecutive rand() calls can return the same value.

#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

I did my research

discovered that my compiler(msvc10)'s rand implementation did use Linear congruential generator just like other c/c++ compiler

Linear congruential generator

Linear congruential generator use the recurrence method.

ptd->_holdrand(n) will never equals ptd->_holdrand(n+1), but the mod result will equal.

msvc implemention

@nos shows the result

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

final answer is the rand() will return same value twice some times as my instinct.

Answer 3

A ideally random rand() function, if called twice, would return the same result each time with a probability of 1.0 / RAND_MAX.

But rand() is not a true random number generator. It's a pseudorandom number generator (PRNG), typically of the linear congruential type.

The internal state of the PRNG must not be repeated on consecutive calls; if it did, rand() would get stuck on the same number forever. This can happen with poorly-designed algorithms like the middle square method.

However, some (but not all) PRNG implementations have more bits in their internal state than they have in their output. For example, java.util.Random uses a 48-bit internal state but only includes the most significant 32 bits in its output. In this case, it's (at least theoretically) possible to get the same output two consecutive times without having the same internal state.