Random Integers from 0 to 999

[Michael B Allen]

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]

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

Where is your shot at it? Without attribution, nobody knows
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

 

[Grumble]

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]

Where is your shot at it? Without attribution, nobody knows
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]

can be


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

 

[Chris Croughton]

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

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]

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

 

[Grumble]

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.

 

[CBFalconer]

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)

 

[Chris Croughton]

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
discard values out of range:

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

 

[CBFalconer]

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.

Since RAND_MAX is normally much larger than (max - min) that effect
is minimal. However, you can allow for it by:

unsigned int ranrange(unsigned int min, unsigned int max)
{
unsigned int t, d, n;

if (min > max) { /* No assert, just an interval */
t = min; min = max; max = t;
}
t = max - min + 1;
d = RAND_MAX / t;
d *= t;
do { /* discard the few biasing values */
n = rand(); /* assuming rand() unbiased */
} while (n > d);
return min + (int)((double)t * n/(1.0 + d));
} /* untested */

It probably requires tweaking for the minimum return from rand,
which may well be either 1 or 0.

 

[Andrey Tarasevich]

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

There's absolutely no way to implement the required functionality by a
stateless function that simply maps 'int' to 'int'. Regardless of how
you do it, some numbers will appear with higher probability than other
numbers. The version you provided is as "terrible" as the previous one
for the very same reason - for the same ranges of input and output
values some numbers will be "twice as likely to show up than other
numbers" (you should've tested it before posting here).

When [0, RAND_MAX] range is significantly wider than the requiested
[min, max] range, this is not really a problem. In other cases, only a
stateful mapping function will help.

 

[websnarf]

[...]
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));
}

This solution (which, unfortunately, is endorsed by the comp.lang.c
FAQ) is no better. As others have posted, you're up against the
pigeon-hole principle, you can't fix it by just changing the mapping in
some way.

And its a real problem in practice -- RAND_MAX need not be higher than
65535, and in most of the compilers on the most popular platform it is
indeed exactly this. I have a more complete summary of the issue here:

http://www.pobox.com/~qed/random.html

 

[Dave Thompson]

Rouben Rostamian wrote:

This solution (which, unfortunately, is endorsed by the comp.lang.c
FAQ) is no better. As others have posted, you're up against the
pigeon-hole principle, you can't fix it by just changing the mapping in
some way.

And its a real problem in practice -- RAND_MAX need not be higher than
65535, and in most of the compilers on the most popular platform it is
indeed exactly this. I have a more complete summary of the issue here:

http://www.pobox.com/~qed/random.html

Need not be higher than, and often is, 32767 (= minimum INT_MAX).

Although for a desired choice range of no more than about 30, I might
consider the <.1% nonuniformity acceptable.

- David.Thompson1 at worldnet.att.net

 

[CBFalconer]

Need not be higher than, and often is, 32767 (= minimum INT_MAX).

Although for a desired choice range of no more than about 30, I
might consider the <.1% nonuniformity acceptable.

AFAIK there is no specification for RAND_MIN, which will be at
least 1 for many implementations. If you require specific
characteristics the only answer is to supply your own random
implmentation. Even then you need to be aware of what is and is
not guaranteed. For example, 32 bit ints are not guaranteed,
contrary to Hsiehs (websnarf) hidden assumptions in at least some
of his code.

 

[Keith Thompson]

AFAIK there is no specification for RAND_MIN, which will be at
least 1 for many implementations.

[...]

There is no RAND_MIN. The standard says that rand() "computes a
sequence of pseudo-random integers in the range 0 to RAND_MAX".

If an implementation's rand() function never returns 0, the implementation
is either non-conforming or of poor quality.

Do you know of an implementation in which rand() never returns 0?

 

[CBFalconer]

AFAIK there is no specification for RAND_MIN, which will be at
least 1 for many implementations.

[...]

There is no RAND_MIN. The standard says that rand() "computes a
sequence of pseudo-random integers in the range 0 to RAND_MAX".

If an implementation's rand() function never returns 0, the
implementation is either non-conforming or of poor quality.

Do you know of an implementation in which rand() never returns 0?

Yes. Any Linear Congruential with a zero adder. Any CRC based
system.

 

[Eric Sosman]

AFAIK there is no specification for RAND_MIN, which will be at
least 1 for many implementations.

[...]

There is no RAND_MIN. The standard says that rand() "computes a
sequence of pseudo-random integers in the range 0 to RAND_MAX".

If an implementation's rand() function never returns 0, the implementation
is either non-conforming or of poor quality.

Do you know of an implementation in which rand() never returns 0?

The trouble is in the testing: If you sample three
hundred twenty-seven quadrillion rand() values and see
no zeroes, can you conclude that rand() will never, ever,
under any circumstances return a zero?

It's reminiscent of the demonstration that all crows are
black. You can travel the world observing crows and noting
that all seen are black; with each successive black crow your
confidence in the hypothesis increases. But "all crows are
black" is equivalent to "all non-black things are non-crows,"
so there's a less strenuous way to proceed: Just sit in your
armchair (none of that tedious travelling), cast your eyes
about you, and observe non-black objects in your field of view.
Behold the butterknife: a non-black non-crow that raises your
confidence. Behold the white cover of K&R, another non-crow:
your confidence swells as if certain spammed pharmaceuticals
had been used. Behold the pinkish appurtenances of the image
of Miss Download, overtly mammalian and hence not a crow: you
are ready to submit your thesis to a journal (and stop thinking
about that swelling, okay?). The upshot is that you can raise
your confidence in "all crows are black" without every observing
a single crow ...

 

[Keith Thompson]

AFAIK there is no specification for RAND_MIN, which will be at
least 1 for many implementations.

[...]

There is no RAND_MIN. The standard says that rand() "computes a
sequence of pseudo-random integers in the range 0 to RAND_MAX".

If an implementation's rand() function never returns 0, the
implementation is either non-conforming or of poor quality.

Do you know of an implementation in which rand() never returns 0?

Yes. Any Linear Congruential with a zero adder. Any CRC based
system.

Do you know of a specific C library implementation that uses an
algorithm in which rand() never returns 0?

Even the sample implementation in the standard (which isn't very good)
returns 0 every few thousand iterations.

As long as the internal state is bigger than the values returned,
you'll probably get 0 every now and then.

 

[CBFalconer]

AFAIK there is no specification for RAND_MIN, which will be at
least 1 for many implementations.

[...]

There is no RAND_MIN. The standard says that rand() "computes a
sequence of pseudo-random integers in the range 0 to RAND_MAX".

If an implementation's rand() function never returns 0, the implementation
is either non-conforming or of poor quality.

Do you know of an implementation in which rand() never returns 0?

The trouble is in the testing: If you sample three
hundred twenty-seven quadrillion rand() values and see
no zeroes, can you conclude that rand() will never, ever,
under any circumstances return a zero?

I am thinking of cases where the generation method is known, and
thus the lack of a zero can be guaranteed.

It's reminiscent of the demonstration that all crows are
black. You can travel the world observing crows and noting
that all seen are black; with each successive black crow your
confidence in the hypothesis increases. But "all crows are

Nah, it just confirms that all crows have a black side, which they
normally present to you.