Random number if range is greater than RAND_MAX?

[Martin]

I am trying to write code that selects a random number in the range 0 to n,
where n can be substantially greater than the RAND_MAX on my system which is
32767. I am using VC++ 2003 FWIW.
As you know, the standard library rand() only returns an integer in the
range 0<=n<=RAND_MAX.
In fact, this problem is posed as an exercise by Andrew Koening in
Accelerated C++. It's Ex 7-9 and it's marked as "difficult" so I don't feel
too bad in asking for help!

Is there a standard solution to this? It must be quite a common requirement,
but I'm stumped.

Thanks,
Martin

 

[John Harrison]

I am trying to write code that selects a random number in the range 0 to n,
where n can be substantially greater than the RAND_MAX on my system which
is 32767. I am using VC++ 2003 FWIW.
As you know, the standard library rand() only returns an integer in the
range 0<=n<=RAND_MAX.
In fact, this problem is posed as an exercise by Andrew Koening in
Accelerated C++. It's Ex 7-9 and it's marked as "difficult" so I don't
feel too bad in asking for help!

Is there a standard solution to this? It must be quite a common
requirement, but I'm stumped.

Thanks,
Martin

If your range is greater than RAND_MAX then clearly you need to call rand()
several times. Does that help?

For instance

long big_rand = (RAND_MAX + 1)*(long)rand() + rand();

john

 

[Ivan Vecerina]

....
If your range is greater than RAND_MAX then clearly you need to call
rand() several times. Does that help?

For instance

long big_rand = (RAND_MAX + 1)*(long)rand() + rand();

Yes. This will work if your randomness requirements are not too high
( which shall be the case anyway if you even consider using std::rand() ).

If the final range is not a power of 2, you may also need to be careful
in the way you map the range (e.g. using a simple division/modulo will
increase the probability of some results compared to others).
See:
http://groups.google.com/[email protected]

Getting good random numbers is difficult, and gets even harder when
working on security-sensitive applications.

If you feel that you want more than std::rand() can provide, a good
solution might be to consider using another library. I would suggest
taking a look at http://www.boost.org/libs/random/index.html.


hth,
Ivan

 

[Method Man]

I am trying to write code that selects a random number in the range 0 to n,
where n can be substantially greater than the RAND_MAX on my system which is
32767. I am using VC++ 2003 FWIW.
As you know, the standard library rand() only returns an integer in the
range 0<=n<=RAND_MAX.
In fact, this problem is posed as an exercise by Andrew Koening in
Accelerated C++. It's Ex 7-9 and it's marked as "difficult" so I don't feel
too bad in asking for help!

Is there a standard solution to this? It must be quite a common requirement,
but I'm stumped.

Thanks,
Martin

Assume N < LONG_MAX is your upper limit. I would generate a random (double)
number between 0 and 1, then multiply by N and store it in a long. Untested
code:

#include <stdlib.h>

const long N = 987654321; /* upper limit */

int main(void) {
double d;
long result;
srand((unsigned) time(NULL));
d = rand() / RAND_MAX;
result = d * N;
}

 

[Martin]

Assume N < LONG_MAX is your upper limit. I would generate a random
(double)
number between 0 and 1, then multiply by N and store it in a long.
Untested
code:

#include <stdlib.h>

const long N = 987654321; /* upper limit */

int main(void) {
double d;
long result;
srand((unsigned) time(NULL));
d = rand() / RAND_MAX;
result = d * N;
}

Thanks, I can see the logic there and it seems to do the trick!

Martin

 

[chris]

Assume N < LONG_MAX is your upper limit. I would generate a random (double)
number between 0 and 1, then multiply by N and store it in a long. Untested
code:

#include <stdlib.h>

const long N = 987654321; /* upper limit */

int main(void) {
double d;
long result;
srand((unsigned) time(NULL));
d = rand() / RAND_MAX;
result = d * N;
}

You should be careful with code like this. While this will give you a
number between 1 and N, there are only RAND_MAX possible values it can
give you (in your case <40,000). Therefore the vast majority of numbers
will never occur. If this doesn't bother you thats fine. Just making
sure you are aware of it...

 

[me]

Assume N < LONG_MAX is your upper limit. I would generate a random (double)
number between 0 and 1, then multiply by N and store it in a long. Untested
code:

#include <stdlib.h>

const long N = 987654321; /* upper limit */

int main(void) {
double d;
long result;
srand((unsigned) time(NULL));
d = rand() / RAND_MAX;
result = d * N;
}

There's a problem with this code. Imagine, for example, you want a
random number between 0 and 256000, and you have an RNG that generates
numbers between 0 and 256. By your logic you could generate a random
number by doing (random() * 1000). But this would only generate a number
in the set {0,1000,2000,3000,...,254000,255000,256000}, and so would not
be random....

cheers

pjw

 

[Method Man]

Thanks, I can see the logic there and it seems to do the trick!

As others have mentioned, this code may work for your upper limit, but it
does not generate numbers in a uniform distribution (some numbers may never
get selected). See Ivan's post for alternate solutions.

 

[David Harmon]

I am trying to write code that selects a random number in the range 0 to n,
where n can be substantially greater than the RAND_MAX on my system

Get a better random number generator.
See chapter 22.7 in Stroustrup.
See the Boost Random library.

 

[Karl Heinz Buchegger]

As others have mentioned, this code may work for your upper limit, but it
does not generate numbers in a uniform distribution (some numbers may never
get selected). See Ivan's post for alternate solutions.

<nitpicking>
The above generates only 1 number: 0
(or was it 2: 0 and N? I never can remember if rand()'s
return value includes or does not include RAND_MAX)
</nitpicking>