multiply random number

Discussion in 'C++' 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. mlimber 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...)
    >
    > Thanks,
    >
    > qq


    If you're not talking about the standard function std::rand(), then
    your post is off topic here since it is not concerned with the C++
    language or libraries. See the FAQ for what is on-topic:
    http://www.parashift.com/c -faq-lite/how-to-post.html#faq-5.9. You
    probably want a newsgroup dealing with algorithms in general (e.g.,
    comp.programming) or one dealing with random number generation.

    Cheers! --M
    mlimber, Nov 11, 2005
    #2
    1. Advertising

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


    Is there a C++ language question somewhere hiding in all this? For
    general programming questions consider 'comp.programming'.

    If you're talking about the Standard function 'rand', then it (a) doesn't
    generate 0 to 100 numbers, its limits are 0 and RAND_MAX, and (b) is in
    fact quite inexpensive.

    V
    Victor Bazarov, Nov 11, 2005
    #3
  4. 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...)
    >
    > Thanks,
    >
    > qq
    >


    I don't think it is possible to solve that problem and guarantee to only
    call rand() 10 times. I could be wrong.

    john
    John Harrison, Nov 11, 2005
    #4
  5. John Harrison 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...)


    > I don't think it is possible to solve that problem and guarantee to only
    > call rand() 10 times. I could be wrong.


    You can, for example, create a list with the numbers from 0 to 100, call
    rand, pick the number obtained and remove it from the list, call rand and
    pick the number obtained modulus the remaining elements in the list, remove
    it from the list, and repeat the times desired.

    --
    Salu2
    =?ISO-8859-15?Q?Juli=E1n?= Albo, Nov 11, 2005
    #5
  6. John Harrison 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...)
    >>
    >> Thanks,
    >>
    >> qq
    >>

    >
    > I don't think it is possible to solve that problem and guarantee to only
    > call rand() 10 times. I could be wrong.


    I am thinking something in the direction of: make a vector of 100 values,
    ten loops, each containing: a calls to 'rand()' to get an index, extract
    the value from the vector, amend the value indexed to the value below or
    above it, unless it's been already extracted, then keep going in that
    direction until reaching the value that hasn't been extracted yet. The
    proof of the randomness of the values extracted that way lies on the OP.

    V
    Victor Bazarov, Nov 11, 2005
    #6
  7. Julián Albo wrote:
    > John Harrison 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...)

    >
    >
    >>I don't think it is possible to solve that problem and guarantee to only
    >>call rand() 10 times. I could be wrong.

    >
    >
    > You can, for example, create a list with the numbers from 0 to 100, call
    > rand, pick the number obtained and remove it from the list, call rand and
    > pick the number obtained modulus the remaining elements in the list, remove
    > it from the list, and repeat the times desired.
    >


    But after you remove an item for the list you need a random number from
    0 to 99, and you haven't got that. By using a modulus you are biasing
    the pick, so unless you list is random in the first place (which it
    isn't) you are going to get biased results.

    john
    John Harrison, Nov 11, 2005
    #7
  8. Mark P Guest

    Julián Albo wrote:
    > John Harrison 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...)

    >
    >
    >>I don't think it is possible to solve that problem and guarantee to only
    >>call rand() 10 times. I could be wrong.

    >
    >
    > You can, for example, create a list with the numbers from 0 to 100, call
    > rand, pick the number obtained and remove it from the list, call rand and
    > pick the number obtained modulus the remaining elements in the list, remove
    > it from the list, and repeat the times desired.
    >


    The OP didn't specify but if the desired distribution is uniformly
    random then this will not work (i.e., not all outcomes are equally likely).
    Mark P, Nov 11, 2005
    #8
  9. Victor Bazarov wrote:
    > John Harrison 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...)
    >>>
    >>> Thanks,
    >>>
    >>> qq
    >>>

    >>
    >> I don't think it is possible to solve that problem and guarantee to
    >> only call rand() 10 times. I could be wrong.

    >
    >
    > I am thinking something in the direction of: make a vector of 100 values,
    > ten loops, each containing: a calls to 'rand()' to get an index, extract
    > the value from the vector, amend the value indexed to the value below or
    > above it, unless it's been already extracted, then keep going in that
    > direction until reaching the value that hasn't been extracted yet. The
    > proof of the randomness of the values extracted that way lies on the OP.
    >
    > V


    It's clever, but it doesn't sound random to me.

    Suppose your initial list is 0 to 100 and the first random number picks
    5. So 5 is one of your random numbers, but in the list 5 gets replaced
    with the next higher number, i.e. 6. So now you have two sixes in the
    list. And if either of those sixes gets hit you'll have three sevens, etc.

    I think you'll will get more bunching than you would with a
    straightforward random pick.

    john
    John Harrison, Nov 11, 2005
    #9
  10. John Harrison wrote:

    >> You can, for example, create a list with the numbers from 0 to 100, call
    >> rand, pick the number obtained and remove it from the list, call rand and
    >> pick the number obtained modulus the remaining elements in the list,
    >> remove it from the list, and repeat the times desired.

    >
    > But after you remove an item for the list you need a random number from
    > 0 to 99, and you haven't got that. By using a modulus you are biasing
    > the pick, so unless you list is random in the first place (which it
    > isn't) you are going to get biased results.


    Is a random result. Certainly is not equally distributed as the original
    rand function, but the distribution properties of the result were not in
    the OP conditions, it just asked for speed and for call rand 10 times.

    --
    Salu2
    =?ISO-8859-15?Q?Juli=E1n?= Albo, Nov 11, 2005
    #10
  11. Mark P 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...)
    >
    > Thanks,
    >
    > qq
    >


    This is an instance of a general problem of converting random values
    from one set into random values from another set. In your case there
    are (100 C 10) possible outcomes and you have random values from a set
    of size 100. Since (100 C 10) is not divisible by 100, there is no way
    to guarantee the number of required operations.

    You can do well on expectation though and a short illustration should
    give you the idea. Suppose you want to pick a number between 1 and 5
    and you only have a coin. Flip it three times to get a number between 1
    and 8. If the number is less than or equal to 5, you're done.
    Otherwise you have one of three numbers. Flip once more get another bit
    which, combined with the leftover choice among three, gives you one
    among 6 values. If the value is 1-5 your done, otherwise repeat the
    process.

    I'm not sure this is optimal but as you can see, unless rand() truly is
    expensive, it's probably not worth the effort.

    Mark
    Mark P, Nov 11, 2005
    #11
  12. Neil Cerutti Guest

    On 2005-11-11, John Harrison <> wrote:
    > Victor Bazarov wrote:
    >> John Harrison 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...)

    >> I am thinking something in the direction of: make a vector of
    >> 100 values, ten loops, each containing: a calls to 'rand()' to
    >> get an index, extract the value from the vector, amend the
    >> value indexed to the value below or above it, unless it's been
    >> already extracted, then keep going in that direction until
    >> reaching the value that hasn't been extracted yet. The proof
    >> of the randomness of the values extracted that way lies on the
    >> OP.
    >>
    >> V

    >
    > It's clever, but it doesn't sound random to me.
    >
    > Suppose your initial list is 0 to 100 and the first random
    > number picks 5. So 5 is one of your random numbers, but in the
    > list 5 gets replaced with the next higher number, i.e. 6. So
    > now you have two sixes in the list. And if either of those
    > sixes gets hit you'll have three sevens, etc.
    >
    > I think you'll will get more bunching than you would with a
    > straightforward random pick.


    If the OP really gave a crap about randomness he wouldn't be
    worried about getting duplicates. ;-)

    Anyhow, I took a stab at it, using a rotating translation table.

    And, err, rand_expensive needs to be *really* expensive before
    adopting this solution.

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    #include <cstdlib>
    #include <ctime>

    using namespace std;

    int rand_expensive()
    {
    /* Spend millions of resources somehow doing the following: */
    return rand()%101;
    }

    struct counter
    {
    int c_;
    counter(int c): c_(c) { }
    int operator()()
    {
    return c_++;
    }
    };

    int main()
    {
    srand(time(0));
    vector<int> nums;
    vector<int> range(101);
    generate_n(range.begin(), 101, counter(0));
    for (int i = 0; i < 10; ++i) {
    int r = rand_expensive();
    while (find(nums.begin(), nums.end(), range[r]) != nums.end())
    {
    rotate(range.begin(), range.begin()+1, range.end());
    }
    nums.push_back(range[r]);
    }
    copy(nums.begin(), nums.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
    }

    --
    Neil Cerutti
    Neil Cerutti, Nov 11, 2005
    #12
    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. Replies:
    8
    Views:
    431
    osmium
    Oct 14, 2006
  2. Replies:
    20
    Views:
    1,198
  3. globalrev
    Replies:
    4
    Views:
    733
    Gabriel Genellina
    Apr 20, 2008
  4. Tim Chase
    Replies:
    8
    Views:
    408
  5. VK
    Replies:
    15
    Views:
    1,090
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page