Velocity Reviews > Random Integers from 0 to 999

# Random Integers from 0 to 999

Michael B Allen
Guest
Posts: n/a

 03-24-2005
Someone once posted the following macro on clc:

#define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)

Unfortunately it's flawed. If rand() returns RAND_MAX the result can be
one larger than b.

So can someone provide a *proper* macro (or function) that returns a
random integer between (actually in) a range of values? For example
randint(0, 999) could return:

0
10
777
999

Mike

Michael Mair
Guest
Posts: n/a

 03-24-2005
Michael B Allen wrote:
> Someone once posted the following macro on clc:
>
> #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
>
> Unfortunately it's flawed. If rand() returns RAND_MAX the result can be
> one larger than b.
>
> So can someone provide a *proper* macro (or function) that returns a
> random integer between (actually in) a range of values? For example
> randint(0, 999) could return:
>
> 0
> 10
> 777
> 999

from which source this comes.

#define RANDINT(a,b) (a)+(((b)-(a)+1)*(double)rand()/(1u+RAND_MAX))

may serve you better; note the double which serves you well
if RAND_MAX has more digits than float can represent.
There are other deficiencies for this approach; why don't you
use the suggestions of, say, Lawrence Kirby (or other regulars)
which make all values equally probable?
Apart from that: I would rather use a function for this purpose.
If you need many random numbers, consider filling an array and
retrieving from there until it is "used up", then refilling.

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

Grumble
Guest
Posts: n/a

 03-24-2005
Michael B Allen wrote:

> Someone once posted the following macro on clc:
>
> #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
>
> Unfortunately it's flawed. If rand() returns RAND_MAX the result can be
> one larger than b.
>
> So can someone provide a *proper* macro (or function) that returns a
> random integer between (actually in) a range of values? For example
> randint(0, 999) could return:
>
> 0
> 10
> 777
> 999

int randint(int min, int max)
{
assert(min <= max);
return min + rand() % (max - min + 1);
}

0 <= rand() <= RAND_MAX
0 <= rand()%(max-min+1) < max-min+1
0 <= rand()%(max-min+1) <= max-min
min <= min+rand()%(max-min+1) <= max

Mark Piffer
Guest
Posts: n/a

 03-24-2005
Michael Mair wrote:
> Michael B Allen wrote:
> > Someone once posted the following macro on clc:
> >
> > #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
> >
> > Unfortunately it's flawed. If rand() returns RAND_MAX the result

can be
> > one larger than b.
> >

>
> from which source this comes.
>
> #define RANDINT(a,b) (a)+(((b)-(a)+1)*(double)rand()/(1u+RAND_MAX))
>
> may serve you better; note the double which serves you well
> if RAND_MAX has more digits than float can represent.
> There are other deficiencies for this approach; why don't you
> use the suggestions of, say, Lawrence Kirby (or other regulars)
> which make all values equally probable?
> Apart from that: I would rather use a function for this purpose.
> If you need many random numbers, consider filling an array and
> retrieving from there until it is "used up", then refilling.
>

Unluckily, both, your and Grumble's snippet produce UB due to integer
overflow when RAND_MAX happens to equal INT_MAX (like on all my 16-Bit
compilers) and the arguments are (0,RAND_MAX). It looks like

#define RANDINT(a,b)\
((b)-(a)==RAND_MAX?(a)+rand()a)+rand()%((b)-(a)+1))

will do it, although the distribution will be abysmal. Then again, for
embedded architectures, where neither floating point nor much RAM is an
option, I use such generators exactly for their simplicity and not the
randomness. Most of my test data just needs to be better than
iterative, but not truly random. Where "real" randomness is needed I go
and ask the big boys (the mathematicians); uniform distributions won't
cut it most of the time anyway.

Mark

Michael Mair
Guest
Posts: n/a

 03-24-2005
Mark Piffer wrote:
> Michael Mair wrote:
>
>>Michael B Allen wrote:
>>
>>>Someone once posted the following macro on clc:
>>>
>>>#define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
>>>
>>>Unfortunately it's flawed. If rand() returns RAND_MAX the result

>
> can be
>
>>>one larger than b.
>>>

>>
>>from which source this comes.
>>
>> #define RANDINT(a,b) (a)+(((b)-(a)+1)*(double)rand()/(1u+RAND_MAX))
>>
>>may serve you better; note the double which serves you well
>>if RAND_MAX has more digits than float can represent.
>>There are other deficiencies for this approach; why don't you
>>use the suggestions of, say, Lawrence Kirby (or other regulars)
>>which make all values equally probable?
>>Apart from that: I would rather use a function for this purpose.
>>If you need many random numbers, consider filling an array and
>>retrieving from there until it is "used up", then refilling.

