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 algogeeks+unsubscr...@googlegroups.com.
