Random number if range is greater than RAND_MAX?

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

"Martin" <martin@nospam.com> wrote in message
news:41971aa8$0$21877$61ce578d@news.syd.swiftdsl.c om.au...[color=blue]
>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[/color]

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

"John Harrison" <john_andronicus@hotmail.com> wrote in message
news:2vol7lF2iq2ieU1@uni-berlin.de...[color=blue]
>
> "Martin" <martin@nospam.com> wrote in message
> news:41971aa8$0$21877$61ce578d@news.syd.swiftdsl.c om.au...[color=green]
>>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.[/color][/color]
....[color=blue]
> 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();[/color]

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/groups?thre...ing.google.com

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
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Brainbench MVP for C++ <> http://www.brainbench.com

"Martin" <martin@nospam.com> wrote in message
news:41971aa8$0$21877$61ce578d@news.syd.swiftdsl.c om.au...[color=blue]
> I am trying to write code that selects a random number in the range 0 to[/color]
n,[color=blue]
> where n can be substantially greater than the RAND_MAX on my system which[/color]
is[color=blue]
> 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[/color]
feel[color=blue]
> too bad in asking for help!
>
> Is there a standard solution to this? It must be quite a common[/color]
requirement,[color=blue]
> but I'm stumped.
>
> Thanks,
> Martin
>
>[/color]

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;
}

"Method Man" <a@b.c> wrote in message
news:kDFld.9495$hp3.1058784@read2.cgocable.net...[color=blue]
>
> "Martin" <martin@nospam.com> wrote in message
> news:41971aa8$0$21877$61ce578d@news.syd.swiftdsl.c om.au...[color=green]
>> I am trying to write code that selects a random number in the range 0 to[/color]
> n,[color=green]
>> where n can be substantially greater than the RAND_MAX on my system which[/color]
> is[color=green]
>> 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[/color]
> feel[color=green]
>> too bad in asking for help!
>>
>> Is there a standard solution to this? It must be quite a common[/color]
> requirement,[color=green]
>> but I'm stumped.
>>
>> Thanks,
>> Martin
>>
>>[/color]
>
> 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;
> }[/color]

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

Martin

Method Man wrote:[color=blue]
> "Martin" <martin@nospam.com> wrote in message
> news:41971aa8$0$21877$61ce578d@news.syd.swiftdsl.c om.au...
>[color=green]
>>I am trying to write code that selects a random number in the range 0 to[/color]
>
> n,
>[color=green]
>>where n can be substantially greater than the RAND_MAX on my system which[/color]
>
> is
>[color=green]
>>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[/color]
>
> feel
>[color=green]
>>too bad in asking for help!
>>
>>Is there a standard solution to this? It must be quite a common[/color]
>
> requirement,
>[color=green]
>>but I'm stumped.
>>
>>Thanks,
>>Martin
>>
>>[/color]
>
>
> 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;
> }
>[/color]

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...

Method Man wrote:[color=blue]
> "Martin" <martin@nospam.com> wrote in message
> news:41971aa8$0$21877$61ce578d@news.syd.swiftdsl.c om.au...
>[color=green]
>>I am trying to write code that selects a random number in the range 0 to[/color]
>
> n,
>[color=green]
>>where n can be substantially greater than the RAND_MAX on my system which[/color]
>
> is
>[color=green]
>>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[/color]
>
> feel
>[color=green]
>>too bad in asking for help!
>>
>>Is there a standard solution to this? It must be quite a common[/color]
>
> requirement,
>[color=green]
>>but I'm stumped.
>>
>>Thanks,
>>Martin
>>
>>[/color]
>
>
> 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;
> }
>
>[/color]
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

"Martin" <martin@nospam.com> wrote in message
news:41973027$0$21870$61ce578d@news.syd.swiftdsl.c om.au...[color=blue]
>
> "Method Man" <a@b.c> wrote in message
> news:kDFld.9495$hp3.1058784@read2.cgocable.net...[color=green]
> >
> > "Martin" <martin@nospam.com> wrote in message
> > news:41971aa8$0$21877$61ce578d@news.syd.swiftdsl.c om.au...[color=darkred]
> >> I am trying to write code that selects a random number in the range 0[/color][/color][/color]
to[color=blue][color=green]
> > n,[color=darkred]
> >> where n can be substantially greater than the RAND_MAX on my system[/color][/color][/color]
which[color=blue][color=green]
> > is[color=darkred]
> >> 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[/color]
> > feel[color=darkred]
> >> too bad in asking for help!
> >>
> >> Is there a standard solution to this? It must be quite a common[/color]
> > requirement,[color=darkred]
> >> but I'm stumped.
> >>
> >> Thanks,
> >> Martin
> >>
> >>[/color]
> >
> > 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;
> > }[/color]
>
> Thanks, I can see the logic there and it seems to do the trick!
>[/color]

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.

On Sun, 14 Nov 2004 16:43:34 +0800 in comp.lang.c++, "Martin" <martin@nospam.com> wrote,[color=blue]
>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[/color]

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

Method Man wrote:[color=blue]
>[color=green][color=darkred]
> > > 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;
> > > }[/color]
> >
> > Thanks, I can see the logic there and it seems to do the trick!
> >[/color]
>
> 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.[/color]

<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>

--
Karl Heinz Buchegger
kbuchegg@gascad.at