GOOD random numbers!

Here''s a collection of random number generators.

---

[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

If you want a number between 0 and n, use rand() % n. If you want numbers between 1 and n+1, use (rand() % n) + 1. That should get you everything you want.

quote:

---

Original post by Chozo
If you want a number between 0 and n, use rand() % n.

---

This method leads to uneven distributions when the number of different values possibly generated by rand() (i.e. RAND_MAX) is not an exact multiple of n.

Here''s a very simplified example
- assume rand() can generate the numbers ( 0, 1, 2, 3 )
- rand() % 3 will take the values ( 0, 1, 2, 0 )
- The probability of getting 0 is 50%, 1 is 25%, 2 is 25%

The method used by the original poster is correct.

Hm, interesting, I hadn''t even thought of that. I figured that since modding was faster than casting, division, multiplication, and back casting, it would be a worthwile tradeoff. But if you really need that tight distribution, it''s important to be more correct. Thanks for the correction.

The "unequal distribution" argument is an interesting one, but nowadays is not very compelling. RAND_MAX on most implementations is large enough that the incomplete mod-cycle at the end is a very small fraction of the total range.

Older rand() algorithms had low entropy in the low-order bits, which caused problems if you were looking for a random number in a power-of-two range... but this has been fixed pretty much everywhere. And float-to-int conversion is slooooow, so the performance of mod is better.

---

Don''t listen to me. I''ve had too much coffee.

edit: I hate not being able to nest quotes....
edit: I hate missing tags...
edit: I can't do less than/greater than signs easy

quote:

---

Original post by Fruny

...the quote...

This method leads to uneven distributions when the number of different values possibly generated by rand() (i.e. RAND_MAX) is not an exact multiple of n.

Here's a very simplified example
- assume rand() can generate the numbers ( 0, 1, 2, 3 )
- rand() % 3 will take the values ( 0, 1, 2, 0 )
- The probability of getting 0 is 50%, 1 is 25%, 2 is 25%

The method used by the original poster is correct.

---

old argument ^_^. However, the 'original poster' 's method is not perfect either, thanks to floating point round off.

Example: let us suppose that we want a number from 1-100.

Now let us say that RAND_MAX is 150 (extreem example).

according to this, a number between 1 and 50 will appear twice as often as a number between 51 and 100, using the rand()%n method.

However, by doing (((double)rand())/MAX_RAND)*n method, odd numbers will appear twice as often as even numbers (may be vicea versa, or, since floating points are non-linear in storage methodology, most likely a weirder, more contorted method).

So to sumerize...

rand()%n pros and cons:
since RAND_MAX is huge these days, no overweighting of significance should be inccured. On the other hand, smaller numbers will appear more often than larger numbers.

(double)rand()/MAX_RAND * n pros and cons:
more even distribution of numbers, sort of, but not really.

Also, you not only take a random number, but you go through the extra processing of converting int to double, and preform a floating point division and multiplication.

If you're going to waste cycles like that for better distribution (in other words, you have some science experiment that needs perfection as far as the rand() function itself can provide), why not do this:

int myrand(int n)
{
int bfnurm=0; //Biggest Factor of N Under RandMax
while ((bfnurm+n) < RAND_MAX) //Calculate BFNURM
{
bfnurm += n;
}
//okay, we're done. Now get our random variable...
int randvar=0;
while ( (randvar=rand()) >= bfnurm ) //throw out all values above the 'max factor'
{ /* do nothing */}
return randvar%n;
}

This would truncate the last chunk of numbers that would not make a complete run through all the possible values. To take our critics example (slightly modified for better explination):

rand can produce:
0 1 2 3 4 5 6 7(3 numbers added, for more examples)

we want: 0 1 or 2

using rand%3:

0 comes up 3 times (0,3,6)
1 comes up 3 times (1,4,7)
2 comes up 2 times (2,5)

the function provided would cut away what rand could provide to:
0 1 2 3 4 5

0 comes up 2 times (0,3)
1 comes up 2 times (1,4)
2 comes up 2 times (2,5)

The drawback is that my method, assuming rand never gave us a number we could use, could take infinitly long in theory. That is, a truely random function could keep giving us 7 from our example.

But, the odds of that are one in infinity. Aka rare. And the chance of a number being thrown out can not be greater than 50% (by getting the greatest factor bellow rand_max, we ensure this).

Also note that the provided algorythm is a mere sample. It is definatly NOT optimized in any shape or form. Use it at your own peril.

Let the flames begin for my stupidity ^_^.

My final word: unless you're going for huge random numbers, stick with rand()%n.

If you ARE going for huge random numbers, then maybe use my algorythm in optimized form (precalculated bfnurm...just make the function inline, set a bool flag for the first run through, and make that as well as bfnurm static).

Okay, enough pretending I'm smart.
-Mike

[edited by - MaulingMonkey on December 16, 2002 5:03:37 AM]

[edited by - MaulingMonkey on December 16, 2002 5:04:39 AM]

[edited by - MaulingMonkey on December 16, 2002 5:06:42 AM]

No, never use % with rand (). It's not even fast. This subject is covered very completely in this post.

I've done some extensive investigation of MSVC 6.0's rand () function (the most ubiquitous, though not the only one). Yes, it's periodic. It also produces every number between 0 and RAND_MAX the same number of times in a period--in other words, perfectly uniform.

A note on the % 3 post. RAND_MAX is 0x7FFF on MSVC 6.0's rand (). If N = range of 0 to RAND_MAX, N % 3 would produce 2667 0s, 2667 1s and 2666 2s, for a ratio of 33.33375%:33.33375%:33.325%. The modulo method actually masks the distribution problem with small arguments. It's with larger arguments that the modulo method breaks down: rand () % 0x6000 will produce about twice as many results between 0 and 0x3FFF than between 0x4000 and 0x5FFF.

Also note that using rand () % N where N is a power of 2 on MSVC will give you a perfectly uniform distribution. But that's not an excuse to use %.

Run timing trials yourself; rand_good will be much faster than rand_bad:


The reason is that rand_good is not a multiplication and a division; it's a multiplication and a SHIFT, which is much faster than modulo (which is really a division--the slowest thing you can do to an ALU). Also not that this is highly MSVC-specific. I beleive gnu uses a RAND_MAX that will overflow a 32-bit integer if you try this method.

I believe (I don't have the inside MS information to back this up) that the reason Microsoft has such a small RAND_MAX is _because_ this method is so very, very fast. IOW, rand () is _meant_ to be used in this way. The fact that RAND_MAX is a value such that N can be from 0 to RAND_MAX and just get to the edge of overflowing a 32-bit integer is too good to be a coincidence.

Now, when you throw doubles into the mix as the OP does, all bets are off from my end; I haven't investigated the double or float efficiency of using rand, either in speed or distribution. I think there might be some rounding problems with Muzlack's method, so I'd have to investigate rand01 independently (I don't have time at the moment). However, he can safely replace rand_n with my rand_good function.

His problem also depends on how he's using his random numbers. Uniform random distributions aren't appropriate for all applications. I would have to see how he's using rand_n(100) to see why he's having a problem. I have a feeling that his distribution might not be the problem--it might be that a uniform RV isn't what's needed.

edit: got ratios backward with my modulo math--it's Monday

[edited by - Stoffel on December 16, 2002 12:11:30 PM]

So, on a system that uses INT_MAX for it''s RAND_MAX, what should one go with? Like you said, that method will overflow an int, so for the sake of portability, what''s the right thing to do? Or are random numbers too subjective to agree on a right way?

quote:

---

Original post by Muzlack
I HATE random numbers. Every single time I think I have a fine equation that should work right, I find out later it doesn''t. For example, I used this function:

inline double rand01(){ return (double)rand()/(double)RAND_MAX;};
inline int rand_n(int n){ return (int)(rand01()*n);}

And, I''ll use rand_n to get a random number between 0 and the argument n. It works fine for a number between say, 1 and 4, but now, I''m trying to implement random battles, and if I have a number between one and 100, then the program, for a long time will not give me battles, then every step I''ll get battles for a while, then a long time without, etc etc...

Is there ANY good random number methods? I think I''ve heard of one using sockets, but I don''t want to make the user be connected to the internet to play my game!



--Muzlack

[edited by - Muzlack on December 15, 2002 11:21:36 AM]

---

Try the Mersenne Twister algorithm.

quote:

---

Original post by Muzlack
I think I''ve heard of one using sockets...

---

If you''re thinking of this one, that''s just an old joke of mine.

lol... I think that was the one I was thinking of.