G
Guest
How to generate a random integer that is bigger than RAND_MAX.
the RAND_MAX is the max of rand function. and equal to 0x7fff
the RAND_MAX is the max of rand function. and equal to 0x7fff
M
Markus Schoder
海风 said:
This is a quality of implementation issue. The implementation I am
using has RAND_MAX equal to 0x7fffffff.
Anyway you can use the boost random library which was by the way
accepted into the draft C++0x standard.
S
S. I. Becker
海风 said:
If RAND_MAX = 0x7fff... then you can use:
unsigned int r = ~rand();
If (as I believe is common) RAND_MAX is the largest [signed] int (e.g.
0x7fff in 16bit, 0x7fffffff in 32 bit), then you get a random number
from RAND_MAX + 1 to 2 * RAND_MAX - 1 (0x8000... to 0xffff...) inclusive.
Proof left as an exercise to the reader.
HTH,
Stewart
O
osmium
?? said:
Use a shift operator and add the result of two (or more) calls on rand()
into a larger type. rand() returns a collection of random *bits*.
R
Richard Herring
osmium said:
But be aware that the results of consecutive calls to rand() may have
undesirable correlations. Whether this matters will depend on your
problem domain.
J
Jack Saalweachter
Sadly, this is not a sure thing. For instance, on Windows [VC++ 2003],S. I. Becker said:海风 said:
If RAND_MAX = 0x7fff... then you can use:
unsigned int r = ~rand();
If (as I believe is common) RAND_MAX is the largest [signed] int (e.g.
0x7fff in 16bit, 0x7fffffff in 32 bit), then you get a random number
from RAND_MAX + 1 to 2 * RAND_MAX - 1 (0x8000... to 0xffff...) inclusive.
Proof left as an exercise to the reader.
HTH,
Stewart
RAND_MAX is only 0x7fff, despite the fact that my integers are most
assuredly 32 bits.
So, don't count on any relation between RAND_MAX and INT_MAX. While
there may be a few non-Standard features which are essentially as
portable as you like (e.g. long long), RAND_MAX being equal to INT_MAX
isn't one of them.
Jack
S
Sjouke Burry
You can also make 1 random long integerMarkus said:
out of 2 short ones.
S
Steve Pope
On what system is RAND_MAX that small? I'm seeing 2^31 - 1
on gcc/linux, which is 0x7fffffff.
Steve
O
osmium
Steve Pope said:
I can't begin to imagine why the answer to that question would be useful to
anyone. But Turbo C++ for Windows was one such platform, and I suspect their
are many more.
There used to be a computer in which 16 bits was considered a "word". One
company liked it so much they even made it a part of their identifier naming
conventions.
S
S. I. Becker
Jack said:
However you do still get what was asked for: a random that is bigger
than RAND_MAX. This will always be the case since RAND_MAX is always a
positive [signed] int. It's most significant bit is 0. NOTing it
therefore gives a value with the most significant bit as 1, which as an
unsigned int is larger than RAND_MAX. The range you get is 2^n -
RAND_MAX - 1 to 2^n - 1. (where n is the length of an int in bits).
Something that will always work in the range I quoted is:
unsigned int r = 1 + RAND_MAX + rand();
but I don't consider this as elegant as the solution above. However,
this should be just as fast since 1 + RAND_MAX should be optimised to a
single constant, yielding just a single addition after the rand()
function call.
Stewart
S
Steve Hicks
海风 said:
You could write your own generator which can easily be at least as good
as the one provided by your standard library. "Numerical Recipes in
C++" (or any other language) has a pretty good treatment of this. In
particular, you can start with a seed and iterate, using
X_{n+1} = a * X_n + c (mod 2^32),
for sufficient choices of a and c (evidently, a=1664525 and
c=1013904223 work well). If your integers are 32-bit, then the mod
happens automatically when you multiply and they overflow (and even if
they are longer than 32 bits, you can mask out the higher bits). Thus,
a quick and dirty function would be
unsigned int random() {
static unsigned int x;
x = 1664525L * x + 1013904223L;
return x;
}
-steve
H
Howard
Sjouke Burry said:
But you have no idea if the resulting stream of numbers this would produce
actually exhibits the same quality of "randomness" (using whatever measures
you've chosen to verify the randomness of the original number stream). You
may find a bias of some sort introduced by this method.
-Howard
S
Steve Pope
osmium said:
As was stated upthread, this is a quality of implementation issue.
I have seen some weak implementations of rand() and random(),
including a linux version that could give the same sequence
for different values of seed. Having rand()'s range vastly smaller
than the rane of an int is something of a red flag.
That being said, something like
(rand() & 0x7fff) | ((rand() & 0x7fff) << 15)
is worth a try.
Steve
Steve