[erlang-questions] [ANN] Erlang UUID
Michael Truog
mjtruog@REDACTED
Sat Mar 3 06:48:34 CET 2012
On 03/02/2012 09:02 PM, Richard O'Keefe wrote:
> On 3/03/2012, at 1:32 PM, Michael Truog wrote:
>> If you use this implementation, then it would provide 408 bits of randomness, uniformly distributed.
> I don't see how it can. Just because all the numbers are in a given range does not mean that
> all the numbers in that range are possible. The Wichmann-Hill generator has a state with
> 4 31-bit numbers, meaning that you can't possibly get more than 124 bits out of it. If you
> really get more, you have a different algorithm.
>
> Using 64-bit integer arithmetic, the algorithm looks like
>
> a = (a * 11600LL) % 2147483579;
> b = (b * 47003LL) % 2147483543;
> c = (c * 23000LL) % 2147483423;
> d = (d * 33000LL) % 2147483123;
> w = a/2147483579.0 + b/2147483543.0
> + c/2147483423.0 + d/2147483123.0;
> if (w >= 2.0) w -= 2.0;
> if (w >= 1.0) w -= 1.0;
> return w;
I agree. I think the random_wh06 module had precision problems with the floating point values it was using for R. If I modify the module to fit the 64bit implementation, it does match the 124 bit maximum with the range [0...21267638781707063560975648195455661513) for the uniform distribution (coming from "w" in the 64bit version, without division, or "I" in the random_wh06 module), which is then input for the modulus N to have the algorithm use only a subset of the total range for a uniform distribution. The Erlang code equivalent is:
B1 = (11600 * A1) rem 2147483579,
B2 = (47003 * A2) rem 2147483543,
B3 = (23000 * A3) rem 2147483423,
B4 = (33000 * A4) rem 2147483123,
put(random_wh06_seed, {B1, B2, B3, B4}),
I = ((B1 * 9903516371291919229607132747) +
(B2 * 9903516537312557910938853791) +
(B3 * 9903517090714727049595319831) +
(B4 * 9903518474220420479167438931))
rem 21267638781707063560975648195455661513,
I updated the implementation with this, to correct the problem:
https://github.com/okeuday/erlbench/blob/master/src/random_wh06.erl
Thank you for finding the 64bit C implementation. Please tell me if you think my approach with the recent changes is erroneous.
Thanks,
Michael
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20120302/b45c2ed0/attachment.htm>
More information about the erlang-questions
mailing list