brde at optusnet.com.au
Tue Jul 2 16:33:38 UTC 2013
On Tue, 2 Jul 2013, Andrey Chernov wrote:
> On 02.07.2013 11:39, Bruce Evans wrote:
>> The bugs are a little different than I said above. There is no overflow
>> problem and no problem with invalid values being produces, since the
>> algorithm from ACM is careful to do everything with 32 bit signed
>> integers without causing overflow. The algorithm just doesn't produce
>> values mod 2**32 as expected by all the functions. It does what it
>> claims to do -- it produces values mod (2**32 - 1). The largest bug
>> is that RAND_MAX is off by 1. It is specified as the largest value
>> returned by rand(), but in FreeBSD rand() never returns it unless
>> USE_WEAK_SEEDING is confgured. The values should be unifornly
>> distributed on average beteen 0 and RAND_MAX,but that is impossible
>> if RADND_MAX is never returned. From libc/stdlib/srand.c:
> Don't ever consider USE_WEAK_SEEDING defined - result is distributet
> _very_ poorly and the code should be removed long time ago.
> BTW, I don't understand well fixes you suggest. Is it to define RAND_MAX
> as 0x7ffffffe ?
That would would be more correct. It might have compatibility problems.
I checked the values returned by rand(). The ACM part works as
intended, so it never returns RAND_MAX. It also never returns 0. So
the distribution of values in the documented range [0, RAND_MAX] is
very non-uniform. It is uniform in [1, RAND_MAX - 1]. To use this
algorithm for rand(), 1 should have been subtracted, giving a range
of [0, 0x7ffffffe].
In mathematical terms, the algorithm uses the (multiplicative) group
of units in the field Z/(0x7fffffff.Z), but for rand() we want the
values to be in the the additive group Z/(0x7ffffffe.Z). Subtracting
1 doesn't preserve the group operation but gives the right set of
values. 0x7ffffffff is used because it is prime. 0x800000001,
0xffffffff and 0x100000001 are not prime, so the algorithm can't easily
be modified to give the range [0, 0x7fffffff] or a 32-bit range. The
most interesting prime near 2**31 or 2*32 is 2**32 - 5.
More information about the svn-src-head