http://www.velocityreviews.com/forums/(EMail 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^71. 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.

Thad