Date: Fri, 24 Dec 2004 00:28:26 +1100 (EST) From: Bruce Evans <bde@zeta.org.au> To: Peter Wemm <peter@wemm.org> Cc: freebsd-amd64@FreeBSD.org Subject: Re: /usr/games/random bug? Message-ID: <20041223230006.P73466@delplex.bde.org> In-Reply-To: <200412222325.34375.peter@wemm.org> References: <41C778CD.1080602@jrv.org> <200412222325.34375.peter@wemm.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Wed, 22 Dec 2004, Peter Wemm wrote: > On Monday 20 December 2004 05:13 pm, James R. Van Artsalen wrote: > > 5-stable "/usr/games/random -e 99" seems to always return 0, which > > makes it very predictable. > > > > 5.2.1 does this too. But i386 4.x seems to work as expected (an exit > > value between 0 and 98 inclusive). > > > > The source code line in question is > > > > return (int)((denom * random()) / LONG_MAX); > > > > the assembler code is > > [floating point stuff] > The problem is a code design error and/or invalid assumptions about the > range of values that random() returns.. > > random() returns a long. > However, random()'s range is limited to 31 bits. > > "DESCRIPTION > The random() function uses a non-linear additive feedback random number > generator employing a default table of size 31 long integers to return > successive pseudo-random numbers in the range from 0 to (2**31)-1. The > period of this random number generator is very large, approximately > 16*((2**31)-1)." > > Now, We're taking a 2^31 bit number, and multiplying it by some integer > value, eg: 99. Erm, we're multiplying it by some double value, e.g., 99, to extend random()'s 31-bit range. > Then dividing the result by LONG_MAX, which is 2^62. Actually ((long)(2^63 - 1)). > > Now, the result of (large but not so large number) divided by (much > larger number (a billion times larger!)) is always = 0. The result of the division is double, so it is usually nonzero, but is always >= 0 and much less than 1.0, so rounding it always gives 0 (denom is limited to 255 (should be 127) so denom * random() can't exceed 2^39 which is much less than LONG_MAX on 64-bit machines). > Try changing the LONG_MAX in that division to INT_MAX and it will behave > the same as on i386. > > Then we have (n * (0 .. 2^31)) / (2 ^ 31) which makes much more sense. > And it even works on both 32 and 64 bit systems. INT_MAX would only work accidentally. The divisor (if this simple scaling algorithm is kept) should be (RANDOM_MAX + 1), except RANDOM_MAX doesn't exist. random() unimproves on rand() in not having a macro that gives its limits. This bug has a long history in jot/jot.c: 1.1: *y = (double) random() / INT_MAX; 1.3: *y = (double) random() / LONG_MAX; 1.9: *y = (double) arc4random() / ULONG_MAX; 1.16: *y = arc4random() / ULONG_MAX; 1.17: *y = arc4random() / (double)ULONG_MAX; 1.18: *y = arc4random() / (double)UINT_MAX; 1.19: *y = arc4random() / (double)UINT32_MAX; 1.25 and current: *y = arc4random() / ((double)UINT32_MAX + 1); I.e: - 1.1 assumes 32-bit ints, which was and remains a fairly safe but bad assumption. - 1.3 assumes 32-bit longs, which is an unsafe assumption. - 1.9 moved the problem and changed the limit. arc4random() unimporoves on even random() by not documenting its maximum value, but since arc4random() returns uint32_t and indirectly claims to represent all values up to RAND_MAX, it must have a maximum value between RAND_MAX and 2^32-1. It assumes that RAND_MAX <= 2^32-1. (The spec for RAND_MAX requires that it be between 32767 and INT_MAX, so it might exceed 2^32-1 on machines with >= 33-bit ints.) Rev.1.8 assumes that uint32_t == u_long. - 1.16 completely broke the range adjustment to "fix" a warning. - 1.17 essentially backed out 1.16. - 1.18 "fixed" the scaling on 64-bit machines by essentially backing out 1.1 It assumes that uint32_t == u_int instead of that uint32_t == u_long. - 1.19 removed the assumptions in 1.18. - 1.25 fixed an unrelated bug in the scaling. random(6) has the same bug that was fixed in jot.c 1.25 -- random -e 99 can exit with a status of 99 despite it being documented to exit with a status between 0 98. It seems to be missing the scaling/uniformity bug mentioned in the log message for jot.c 1.25 -- "jot -r -w %d 1 1 4" can never give 4; its range is from 1 to 3 despite its specified range being from 1 to 4. Bruce
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20041223230006.P73466>