Can c rand give two consecutive equal numbers?

[jostpuur]

The title already contains my question.

Here's the same thing in other form, just in case the title isn't clear: Is it possible that the following function returns 1, or is it always 0?

x = rand();
y = rand();
return (x == y);

There's two possibilities. Either the probability for 1 is precisely zero, or then the probability 1 is something very small but non-zero.

I'm programming with c, and this is a rand-function that requires stdlib.h to be included.

 

[D H]

Without knowing how rand is implemented (and you don't), there is no way to answer this question. xkcd has a potential answer, though:

Don't use rand(). You can be assured that on some machines it is incredibly bad.

 

[rcgldr]

The rand function, at least the one used in Microsoft libraries, will never give the same number twice in a row, but it does cycle though a finite set of values (RAND_MAX = 0x7fff), and I'm not sure if it that set includes all numbers from 1 to 32767 (you could create a histogram array 32727 bytes long to test for missing or duplicated numbers). To create larger numbers like 32 bit numbers, I've called rand() 4 times, using bits 11->4 from the number retuned from rand() and concatenating them to create a 32 bit number.

VS has a random class that produces 32 bit numbers, but I think that only works with .NET.

 

[D H]

That RAND_MAX=0x7fff is just one of many reasons why microsoft's rand() is bad, bad, bad. Many implementations of rand() are bad, but few are as bad as microsoft's. Look at it this way: Microsoft no longer its own implementation of rand() to generate random numbers in visual basic (and hence in Excel). They switched from rand() to a another random number generator, Wichmann-Hill, with Excel 2003. (That Wichmann-Hill is not all that good itself and that the Microsoft implementation is apparently flawed is another story.)

Jostpuur, if you have access to the boost library, they have a very good random number generator, Mersenne Twister.

 

[jostpuur]

I have Ubuntu linux. My RAND_MAX is 2^31 - 1 = 2147483647

 

[rcgldr]

I have Ubuntu linux. My RAND_MAX is 2^31 - 1 = 2147483647

Should be OK then. Most random number algorithms use the current value to produce the next value, so they shouldn't produce the same number twice in a row (if they did, they'd get stuck on that number).

 

[D H]

No, it shouldn't. Linux' rand() is just bad, as opposed to bad, bad, bad. Just don't use rand(). The period is too short, the behavior is still wrong.

http://www-cdf.fnal.gov/physics/statistics/notes/cdf6850_badrand.pdf

 

[rcgldr]

If you don't need a huge number of random numbers, you can download one of those programs that quicky generates e or pi to millions of digits with an optional binary output, or some way to convert it to a binary file, then use that binary file as large array of random numbers. I used apfloat's (do a web search) aptest program to generate pi in hex, then converted that to binary with my own program.

 

[D H]

You can also download the source code for better random number generators. The wikipedia article on the Mersenne Twister, http://en.wikipedia.org/wiki/Mersenne_twister, lists implementations in several languages. If you are using C++, the Boost libraries contain a very nice random number package; these are a part of the new (but still draft) standard. Here is the documentation on the Boost Random package: http://www.boost.org/doc/libs/1_47_0/doc/html/boost_random.html. The GNU scientific library, http://www.gnu.org/software/gsl/, also has an extensive random number package.