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 13 4202 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 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.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 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.
In article <11**********************@g47g2000cwa.googlegroups .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
<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. 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.
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.
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
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/ 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...)
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 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...)
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
Thad Smith <Th*******@acm.org> writes: 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...) 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. rl*@hoekstra-uitgeverij.nl (Richard Bos) writes: 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...)
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. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Virus |
last post by:
Ok well what I am trying to do is have
1.) the background color to change randomly with 5 different colors.(change
on page load)
2,) 10 different quotes randomly fadeing in and out in random...
|
by: Peteroid |
last post by:
I know how to use rand() to generate random POSITIVE-INTEGER numbers.
But, I'd like to generate a random DOUBLE number in the range of 0.0 to 1.0
with resolution of a double (i.e., every possible...
|
by: santosh |
last post by:
Hi all,
In the following program I allocate a block of pointers to type char,
initialised to zero. I then point each of those pointers to a block of
allocated memory of fixed size (33 bytes). A...
|
by: toton |
last post by:
Hi,
I am looking for a circular buffer solution ( a fixed buffer) , where
the elements can be pushed back & removed front. It looks stl deque
can be a solution. my question is,
1) circular...
|
by: HumanJHawkins |
last post by:
I wrote this question a little differently in the MFC group since it is
a bit of a different environment than pure C++, but I hope you will
forgive the similarities if anyone is reading both...
|
by: fatimahtaher |
last post by:
Hi,
I am supposed to create a program that generates a random number and then asks the user to guess the number (1-100). The program tells the user if he guessed too high or too low. If he...
|
by: Peter Oliphant |
last post by:
I would like to be able to create a random number generator that produces
evenly distributed random numbers up to given number.
For example, I would like to pick a random number less than 100000,...
|
by: Frankie |
last post by:
It appears that System.Random would provide an acceptable means through
which to generate a unique value used to identify multiple/concurrent
asynchronous tasks.
The usage of the value under...
|
by: wozza |
last post by:
hi
I'm a Dreamweaver user who's created a few simple data entry/
registrations forms in my time, but I'm not really a coder (though I
can follow instructions and am not afraid to dabble...) - I...
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
| |