Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   multiply random number (http://www.velocityreviews.com/forums/t449733-multiply-random-number.html)

 quickcur@yahoo.com 11-11-2005 06:02 PM

multiply random number

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

 mlimber 11-11-2005 06:08 PM

Re: multiply random number

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...)
>
> 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-lit...t.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

 Victor Bazarov 11-11-2005 06:14 PM

Re: multiply random number

quickcur@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...)

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

 John Harrison 11-11-2005 06:27 PM

Re: multiply random number

quickcur@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...)
>
> 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

 =?ISO-8859-15?Q?Juli=E1n?= Albo 11-11-2005 06:33 PM

Re: multiply random number

John Harrison wrote:

> quickcur@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...)

> 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

 Victor Bazarov 11-11-2005 06:40 PM

Re: multiply random number

John Harrison wrote:
> quickcur@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...)
>>
>> 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

 John Harrison 11-11-2005 06:53 PM

Re: multiply random number

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

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

 Mark P 11-11-2005 06:55 PM

Re: multiply random number

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

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

 John Harrison 11-11-2005 06:58 PM

Re: multiply random number

Victor Bazarov wrote:
> John Harrison wrote:
>
>> quickcur@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...)
>>>
>>> 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

 =?ISO-8859-15?Q?Juli=E1n?= Albo 11-11-2005 07:07 PM

Re: multiply random number

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

All times are GMT. The time now is 08:27 AM.