Date: Wed, 22 Dec 2004 23:25:34 -0800 From: Peter Wemm <peter@wemm.org> To: freebsd-amd64@freebsd.org Cc: "James R. Van Artsalen" <james@jrv.org> Subject: Re: /usr/games/random bug? Message-ID: <200412222325.34375.peter@wemm.org> In-Reply-To: <41C778CD.1080602@jrv.org> References: <41C778CD.1080602@jrv.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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 > > .p2align 3 > .LC17: > .long 0 > .long 1006632960 > > call random > cvtsi2sdq %rax, %xmm0 > mulsd 24(%rsp), %xmm0 > mulsd .LC17(%rip), %xmm0 > cvttsd2si %xmm0, %eax > jmp .L1 > > I'm not familiar enough with IEEE fp rules or amd64 fp coding to say > why this doesn't work, nor if this source code is even reasonable. 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. Then dividing the result by LONG_MAX, which is 2^62. Now, the result of (large but not so large number) divided by (much larger number (a billion times larger!)) is always = 0. 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. -- Peter Wemm - peter@wemm.org; peter@FreeBSD.org; peter@yahoo-inc.com "All of this is for nothing if we don't go to the stars" - JMS/B5
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200412222325.34375.peter>