Random Integer Numbers
Pete Becker
says...
>
>Hello netters, I need some input regarding random numbers...
>
>I have 13 array locations. Let's call them: n[0], n[1], n[2],....,
>n[12]. I want to RANDOMLY fill those locations with integers
>from 0 to 12.
>
>i.e. n[0] = 2 n[4] = 1 n[8] = 10 n[12] = 9
> n[1] = 6 n[5] = 0 n[9] = 12
> n[2] = 7 n[6] = 3 n[10] = 5
> n[3] = 11 n[7] = 4 n[11] = 8
>
>Notice that the number having been assigned to any previous array locations
>can NOT BE REPEATED or reassigned to other locations.
>
>I used this approach to generate the random numbers:
>
> while (i<=12) {
> n[i] = ((rand()/RAND_MAX)+0.05) * 12; /* This gives int from 0 to 12 */
> /* No problem yet */
>
> ..... /* Here comes the problem ! Suppose the generator gives
> ..... * the same integer value, I want it to regenerate again
> ..... * until it gives a different value from the previous
> ..... * ones...
> ..... */
>
> i++;
> }
>
>Well, you probably will tell me to use "if" or loop statement to compare the
>values in each array location until all locations are RANDOMLY filled
>with different numbers from 0 to 12.
>
>My questions are:
>1. If any of you (computer scientist?) have ever done almost a similar thing,
> could you let me know the FASTEST way to fill those array locations ?
>2. If I use "if" and loop statement, it seems to me that comparing &
> regenerating may consume time too much after the array element number 10,
> for example, [because we only have two candidates left in that case:
> int number 11, and 12.]
>
>This may be a trivial problem for some of you but I'll appreciate if you can
>email me your ideas. Sending me a source code will be helpful.
Read any of the numerous discussions in this newsgroup about how to shuffle a
deck of cards.
John Automo
my questions. I tried your suggestions, and it worked wonderfully.
John
Gene Wirchenko
them. i.e.
array[0]=0;
array[1]=1;
...
shuffle(array,13); /* write this */
Sincerely,
Gene Wirchenko
--
"'Bugs, Mr. Rico! Zillions of 'em! ...'"
-Robert A. Heinlein, "Starship Troopers"
mag
>
>Hello netters, I need some input regarding random numbers...
>
>I have 13 array locations. Let's call them: n[0], n[1], n[2],....,
>n[12]. I want to RANDOMLY fill those locations with integers
>from 0 to 12.
>
>i.e. n[0] = 2 n[4] = 1 n[8] = 10 n[12] = 9
> n[1] = 6 n[5] = 0 n[9] = 12
> n[2] = 7 n[6] = 3 n[10] = 5
> n[3] = 11 n[7] = 4 n[11] = 8
>
>Notice that the number having been assigned to any previous array locations
>can NOT BE REPEATED or reassigned to other locations.
>
>I used this approach to generate the random numbers:
>
> while (i<=12) {
> n[i] = ((rand()/RAND_MAX)+0.05) * 12; /* This gives int from 0 to 12 */
Think of it as a shuffling problem. I would use the following approach.
int n[13];
int i, j, nTemp;
for (i = 0; i < 13; i++)
n[i] = i;
for (i = 0; i < 13; i++)
{
j = ((float)rand() / RAND_MAX) * 13;
nTemp = n[j];
n[j] = n[i];
n[i] = nTemp;
}
--
MAG
http:/www.eskimo.com/~mag/index.html
/* ********************************************************
To understand recursion one must first understand recursion
******************************************************** */
Jerry Coffin
>Think of it as a shuffling problem. I would use the following approach.
>int n[13];
>int i, j, nTemp;
>for (i = 0; i < 13; i++)
> n[i] = i;
>for (i = 0; i < 13; i++)
> {
> j = ((float)rand() / RAND_MAX) * 13;
> nTemp = n[j];
> n[j] = n[i];
> n[i] = nTemp;
> }
This method of producing random numbers within a range produces some
skew, much like using a modulus does, except that it's often bigger and
slower due to using floating point arithmetic. Consider the following
as an alternative:
#include <stdlib.h>
int rand_lim(int limit) {
/* return a random number between 0 and limit inclusive.
**/
int divisor = RAND_MAX / (limit + 1);
int retval;
while (limit+1 ==(retval= rand() / divisor))
;
return retval;
}
In this function, the numbers which would otherwise produce a skew are
those that are equal to limit+1, and are ignored. Note that despite
reducing the range of the generator, this effectively reduces its
period, as some numbers are are ignored. However, for many purposes,
the period is typically enough greater than the range (or the number of
uses in a single run) that this is unlikely to have much effect. If
you're worried enough about accuracy that a reduction in period isn't
acceptable, then most likely the skew is even less acceptable, so you'll
likely simply want to use the same sort of front end but have it call a
generator with substantially greater period.
Later,
Jerry.
/* I can barely express my own opinions; I certainly can't
* express anybody else's.
*
* The universe is a figment of its own imagination.
*/
Pete Becker
Unfortunately, this doesn't eliminate the skew. For example, suppose you have
a random number generator that generates values uniformly distributed from 0
to 6 inclusive. For this generator, RAND_MAX would be 6. Now let's say
you're trying to generate values from 0 to 4. That is, limit is 4. Whenever
the generator produces a value less than 5 the function returns it. That's
fine. When the generator produces 5 the test against limit+1 discards the
value and the function tries again. When the generator produces 6 the test
allows it and the function returns. So you end up with a uniform selection of
the values in { 0, 1, 2, 3, 4, 6 }.
The trick to making this sort of thing work is to figure out what
range of generated values will map uniformly over the target range and discard
any generated values outside that range. The simplest way is to simply discard
any value outside the target range:
int res = rand();
while( res > limit )
res = rand();
This will usually be rather slow, 'cause it discards lots of values when limit
is small. A better approach is to accept a range from 0 up to the largest
multiple of limit that is smaller than RAND_MAX (this would look a lot clearer
if limit were the number of values desired instead of the largest acceptable
value. Most of those +1's would go away...):
int max = ((RAND_MAX+1)/(limit+1))*(limit+1);
int res = rand();
while( res >= max )
res = rand();
return res % (limit+1);
Jerry Coffin
[ ... ]
>>This method of producing random numbers within a range produces some
>>skew, much like using a modulus does, except that it's often bigger and
>>slower due to using floating point arithmetic. Consider the following
>>as an alternative:
>>
>>#include <stdlib.h>
>>
>>int rand_lim(int limit) {
>>/* return a random number between 0 and limit inclusive.
>>**/
>>
>> int divisor = RAND_MAX / (limit + 1);
>> int retval;
>>
>> while (limit+1 ==(retval= rand() / divisor))
>> ;
>> return retval;
>>}
[ ... ]
>Unfortunately, this doesn't eliminate the skew. For example, suppose you have
>a random number generator that generates values uniformly distributed from 0
>to 6 inclusive. For this generator, RAND_MAX would be 6. Now let's say
>you're trying to generate values from 0 to 4. That is, limit is 4. Whenever
>the generator produces a value less than 5 the function returns it. That's
>fine. When the generator produces 5 the test against limit+1 discards the
>value and the function tries again. When the generator produces 6 the test
>allows it and the function returns. So you end up with a uniform selection of
>the values in { 0, 1, 2, 3, 4, 6 }.
Oops - you're right - it should be using >= instead of ==. I'm not at
all sure the selection of 6 would be uniform, but I'm not at all sure.
> The trick to making this sort of thing work is to figure out what
>range of generated values will map uniformly over the target range and discard
>any generated values outside that range. The simplest way is to simply discard
>any value outside the target range:
> int res = rand();
> while( res > limit )
> res = rand();
>This will usually be rather slow, 'cause it discards lots of values when limit
>is small.
"rather" slow ? I s'pose maybe it's just me, but it looks like it could
be horrendously slow. For an attempt at rolling a die, with a
RAND_MAX==32767, on average it should generate roughly 5400 numbers to
actually return one. I'd call a 3+ orders of magnitude slow-down more
than "rather slow", even with an average machine it should still be
producing output in a matter of milliseconds. However, with a random
number generator with a larger RAND_MAX, this could be completely
unreasonable in a big hurry - assuming a RAND_MAX of 2**32-1, you end up
with nearly 9 orders of magnitude slow-down. On an older machine (e.g.
a 6 or 8 MHz 68000 or 286) that would likely take a couple of seconds to
produce a single number...
>A better approach is to accept a range from 0 up to the largest
>multiple of limit that is smaller than RAND_MAX (this would look a lot clearer
>if limit were the number of values desired instead of the largest acceptable
>value. Most of those +1's would go away...):
> int max = ((RAND_MAX+1)/(limit+1))*(limit+1);
> int res = rand();
> while( res >= max )
> res = rand();
> return res % (limit+1);
Compared to a corrected version of the one I posted, this does have a
minor disadvantage if used with a mediocre generator. The upper bits of
a generator are generally more random than the lower bits, but this
returns lower bits, while the one above returns upper bits. As long as
the generator is written to produce significantly more bits than it
returns, and is already discarding lower bits, this is unlikely to be
significant, but with a generator that simply returns all the bits it
generates, the one above will likely end up slightly better.
Mr Philip Arthur Riebold
>In article <46pk9k$k...@senator-bedfellow.MIT.EDU>, sjau...@ATHENA.MIT.EDU (John Automo)says...
>>
>>Hello netters, I need some input regarding random numbers...
>>
>>I have 13 array locations. Let's call them: n[0], n[1], n[2],....,
>>n[12]. I want to RANDOMLY fill those locations with integers
>>from 0 to 12.
>>
>>i.e. n[0] = 2 n[4] = 1 n[8] = 10 n[12] = 9
>> n[1] = 6 n[5] = 0 n[9] = 12
>> n[2] = 7 n[6] = 3 n[10] = 5
>> n[3] = 11 n[7] = 4 n[11] = 8
>>
>>Notice that the number having been assigned to any previous array locations
>>can NOT BE REPEATED or reassigned to other locations.
>>
>>I used this approach to generate the random numbers:
>>
>> while (i<=12) {
>> n[i] = ((rand()/RAND_MAX)+0.05) * 12; /* This gives int from 0 to 12 */
><<< stuff deleted >>
>Think of it as a shuffling problem. I would use the following approach.
>int n[13];
>int i, j, nTemp;
>for (i = 0; i < 13; i++)
> n[i] = i;
>for (i = 0; i < 13; i++)
> {
> j = ((float)rand() / RAND_MAX) * 13;
> nTemp = n[j];
> n[j] = n[i];
> n[i] = nTemp;
> }
Using this method some arrangements will be more likely to be produced
than others.
The second for(;;) loop should be something like,
for(i = 12; i >= 1; i--) {
j = random_integer_from_range(0, i);
nTemp = n[j];
n[j] = n[i];
n[i] = nTemp;
}
This will produce each arrangement with equal probability
--
Philip Riebold,
Steve Summit
(Jerry Coffin) writes:
> pe...@borland.com (Pete Becker) wrote:
>>> This method of producing random numbers within a range produces some
>> Unfortunately, this doesn't eliminate the skew...
>> A better approach is to accept a range from 0 up to the largest
>
> Compared to a corrected version of the one I posted, this does have a
> minor disadvantage if used with a mediocre generator. The upper bits of
> a generator are generally more random than the lower bits, but this
Here's what the "even longer" (i.e. book-length) version of the
FAQ list has to say; I believe its code has none of the problems
which Jerry and Pete have been discussing. (Last I heard, the
book was supposed to ship from the printers today, so it should be
available RSN.)
13.16: How can I get random integers in a certain range?
A: The obvious way,
rand() % N /* POOR */
(which tries to return numbers from 0 to N-1) is poor, because
the low-order bits of many random number generators are
distressingly *non* random. (See question 13.18.) A better
method is something like
(int)((double)rand() / ((double)RAND_MAX + 1) * N)
If you're worried about using floating point, you could use
rand() / (RAND_MAX / N + 1)
Both methods obviously require knowing RAND_MAX (which ANSI
#defines in <stdlib.h>), and assume that N is much less than
RAND_MAX.
When N is close to RAND_MAX, and if the range of the random
number generator is not a multiple of N (i.e. if
(RAND_MAX+1) % N != 0), all of these methods break down: some
outputs occur more often than others. (Using floating point
does *not* help; the problem is that rand() returns RAND_MAX+1
distinct values, which cannot always be evenly divvied up into N
buckets.) If this is a problem, about the only thing you can do
is to call rand() multiple times, discarding certain values:
unsigned int x = (RAND_MAX + 1u) / N;
unsigned int y = x * N;
unsigned int r;
do {
r = rand();
} while(r >= y);
return r / x;
For any of these techniques, it's straightforward to shift the
range, if necessary; numbers in the range [M, N] could be
generated with something like
M + rand() / (RAND_MAX / (N - M + 1) + 1)
(Note, by the way, that RAND_MAX is a *constant* telling you what
the fixed range of the C library rand() function is. You cannot
set RAND_MAX to some other value, and there is no way of
requesting that rand() return numbers in some other range.)
If you're starting with a random number generator which returns
floating-point values between 0 and 1 (such as the last version
of PMrand() alluded to in question 13.15, or drand48() in
question 13.21), all you have to do to get integers from 0 to N-
1 is multiply the output of that generator by N:
(int)(drand48() * N)
References: K&R2 Sec. 7.8.7 p. 168
PCS Sec. 11 p. 172