Thanks for the explanation Don! It looks like I need better math-foo to
completely understand your explanation...
On Tuesday, February 11, 2014 10:07:05 AM UTC-8, Don wrote:
>
>
> It can be shown mathematically that if you use a multiplier A such that
> A*2^15-1 and A*2^16-1 are both prime, you get a sequence with period
> A*2^15. With A=63663 you get a sequence of nearly two billion. If A was
> larger than 2^16, the multiplication would result in overflow in some
> cases, so the value I used was near the limit. The generator uses only the
> low 16 bits as output. The high 16 bits, however, are kept as state,
> meaning that you can't tell from the current output what the next output
> will be. The full cycle contains each possible output value an equal number
> of times, so over a large sample, the outputs are all equally likely.
>
> Using mod 1000 is not a perfect way to get a uniform value in the range
> 0-1000. Because the outputs are in the range 0..65536, there are 65 ways to
> generate numbers <= 536 and 66 ways to generate numbers > 536. A better way
> to generate a number in the range 0..n-1 is to divide the output by
> 65535/n. Then check the result and if it is >= n, repeat the process until
> you get a valid result.
>
> Don
>
> On Tuesday, February 11, 2014 1:18:26 AM UTC-5, SVIX wrote:
>>
>> :) true... that was silly of me.. I was too quick to post... anyway, the
>> point I was trying to understand was why this specific combination of
>> operations would produce good randomness... Running the original solution
>> you posted a million times (with the max limit set to 1000), below is the
>> frequency of the numbers generated (in the format <number> X <frequency> )
>>
>>
>> On Friday, February 7, 2014 11:42:03 AM UTC-8, Don wrote:
>>>
>>> Because if you put that in a loop you will get a series like:
>>>
>>> 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5...
>>>
>>> On Thursday, February 6, 2014 8:27:27 PM UTC-5, SVIX wrote:
>>>>
>>>> Just curious... Why is this more random than
>>>> (getSystemTimeInMilliseconds() % 10)
>>>>
>>>> On Thursday, February 6, 2014 1:47:15 PM UTC-8, Don wrote:
>>>>>
>>>>> Just noticed that you asked for 1-10, and my code will clearly
>>>>> generate 0-9. Add one for the desired range.
>>>>> Don
>>>>>
>>>>> On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote:
>>>>>>
>>>>>> // Using George Marsaglia's Multiply With Carry generator
>>>>>> int rnd10()
>>>>>> {
>>>>>> static unsigned int x = time(0);
>>>>>> x = 63663 * (x&65535) + (x>>16);
>>>>>> return (x & 65535) % 10;
>>>>>> }
>>>>>>
>>>>>> On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote:
>>>>>>>
>>>>>>> Generate random number form 1 - 10 with probability of 1/10.You are
>>>>>>> not allowed to used rand() function.
>>>>>>>
>>>>>>> any simple way of achieving above with using any complex
>>>>>>> implementation of random number generators algorithm .
>>>>>>>
>>>>>>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