>
> Unluckily, both, your and Grumble's snippet produce UB due to integer
> overflow when RAND_MAX happens to equal INT_MAX (like on all my 16-Bit
> compilers) and the arguments are (0,RAND_MAX). It looks like
>
> #define RANDINT(a,b)\
> ((b)-(a)==RAND_MAX?(a)+rand()a)+rand()%((b)-(a)+1))
>
> will do it, although the distribution will be abysmal. Then again, for
> embedded architectures, where neither floating point nor much RAM is an
> option, I use such generators exactly for their simplicity and not the
> randomness. Most of my test data just needs to be better than
> iterative, but not truly random. Where "real" randomness is needed I go
> and ask the big boys (the mathematicians); uniform distributions won't
> cut it most of the time anyway.

You are right, I forgot to mention this particular problem and
did not correct it; however IIRC it is covered in the mentioned
message by Lawrence Kirby.
If I have too much time on my hands, I will search for it.
I still hold that writing a function is the better way; you
can cut off the excess random values and handle special cases in a
transparent way.

If we speak of overkill: The Mersenne Twister should do for
a start

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

Chris Croughton
Guest
Posts: n/a

 03-24-2005
On Thu, 24 Mar 2005 09:30:34 +0100, Grumble
<(E-Mail Removed)> wrote:

> Michael B Allen wrote:
>
>> Someone once posted the following macro on clc:
>>
>> #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
>>
>> Unfortunately it's flawed. If rand() returns RAND_MAX the result can be
>> one larger than b.

The simple solution is to use (RAND_MAX+1) as the divisor. However, it
has the same probem as below.

>> So can someone provide a *proper* macro (or function) that returns a
>> random integer between (actually in) a range of values? For example
>> randint(0, 999) could return:
>>
>> 0
>> 10
>> 777
>> 999

>
> int randint(int min, int max)
> {
> assert(min <= max);
> return min + rand() % (max - min + 1);
> }

That just uses different bits to do the same thing (except that you
corrected the "off by one" error). However, there are a number of poor
implementations of rand() where the bottom bits are a lot more
predictable than the higher ones (rand() % 4 returning a continuous
repeated sequence of 0, 1, 2, 3 in one of them!).

> 0 <= rand() <= RAND_MAX
> 0 <= rand()%(max-min+1) < max-min+1
> 0 <= rand()%(max-min+1) <= max-min
> min <= min+rand()%(max-min+1) <= max

If the range is not a submultiple of (RAND_MAX + 1) then it does not
give equal probabilities of all of the numbers. For instance, take a
small RAND_MAX of 7 (0 <= rand() <= 7) and a range of [0..4]:

rand() randint()
0 0
1 1
2 2
3 3
4 4
5 0
6 1
7 2

results 0..2 occur twice as often as 3..4. Granted that when RAND_MAX
is very much bigger than the range the error becomes smaller, it is
still there (the potential error is range/(RAND_MAX+1)).

Chris C

Rouben Rostamian
Guest
Posts: n/a

 03-24-2005
In article <d1ttra\$l46\$(E-Mail Removed)>,
Grumble <(E-Mail Removed)> wrote:
>
>int randint(int min, int max)
>{
> assert(min <= max);
> return min + rand() % (max - min + 1);
>}
>
>0 <= rand() <= RAND_MAX
>0 <= rand()%(max-min+1) < max-min+1
>0 <= rand()%(max-min+1) <= max-min
>min <= min+rand()%(max-min+1) <= max

That's a terrible way of generating "random" numbers.

When we ask for a "random number" in the range min..max,
we want every number within that range to occur with equal
probability.

The following example shows that your method does not give a
uniformly distributed random number.

For the sake of illustration, let's say RAND_MAX is 7.
Suppose you want random numbers in the set {0,1,2,3,4,5}.

rand() randint()
0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4
5 -> 5
6 -> 0
7 -> 1

Therefore the numbers 0 and 1 are twice as likely to show up
than other numbers.

Here is a better way:

int randint(int min, int max)
{
assert(min <= max);
return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX));
}

--
Rouben Rostamian

Grumble
Guest
Posts: n/a

 03-24-2005
Rouben Rostamian wrote:

> Grumble wrote:
>
>> int randint(int min, int max)
>> {
>> assert(min <= max);
>> return min + rand() % (max - min + 1);
>> }

