[erlang-questions] [ANN] Erlang UUID

[Michael Truog]

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>