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)r and()/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]

Re: Random Integers from 0 to 999

Michael B Allen wrote:[color=blue]
> Someone once posted the following macro on clc:
>
> #define randint(a,b) (a)+(((b)-(a)+1)*(float)r and()/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[/color]

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
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Grumble]

Re: Random Integers from 0 to 999

Michael B Allen wrote:
[color=blue]
> Someone once posted the following macro on clc:
>
> #define randint(a,b) (a)+(((b)-(a)+1)*(float)r and()/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[/color]

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]

Re: Random Integers from 0 to 999

Michael Mair wrote:[color=blue]
> Michael B Allen wrote:[color=green]
> > Someone once posted the following macro on clc:
> >
> > #define randint(a,b) (a)+(((b)-(a)+1)*(float)r and()/RAND_MAX)
> >
> > Unfortunately it's flawed. If rand() returns RAND_MAX the result[/color][/color]
can be[color=blue][color=green]
> > one larger than b.
> >[/color]
>
> 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.
>[/color]

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)+r and()%((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]

Re: Random Integers from 0 to 999

Mark Piffer wrote:[color=blue]
> Michael Mair wrote:
>[color=green]
>>Michael B Allen wrote:
>>[color=darkred]
>>>Someone once posted the following macro on clc:
>>>
>>>#define randint(a,b) (a)+(((b)-(a)+1)*(float)r and()/RAND_MAX)
>>>
>>>Unfortunatel y it's flawed. If rand() returns RAND_MAX the result[/color][/color]
>
> can be
>[color=green][color=darkred]
>>>one larger than b.
>>>[/color]
>>
>>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.[/color]
>
> 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)+r and()%((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.[/color]

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]

Re: Random Integers from 0 to 999

On Thu, 24 Mar 2005 09:30:34 +0100, Grumble
<devnull@kma.eu .org> wrote:
[color=blue]
> Michael B Allen wrote:
>[color=green]
>> Someone once posted the following macro on clc:
>>
>> #define randint(a,b) (a)+(((b)-(a)+1)*(float)r and()/RAND_MAX)
>>
>> Unfortunately it's flawed. If rand() returns RAND_MAX the result can be
>> one larger than b.[/color][/color]

The simple solution is to use (RAND_MAX+1) as the divisor. However, it
has the same probem as below.
[color=blue][color=green]
>> 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[/color]
>
> int randint(int min, int max)
> {
> assert(min <= max);
> return min + rand() % (max - min + 1);
> }[/color]

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!).
[color=blue]
> 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[/color]

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]

Re: Random Integers from 0 to 999

In article <d1ttra$l46$1@n ews-rocq.inria.fr>,
Grumble <devnull@kma.eu .org> wrote:[color=blue]
>
>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[/color]

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

--
Rouben Rostamian

[Grumble]

Re: Random Integers from 0 to 999

Rouben Rostamian wrote:
[color=blue]
> Grumble wrote:
>[color=green]
>> int randint(int min, int max)
>> {
>> assert(min <= max);
>> return min + rand() % (max - min + 1);
>> }[/color]
>
> 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)) ;
> }[/color]

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]

Re: Random Integers from 0 to 999

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

#define ranrange(a, b) (int)((a) + rand()/((double)RAND_M AX + 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_M AX)
\
* ((b) - (a) + 1))

(untested)
[color=blue]
>
> 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[/color]

--
"If you want to post a followup via groups.google.c om, 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
"Reply" at the bottom of the article headers." - Keith Thompson

[CBFalconer]

Re: Random Integers from 0 to 999

Grumble wrote:[color=blue]
> Rouben Rostamian wrote:[color=green]
>> Grumble wrote:
>>[color=darkred]
>>> int randint(int min, int max)
>>> {
>>> assert(min <= max);
>>> return min + rand() % (max - min + 1);
>>> }[/color]
>>[/color][/color]
.... snip ...[color=blue][color=green]
>>
>> 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)) ;
>> }[/color]
>
> 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.[/color]

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

unsigned int ranrange(unsign ed 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.

--
"If you want to post a followup via groups.google.c om, 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
"Reply" at the bottom of the article headers." - Keith Thompson

[Andrey Tarasevich]

Re: Random Integers from 0 to 999

Rouben Rostamian wrote:[color=blue]
> ...
> 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)) ;
> }
> ...[/color]

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.

--
Best regards,
Andrey Tarasevich

[Chris Croughton]

Re: Random Integers from 0 to 999

On Thu, 24 Mar 2005 15:09:47 +0000 (UTC), Rouben Rostamian
<rouben@pc18.ma th.umbc.edu> wrote:
[color=blue]
> In article <d1ttra$l46$1@n ews-rocq.inria.fr>,
> Grumble <devnull@kma.eu .org> wrote:[color=green]
>>
>>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[/color]
>
> 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)) ;
> }[/color]

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

[websnarf@gmail.com]

Re: Random Integers from 0 to 999

Rouben Rostamian wrote:[color=blue]
> [...]
> 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)) ;
> }[/color]

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

---
Paul Hsieh

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

http://bstring.sf.net/

[Dave Thompson]

Re: Random Integers from 0 to 999

On 26 Mar 2005 16:50:31 -0800, websnarf@gmail. com wrote:
[color=blue]
> Rouben Rostamian wrote:[/color]
<snip>[color=blue][color=green]
> > return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX)) ;[/color][/color]
<snip>[color=blue]
> 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[/color]

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

[CBFalconer]

Re: Random Integers from 0 to 999

Dave Thompson wrote:[color=blue]
> On 26 Mar 2005 16:50:31 -0800, websnarf@gmail. com wrote:[color=green]
>> Rouben Rostamian wrote:[/color]
> <snip>[color=green][color=darkred]
>>> return min + (int)((max-min+1.0)*rand()/(1.0+RAND_MAX)) ;[/color][/color]
> <snip>[color=green]
>> 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[/color]
> summary of the issue here:[color=green]
>>
>> http://www.pobox.com/~qed/random.html[/color]
>
> 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.[/color]

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.

--
"If you want to post a followup via groups.google.c om, 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
"Reply" at the bottom of the article headers." - Keith Thompson