[erlang-questions] [ANN] Erlang UUID

[Michael Truog]

On 02/29/2012 01:09 PM, Per Andersson wrote:
>
>> Please also remember that the function to retrieve the MAC address from within Erlang is undocumented,
> The function to retrieve MAC address from Erlang is not
> undocumented anymore.
>
>     [0] http://www.erlang.org/doc/man/inet.html#getifaddrs-0
>

Thanks for mentioning that.

>> and "okeuday/uuid" v1 does not depend on an interface being available (i.e., for the MAC address) while
>> "avtobiff/erlang-uuid" v1 will attempt to use random:uniform/1 to create more than 44bits of randomness if no interface is available.
>>
>> 2) There is an important problem within "avtobiff/erlang-uuid" for v4, since random:uniform/1 only provides 44 bits of randomness, if you are lucky (that is probably pushing it, since the algorithm may have been meant to only provide 32 bits), however, the v4 function is attempting to use random:uniform/1 to provide 48 bits and 62 bits, where the rest should become 0 because of the algorithm used by random:uniform/1.  The other problem with v4 is that it reseeds random:uniform/1 each time the function is called with erlang:now(), which creates additional latency and possibly makes the v4 uuid less-random (depending on how it is called, e.g., on a timer).  To see a better implementation for v4, using random:uniform/1, there is get_v4_urandom_bigint/0 and get_v4_urandom_native/0 in "okeuday/uuid", however, both solutions become slower in testing when compared with get_v4/0 which uses crypto:rand_bytes/1 instead of multiple calls to random:uniform/1.
> Thanks for the comments on this. Erlang UUID no longer uses
> random:uniform/1 to create anymore than 32 bits of random
> data.
>
> However, how do you deduce that random:uniform/1 only provides
> 44 bits of random data? Since a float is returned from random:random/0
> which is used by random:uniform/1, isn't the total random bits 16 or 24
> (4 and 3 words on 32-bit and 64-bit architectures respectively)?
>
>     [1] http://www.erlang.org/doc/efficiency_guide/advanced.html#id68291
>
I have not tried to track down the paper connected with the algorithm implemented within the random module (B.A. Wichmann and I.D.Hill, in 'An efficient and portable pseudo-random number generator', Journal of Applied Statistics. AS183. 1982, or Byte March 1987), so I am not sure if they were limited to 32 bit integers, but I assume they were.  When I looked at this awhile ago, I forgot to add 1 to the result, so it is actually 45 bits, not 44 bits.  Before looking at the algorithm, I knew empirically that the random module had some limitation that causes a lack of variation in the output I saw, and the way I consider it to be 45 bits is through looking at the input to the floating point number that is used (part of the random:uniform/0 code):
    B1 = (A1*171) rem 30269,
    B2 = (A2*172) rem 30307,
    B3 = (A3*170) rem 30323,
    put(random_seed, {B1,B2,B3}),
    R = A1/30269 + A2/30307 + A3/30323,
    R - trunc(R).
So, {B1, B2, B3} becomes the next seed value {A1, A2, A3}.  Simplifying this, gives:
    R = (918999161 * A1 + 917846887 * A2 + 917362583 * A3) / 27817185604309
Whatever the values for A1, A2, and A3, (918999161 * A1 + 917846887 * A2 + 917362583 * A3) can not exceed 27817185604309 (30269 * 30307 * 30323) because of the previous modulus.  So, that means the algorithm breaks down, being unable to uniformly sample numbers beyond an N of 27817185604309, when considering the N provided to random:uniform/1.  When determining how many bits it takes to represent 27817185604309, you get:
1> (math:log(27817185604309) / math:log(2)) + 1.
45.6610416965467

If you are concerned about the floating point part:
2> 1 / 27817185604309.
3.59489998098548e-14

As shown here http://en.wikipedia.org/wiki/Double-precision_floating-point_format , 15.955 decimal digits can be represented within a double precision floating point number.  This is enough to contain the fraction, since Erlang is using double precision for the calculation, so it should not reduce the maximum number of bits that can be provided for uniformly random numbers.

>> 3) The other important difference is the license.  "avtobiff/erlang-uuid" is under a GPLv3 license, while "okeuday/uuid" is under a BSD license.  So, there is nothing blocking the commercial use of "okeuday/uuid" (please remember I am not a lawyer, nor am I giving legal advice).
> It is of course entirely possible to develop commercial applications with
> GPL'd software. What you can't do is to transform free software into
> proprietary software.
>
This is a little misleading.  You can never sell anything that contains GPL software, so many people consider GPL software to poison a code-base, since it can limit a full stack from becoming a product (this is the reason why some BSD distributions want a compiler that is not gcc, etc.).  So, the most you can do with GPL software is sell the service that is written with it, assuming you always submit your proprietary code changes to the developer of the GPL project (disclaimer: please remember I am not a lawyer, nor am I giving legal advice).

-- Michael