multiple random number

Discussion in 'C Programming' started by quickcur@yahoo.com, Nov 11, 2005.

  1. Guest

    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
    , Nov 11, 2005
    #1
    1. Advertising

  2. Ben Pfaff Guest

    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:
    web: http://benpfaff.org
    Ben Pfaff, Nov 11, 2005
    #2
    1. Advertising

  3. Skarmander Guest

    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, Nov 11, 2005
    #3
  4. Skarmander Guest

    Skarmander wrote:
    > 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.jp/~m-mat/MT/emt.html),
    which comes with C source.

    S.
    Skarmander, Nov 11, 2005
    #4
  5. In article <>,
    <> 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
    Walter Roberson, Nov 11, 2005
    #5
  6. osmium Guest

    <> 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.
    osmium, Nov 11, 2005
    #6
  7. SM Ryan Guest

    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.
    SM Ryan, Nov 11, 2005
    #7
  8. Skarmander Guest

    osmium wrote:
    > <> 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 = 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.
    Skarmander, Nov 12, 2005
    #8
  9. Netocrat Guest

    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.

    --
    http://members.dodo.com.au/~netocrat
    Netocrat, Nov 12, 2005
    #9
  10. Guest

    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 = 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/
    , Nov 12, 2005
    #10
  11. Thad Smith Guest

    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
    Thad Smith, Nov 13, 2005
    #11
  12. Richard Bos Guest

    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
    Richard Bos, Nov 14, 2005
    #12
  13. Tim Rentsch Guest

    OT - Re: multiple random number

    Thad Smith <> writes:

    > 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.
    Tim Rentsch, Nov 16, 2005
    #13
  14. Tim Rentsch Guest

    OT - Re: multiple random number

    (Richard Bos) writes:

    > 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, 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.
    Tim Rentsch, Nov 16, 2005
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. xeys_00
    Replies:
    12
    Views:
    852
    Jonathan Arnold
    Apr 11, 2005
  2. globalrev
    Replies:
    4
    Views:
    756
    Gabriel Genellina
    Apr 20, 2008
  3. Frantisek Fuka

    Multiple random number generators

    Frantisek Fuka, Apr 29, 2006, in forum: Ruby
    Replies:
    2
    Views:
    125
    Robert Klemme
    Apr 30, 2006
  4. Alex Untitled
    Replies:
    11
    Views:
    658
    Giampiero Zanchi
    Nov 16, 2009
  5. VK
    Replies:
    15
    Views:
    1,161
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page