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]

qu******@yahoo. com writes:

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.
--
Ben Pfaff
email: bl*@cs.stanford .edu
web: http://benpfaff.org

[Skarmander]

qu******@yahoo. com 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...)

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.programmin g
and sci.crypt.rando m-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]

Skarmander wrote:

qu******@yahoo. com 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...)

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.j...t/MT/emt.html),
which comes with C source.

S.

[Walter Roberson]

In article <11************ **********@g47g 2000cwa.googleg roups.com>,
<qu******@yahoo .com> 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...)

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().
--
Chocolate is "more than a food but less than a drug" -- RJ Huxtable

[osmium]

<qu******@yahoo .com> 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...)

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]

qu******@yahoo. com 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.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
Raining down sulphur is like an endurance trial, man. Genocide is the
most exhausting activity one can engage in. Next to soccer.

[Skarmander]

osmium wrote:

<qu******@yahoo .com> 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...)

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[i] = rand(); /* Some rand()-based expression */
for (j = 0; j != i && numbers[j] != numbers[i]; ++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[i] = rand();
for (int j = 0; j != i; ++j) {
if (numbers[j] == numbers[i]) 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[i] = rand(); /* Some rand()-based expression */
for (j = 0; j != i && numbers[j] != numbers[i]; ++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[i] = rand();
for (int j = 0; j != i; ++j) {
if (numbers[j] == numbers[i]) goto restart;
}
}

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

--
http://members.dodo.com.au/~netocrat

[websnarf]

quick...@yahoo. com 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...)

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[i] = 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.

--
Paul Hsieh
http://www.pobox.com/~qed/random.html
http://bstring.sf.net/