Velocity Reviews > multiple random number

# multiple random number

Guest
Posts: n/a

 11-13-2005
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

> Suppose I have a function rand() that can generate one integer random
> number between 0 and 100. Suppose also rand() is very expensive. What
> is the fastest way to generate 10 different random number between 0 and
> 100? (call rand() only 10 times...)

When you say a number between 0 and 100, do you mean the 99 values
1..99, or the 101 values from 0 through 100? In either case, you are
asking for a random set of 10 such values. There are C(101,10) such
combinations. This would take about 6.6 random values of 0..100 to
represent. The problem is the .6. You could generate 7 random values
and convert it a single number 0 to 101^7-1. If the resulting value is
less than C(101,10), you have identified a unique combination.

The problem comes if the value is larger. What do you do then? The
simplest thing is to start over with 7 more random values. Again, you
may get a value outside the desired range. A more complicated scheme
would use the initial combined random value with future rand() calls to
get an unbiased result faster. Regardless of the method used, there is
(I think) no limit to the number of rand() calls that need to be made to
ensure an unbiased result. For practical implementations you could
truncate the series at some point and generate a biased result with low
probability.

-

Richard Bos
Guest
Posts: n/a

 11-14-2005
(E-Mail Removed) wrote:

> Suppose I have a function rand() that can generate one integer random
> number between 0 and 100. Suppose also rand() is very expensive. What
> is the fastest way to generate 10 different random number between 0 and
> 100? (call rand() only 10 times...)

Homework? Sounds like it. In any case, it's an algorithm problem, not a
C problem per se. However...

Creating 100 different numbers between 0 and 100 (assuming inclusive
bottom/exclusive top; the alternatives are no harder but the numbers
will be slightly different) is simple and fast, but they won't be in
random order.
Shuffling this set of 100 different numbers is also not hard (and
snippets for doing so are readily available); the first N numbers will
then all be different, and will lie within the desired range. You will
have done 100 calls to rand(), though.
However, what happens with the most popular shuffle algorithm when you
stop after 10 calls to rand()?

Richard

Tim Rentsch
Guest
Posts: n/a

 11-16-2005

> (E-Mail Removed) wrote:
>
> > Suppose I have a function rand() that can generate one integer random
> > number between 0 and 100. Suppose also rand() is very expensive. What
> > is the fastest way to generate 10 different random number between 0 and
> > 100? (call rand() only 10 times...)

>
> When you say a number between 0 and 100, do you mean the 99 values
> 1..99, or the 101 values from 0 through 100? In either case, you are
> asking for a random set of 10 such values. There are C(101,10) such
> combinations. This would take about 6.6 random values of 0..100 to
> represent. The problem is the .6. You could generate 7 random values
> and convert it a single number 0 to 101^7-1. If the resulting value is
> less than C(101,10), you have identified a unique combination.

I expect you can get close to 6.6 calls to rand() on the average if
some state is saved across calls (to the function that yields the 10
distinct numbers). If no state is saved across calls (ie, other than
the state that rand() uses for its own purposes), it looks like just
over 7.1 calls to rand() are needed on the average.

> The problem comes if the value is larger. What do you do then? The
> simplest thing is to start over with 7 more random values. Again, you
> may get a value outside the desired range. A more complicated scheme
> would use the initial combined random value with future rand() calls to
> get an unbiased result faster.

Yes, that's not too hard to do; that makes a nice exercise if someone
is interested.

> Regardless of the method used, there is
> (I think) no limit to the number of rand() calls that need to be made to
> ensure an unbiased result. For practical implementations you could
> truncate the series at some point and generate a biased result with low
> probability.

There's no upper bound to the number of rand() calls that might be
needed, but the probability of needing large numbers of calls goes to
zero extremely quickly. There doesn't seem to be much point in
truncating prematurely; by the time 50 or 100 calls to rand() are
needed, the "infinite loop" will have found its answer with
probability greater than the probability of the sun rising tomorrow.
So betting the loop will terminate quickly is a very safe bet.

Tim Rentsch
Guest
Posts: n/a

 11-16-2005
(E-Mail Removed) (Richard Bos) writes:

> (E-Mail Removed) wrote:
>
> > Suppose I have a function rand() that can generate one integer random
> > number between 0 and 100. Suppose also rand() is very expensive. What
> > is the fastest way to generate 10 different random number between 0 and
> > 100? (call rand() only 10 times...)

>
> Homework? Sounds like it. In any case, it's an algorithm problem, not a
> C problem per se. However...
>
> Creating 100 different numbers between 0 and 100 (assuming inclusive
> bottom/exclusive top; the alternatives are no harder but the numbers
> will be slightly different) is simple and fast, but they won't be in
> random order.
> Shuffling this set of 100 different numbers is also not hard (and
> snippets for doing so are readily available); the first N numbers will
> then all be different, and will lie within the desired range. You will
> have done 100 calls to rand(), though.
> However, what happens with the most popular shuffle algorithm when you
> stop after 10 calls to rand()?

Nothing bad, if the random numbers needed can be generated without
bias and with only a single call to rand() each. That's the problem
however. If you meant this algorithm:

for( i = 0; i < 10; i++ ){
n = random_number_less_than( 101 );
EXCHANGE( a[i], a[n] );
}

then the resulting shuffle distribution is biased. If you meant this
algorithm:

for( i = 0; i < 10; i++ ){
n = random_number_less_than( 101 - i );
EXCHANGE( a[i], a[i+n] );
}

then generating the random numbers takes more than one call to rand()
(that generates numbers between 0 and 100, inclusive), if the numbers
that come out of 'random_number_less_than( unsigned k )' are uniformly
distributed.