>
> That's a terrible way of generating "random" numbers.
>
> When we ask for a "random number" in the range min..max,
> we want every number within that range to occur with equal
> probability.
>
> The following example shows that your method does not give a
> uniformly distributed random number.
>
> For the sake of illustration, let's say RAND_MAX is 7.
> Suppose you want random numbers in the set {0,1,2,3,4,5}.
> Then according to your algorithm:
>
> rand() randint()
> 0 -> 0
> 1 -> 1
> 2 -> 2
> 3 -> 3
> 4 -> 4
> 5 -> 5
> 6 -> 0
> 7 -> 1
>
> Therefore the numbers 0 and 1 are twice as likely to show up
> than other numbers.
>
> Here is a better way:
>
> int randint(int min, int max)
> {
> assert(min <= max);
> return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX));
> }

You algorithm is as "broken" as mine because of a fundamental problem:

If you try to place 8 balls in 6 buckets, then, no matter how you slice
and dice it, you'll end up with more balls in some buckets. The only way
out is to discard 2 balls.

--
Regards, Grumble

CBFalconer
Guest
Posts: n/a

 03-24-2005
Michael B Allen wrote:
>
> Someone once posted the following macro on clc:
>
> #define randint(a,b) (a)+(((b)-(a)+1)*(float)rand()/RAND_MAX)
>
> Unfortunately it's flawed. If rand() returns RAND_MAX the result
> can be one larger than b.

#define ranrange(a, b) (int)((a) + rand()/((double)RAND_MAX + 1) \
* ((b) - (a) + 1))

assuming 0 == rand() can occur. Many systems will never return 0,
so:

#define ranrange(a, b) (int)((a) + (rand() - 1)/((double)RAND_MAX)
\
* ((b) - (a) + 1))

(untested)

>
> So can someone provide a *proper* macro (or function) that returns
> a random integer between (actually in) a range of values?
> For example randint(0, 999) could return:
>
> 0
> 10
> 777
> 999

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the

Chris Croughton
Guest
Posts: n/a

 03-24-2005
On Thu, 24 Mar 2005 15:09:47 +0000 (UTC), Rouben Rostamian
<(E-Mail Removed)> wrote:

> In article <d1ttra\$l46\$(E-Mail Removed)>,
> Grumble <(E-Mail Removed)> wrote:
>>
>>int randint(int min, int max)
>>{
>> assert(min <= max);
>> return min + rand() % (max - min + 1);
>>}
>>
>>0 <= rand() <= RAND_MAX
>>0 <= rand()%(max-min+1) < max-min+1
>>0 <= rand()%(max-min+1) <= max-min
>>min <= min+rand()%(max-min+1) <= max

>
> That's a terrible way of generating "random" numbers.
>
> When we ask for a "random number" in the range min..max,
> we want every number within that range to occur with equal
> probability.
>
> The following example shows that your method does not give a
> uniformly distributed random number.
>
> For the sake of illustration, let's say RAND_MAX is 7.
> Suppose you want random numbers in the set {0,1,2,3,4,5}.
> Then according to your algorithm:
>
> rand() randint()
> 0 -> 0
> 1 -> 1
> 2 -> 2
> 3 -> 3
> 4 -> 4
> 5 -> 5
> 6 -> 0
> 7 -> 1
>
> Therefore the numbers 0 and 1 are twice as likely to show up
> than other numbers.
>
> Here is a better way:
>
> int randint(int min, int max)
> {
> assert(min <= max);
> return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX));
> }

Why is that any better? Assuming your example of RAND_MAX==7, and
wanting numbers in the set [0,5]:

rand() randint()
0 -> 0*6/8 0/8 -> 0
1 -> 1*6/8 6/8 -> 0
2 -> 2*6/8 12/8 -> 1
3 -> 3*6/8 18/8 -> 2
4 -> 4*6/8 24/8 -> 3
5 -> 5*6/8 30/8 -> 3
6 -> 6*6/8 36/8 -> 4
7 -> 7*6/8 42/8 -> 5

All you've done is to change it so that 0 and 3 get the extra hits
instead of 0 and 1. OK, it looks slightly more uniform (the mean will be
better,2.25 instead of 2, it should be 2.5) but it's still got the same
problem of two of the numbers occuring twice as often as the others.

A way of getting round the problem is to use an iterative method and

int randint(int min, int max)
{
unsigned range = max - min + 1;
int bits = 1;
int result;
assert(range > 0 && range <= RAND_MAX);
while (range-1 > bits)
bits = bits*2 + 1;
do result = rand() & bits; while (result > range);
return result + min;
}

This only works if RAND_INT is 2^n - 1, but that's the case on all
implementations I've found. It is also susceptible to the quality of
the lower bits of rand(), which on some implementations are not very
random...

Chris C