Velocity Reviews > C++ > multiply random number

multiply random number

Mark P
Guest
Posts: n/a

 11-11-2005
http://www.velocityreviews.com/forums/(E-Mail 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...)
>
> 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

Neil Cerutti
Guest
Posts: n/a

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

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

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

And, err, rand_expensive needs to be *really* expensive before

#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