multiple random number

[quickcur]

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...)

Thanks,

qq

 

[Ben Pfaff]

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...)

The fastest way would probably be to use a function other than
rand() to do the generation. Other than that, I don't even see
what question you're asking. There are only a few reasonable
ways to write a 10-iteration loop, given no more information.

 

[Skarmander]

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...)

Use a different rand() that is not expensive, possibly taking into
account a loss of randomness.

A random number generator based on linear congruence is fast and, if
written well, "random enough" for most purposes. You could seed it with
one number from rand(), if this is a superior source of random numbers.

See question 13.15 of the FAQ of this ng. You may also get better
replies in a newsgroup that's not specific to C, like comp.programming
and sci.crypt.random-numbers (but read their FAQs first, when
appropriate, I have not).

(Pseudo)-random number generation is its own field of study in computer
programming.

S.

 

[Skarmander]

Use a different rand() that is not expensive, possibly taking into
account a loss of randomness.

A random number generator based on linear congruence is fast and, if
written well, "random enough" for most purposes. You could seed it with
one number from rand(), if this is a superior source of random numbers.

Update to my own reply: a popular fast RNG that is rumored to outpace
even LC while having much better statistical properties is the Mersenne
Twister (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html),
which comes with C source.

S.

 

[Walter Roberson]

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...)

That's an algorithm question, not a C question.

[OT]
If rand() really does return a *random* number, then you cannot
do what you want with just 10 calls to rand(). If rand() is truly
producing a random number, then it could *by chance* return 0
four hundred and twenty-two times in a row -- and then turn
around and return 100 for the next 3 million calls. This circumstance
is merely -unlikely-, not impossible.

If you try to overcome this by using some kind of algorithm to
choose a different number (e.g., md5 hash of (rand() + the current index)
then anyone who knew your algorithm and knew the previous numbers
in the series would be able to predict the next number in the series
with probability greater than that inherent in the random
distribution function.

So really you cannot do much except to keep calling rand() until you
have 10 different results. If, as you say, rand() is expensive,
then nearly any reasonable kind of housekeeping to check for duplicates
would be less expensive than a single call to rand().

 

[osmium]

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...)

A series of random numbers may include repeated numbers. So you are asking
for a random number that *isn't* a random number.

What is that thing in parenthesis at the end? Is that a tentative solution?
Why is it in parenthesis? Clearly it is *not* a usable solution to the
question you ask.

I haven't read and understood all the messages in this thread so this may be
a repeat. I would draw ten random numbers, put them in an array, copy the
array, sort the duplicate array, and look for duplicate entries. Replacing
and retesting if needed. To use the numbers, just draw them in order, 0, 1,
2 .... in the originally drawn array. After all they are already random,
there is no reason to redo something.

 

[SM Ryan]

(e-mail address 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...)

If you want a random draw, you can check Knuth's Art of Programming.

 

[Skarmander]

A series of random numbers may include repeated numbers. So you are asking
for a random number that *isn't* a random number.

What is that thing in parenthesis at the end? Is that a tentative solution?
Why is it in parenthesis? Clearly it is *not* a usable solution to the
question you ask.

I haven't read and understood all the messages in this thread so this may be
a repeat. I would draw ten random numbers, put them in an array, copy the
array, sort the duplicate array, and look for duplicate entries. Replacing
and retesting if needed.

Actually, for generating just 10 numbers, doing it the "stupid" way is
probably faster than going through all that.

int numbers[count];
int i;
do {
for (i = 0; i != count; ++i) {
int j;
numbers = rand(); /* Some rand()-based expression */
for (j = 0; j != i && numbers[j] != numbers; ++j);
if (j != i) break;
}
} while (i != count);

That is, just do a linear search for duplicates when you generate a new
value. This doesn't scale, but is efficient for small values of count.

Here's the version for the goto appreciation society, with C99 style
declarations:

int numbers[count];
restart:
for (int i = 0; i != count; ++i) {
numbers = rand();
for (int j = 0; j != i; ++j) {
if (numbers[j] == numbers) goto restart;
}
}

S.

 

[Netocrat]

On Sat, 12 Nov 2005 02:15:32 +0100, Skarmander wrote:
[generating 10 unique random numbers]

Actually, for generating just 10 numbers, doing it the "stupid" way is
probably faster than going through all that.

int numbers[count];
int i;
do {
for (i = 0; i != count; ++i) {
int j;
numbers = rand(); /* Some rand()-based expression */
for (j = 0; j != i && numbers[j] != numbers; ++j);
if (j != i) break;
}
} while (i != count);

That is, just do a linear search for duplicates when you generate a new
value. This doesn't scale, but is efficient for small values of count.

More so if you reverse the outermost and middle loops (modifying
conditionals).

Here's the version for the goto appreciation society, with C99 style
declarations:

int numbers[count];
restart:
for (int i = 0; i != count; ++i) {
numbers = rand();
for (int j = 0; j != i; ++j) {
if (numbers[j] == numbers) goto restart;
}
}

This one's easier - just bring restart down a line.

 

[websnarf]

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...)

rand() is a standard C function call. Its range is between 0 and
RAND_MAX inclusive, and RAND_MAX must be >= 32767, but is defined by
your compiler. Anyhow, so suppose that instead we have rand10() which
behaves as the rand() function you described.

Ok, you don't specify any qualifications to the kind of "random" that
you want, so if you produce 10 random numbers between 0 and 10, then
they will also be between 0 and 100, so you're done. If you are
expecting more, like that there is a chance that any number between 0
and 100 is chosen, then you can do the obvious:

a[0] = rand10();
for(i=1; i < 10; i++) a = a[i-1] + rand10();

The numbers won't be random with respect to each other, but taken as a
whole, you could sort of say these number are "random" and covers your
range. Now you have to understand that unlike 10 choices from U[0,100]
(meaning uniformly distributed from 0 to 100 inclusive, and in this
case, just picking integers) there are many anomolies with such a
method of choice -- no gap of more than 10 is possible, the [0,10] gap
is not possible, and the expected average is far far less than 50 (I
think its 27.5, but don't quote me). Also taken as a sequence, the
numbers are also always non-decreasing (but this may not matter to
you.)

If you want to actually generate 10 random numbers from the U[0,100]
distribution, well, it seems you simply don't have enough entropy from
just ten choices from U[0,10]. In general entropy cannot be increased
without additional sources of entropy.

 

[Thad Smith]

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

 

[Richard Bos]

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]

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]

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, 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, 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.