Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > multiple random number

Reply
Thread Tools

multiple random number

 
 
Thad Smith
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.

-
Thad

 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
Tim Rentsch
Guest
Posts: n/a
 
      11-16-2005
Thad Smith <(E-Mail Removed)> 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...)

>
> 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.
 
Reply With Quote
 
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Math.random() and Math.round(Math.random()) and Math.floor(Math.random()*2) VK Javascript 15 05-02-2010 03:43 PM
How do I get a random number between two random numbers? Alex Untitled Ruby 11 11-16-2009 09:45 AM
random.random(), random not defined!? globalrev Python 4 04-20-2008 08:12 AM
Multiple random number generators Frantisek Fuka Ruby 2 04-30-2006 11:13 AM
My random number is only random for the first run??? xeys_00 C++ 12 04-11-2005 03:58 PM



Advertisments