31

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());
Improve this question
17
  • 66
    Of course. Why wouldn't it? Commented Jun 3, 2014 at 9:16
  • 5
    Take a look at stackoverflow.com/q/21634465/3235496 (it's a java-question but brings up valid points). Commented Jun 3, 2014 at 9:22
  • 19
    You can cast a die twice and get six each time, no? Commented Jun 3, 2014 at 9:34
  • 9
    Returning only unique numbers is a pattern and is not random as such. Commented Jun 3, 2014 at 10:26
  • 22
    dilbert.com/strips/comic/2001-10-25 Commented Jun 3, 2014 at 12:19

4 Answers 4

Reset to default
46

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; }
Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

@bits_international because it came later and unwind's answer was everyone's first impulse.
@bits_international: The definition in the manual or standard is more authoritative than the result of a program execution. For all we know (without reference to an actual definition of rand()), this behavior could be a bug in the visual studio implementation, or the program could have undefined behaviour.
Just a nitpick, but it looks like this could miss a lot of random consecutive numbers. It only checks if an odd call is the same as the next even one, not that an even call is the same as the next one one. You found one eventually but there's a good chance there's an earlier case.
On Ubuntu 64 bit (amd64), with gcc 4.6.3, rand() will repeat 1804289383 after 2888000745 iterations.
@Mankarse: This program demonstrates that the answer to the OP's question is "yes": the OP asked if it can ever happen, and this answer demonstrates that it can. The OP did not ask about whether that behavior was allowed by the standard. Even if this were a bug in MSVC, it would still answer the question. (Of course, it would also be useful for the answer to state that this was a bug, if it were.)
|
31

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.

use the

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.

Improve this answer

9 Comments

It's nice that you did your research, but that's often the step before posting a question (a rule that almost no one on stackoverflow abides by).
+1 for supplementing your own question with some math as an answer. Like @Shahbaz said, it's best to do this kind of research before the question, to avoid needing to ask if you find what you were looking for, but it's good to have reference questions like these on SO (in my opinion) anyway.
@ChrisCirefice, That's true. The best thing to do would be this: do research (in the process possibly find out that no question in SO answers you). If you don't find your answer, ask question. If you do find your answer, ask the question anyway and post your response to help others (you can post a question and its answer at the same time!). Reap rewards for a well-researched question (and possibly well-written answer).
But then quite often the answers give a hint what research to do, so without reading the answers to the question an attempt at research would have failed. Sometimes answers give an incomplete answer, and the questioner, more interested in the complete answer than everyone else, can use this as a start. Posting an improved answer benefits everyone. And research after posting is miles better than no research after posting.
@Shahbaz I disagree. I think that if a question is likely to generate information that's helpful to other users, it's fine to post it, as long as it isn't a duplicate. This is definitely such a question.
|
9

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.

Improve this answer

Comments

6

A good random number generator should sometimes return the same value twice in a row. Let's say it returns positive integers 0 <= r < 2^31. The chance that two consecutive numbers are the same would be about one in two billion for a perfect random number generator. The chance of not getting two consecutive numbers that are the same in 100 billion calls is about one in 10^15.

Improve this answer

2 Comments

until you use randomize() with rand/random (), right? randomize() func is a separate one that I have used in past whenever I wanted random/rand() to return me a pure random number. Again, you still have the probability to get the same # but it's rare.
@ArunSangal depends on what you are using it for, what you are seeding with.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.