I'm getting very queasy feelings about Random.
My understanding of the linear congruence random number generator algorithm is that it depends (crucially) on doing exact integer arithmetic with enough precision to hold all the digits in the multiplication at its heart. Using floating point arithmetic for a linear congruence algorithm is one of the classic ways of implementing a random number generator that is badly flawed. In my version of Squeak (3.8) the class Random seems to be using floats. Uh oh. Can somebody comment? Has the Squeak random number generator ever been tested? (Knuth gives a whole raft of tests ...) |
At the time when David N Smith provided it, it replaced a very flawed
implementation. From the comments you can see it's a: "This Random Number Generator graciously contributed by David N. Smith. It is an adaptation of the Park-Miller RNG which uses Floats to avoid the need for LargeInteger arithmetic.: Normally it would return integers, but as you see it returns floats, to avoid the creation and time needed to deal with large integer objects. The theItsCompletelyBrokenTest method returns values that don't match for some of the entries due to rounding. Someone with a powerpc machine would need to cross check using an older VM. We altered the current VMs a few years back to align floating point rounding rules when it was discovered they gave different results on the platforms for Croquet. On Sep 7, 2008, at 4:45 AM, Jim Rosenberg wrote: > I'm getting very queasy feelings about Random. > > My understanding of the linear congruence random number generator > algorithm is that it depends (crucially) on doing exact integer > arithmetic with enough precision to hold all the digits in the > multiplication at its heart. Using floating point arithmetic for a > linear congruence algorithm is one of the classic ways of > implementing a random number generator that is badly flawed. > > In my version of Squeak (3.8) the class Random seems to be using > floats. Uh oh. > > Can somebody comment? Has the Squeak random number generator ever > been tested? (Knuth gives a whole raft of tests ...) > -- = = = ======================================================================== John M. McIntosh <[hidden email]> Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com = = = ======================================================================== |
John M McIntosh a écrit :
> At the time when David N Smith provided it, it replaced a very flawed > implementation. > > From the comments you can see it's a: > "This Random Number Generator graciously contributed by David N. Smith. > It is an adaptation of the Park-Miller RNG which uses Floats to avoid > the need for LargeInteger arithmetic.: > > Normally it would return integers, but as you see it returns floats, to > avoid the creation and time needed to deal with large integer objects. > > The theItsCompletelyBrokenTest method returns values that don't match > for some of the entries due to rounding. Someone with a powerpc machine > would need > to cross check using an older VM. We altered the current VMs a few years > back to align floating point rounding rules when it was discovered they > gave different results on the > platforms for Croquet. > > > On Sep 7, 2008, at 4:45 AM, Jim Rosenberg wrote: > >> I'm getting very queasy feelings about Random. >> >> My understanding of the linear congruence random number generator >> algorithm is that it depends (crucially) on doing exact integer >> arithmetic with enough precision to hold all the digits in the >> multiplication at its heart. Using floating point arithmetic for a >> linear congruence algorithm is one of the classic ways of implementing >> a random number generator that is badly flawed. >> >> In my version of Squeak (3.8) the class Random seems to be using >> floats. Uh oh. >> >> Can somebody comment? Has the Squeak random number generator ever been >> tested? (Knuth gives a whole raft of tests ...) >> > > -- > =========================================================================== > John M. McIntosh <[hidden email]> > Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com > =========================================================================== > > If underlying floating point arithmetic unit is compliant with IEEE 754, then the algorithm implemented in Random should return same values as the Integer form. Float (that is double precision) are able of performing exact arithmetic up to 53 bits. Operations performed in Random>>initialize and Random>>#nextValue are crafted to involve no more than 31 bit arithmetic on Integer values. I mean intermediate results will never axceed 31 bits. And all these Integer values can be represented exactly in Float. Here are the highest bits involved: a highBit -> 15 m highBit -> 31 q highBit -> 17 r highBit -> 12 This will result in highest possible bits: hi highBit -> 14 lo highbit -> 17 aLoRHi highBit -> 31 Rewriting #theItsCompletelyBrokenTest more explicitely: | seed a m rng c1 c2 | seed := 2345678901. a := 16r000041A7. m := 16r7FFFFFFF. rng := Random new. rng seed: seed. c1 := (1 to: 100) collect: [:i | rng next hex]. c2 := (1 to: 100) inject: seed into: [:prevSeed :i | prevSeed * a \\ m]. c2 := c2 collect: [:nextSeed | (nextSeed/m) asFloat hex]. ^c1 = c2 I get no problem on my PC. Of course, if you subclassed Random with less care, that could be a problem. Nicolas |
In reply to this post by Jim Rosenberg
This one seems to work well::
http://xkcd.com/221/ On Saturday Sep 6, 2008 AD, at 22:45, Jim Rosenberg wrote: > I'm getting very queasy feelings about Random. > > My understanding of the linear congruence random number generator > algorithm is that it depends (crucially) on doing exact integer > arithmetic with enough precision to hold all the digits in the > multiplication at its heart. Using floating point arithmetic for a > linear congruence algorithm is one of the classic ways of > implementing a random number generator that is badly flawed. > > In my version of Squeak (3.8) the class Random seems to be using > floats. Uh oh. > > Can somebody comment? Has the Squeak random number generator ever > been tested? (Knuth gives a whole raft of tests ...) > |
In reply to this post by johnmci
Without looking at the implementation in Squeak, the Park Miller
generator in VisualWorks looks exactly the same and it may not be a good idea to return a double from it. This is because Park Miller produces (IIRC) 31 random bits, and the double mantissas have 53 bits (including the implicit bit), so the behavior of up to 22 bits is undefined. In the case of VisualWorks, bit #32 was always 1 due to the arithmetic operations used. Note this is not an issue with Park Miller, but rather with attempting to answer results more precise than possible. Other bits had questionable behavior too. Lagged fibonacci generators are both better and faster. Andres. John M McIntosh wrote: > At the time when David N Smith provided it, it replaced a very flawed > implementation. > > From the comments you can see it's a: > "This Random Number Generator graciously contributed by David N. > Smith. It is an adaptation of the Park-Miller RNG which uses Floats > to avoid the need for LargeInteger arithmetic.: > > Normally it would return integers, but as you see it returns floats, > to avoid the creation and time needed to deal with large integer objects. > > The theItsCompletelyBrokenTest method returns values that don't match > for some of the entries due to rounding. Someone with a powerpc > machine would need > to cross check using an older VM. We altered the current VMs a few > years back to align floating point rounding rules when it was > discovered they gave different results on the > platforms for Croquet. > > > On Sep 7, 2008, at 4:45 AM, Jim Rosenberg wrote: > >> I'm getting very queasy feelings about Random. >> >> My understanding of the linear congruence random number generator >> algorithm is that it depends (crucially) on doing exact integer >> arithmetic with enough precision to hold all the digits in the >> multiplication at its heart. Using floating point arithmetic for a >> linear congruence algorithm is one of the classic ways of >> implementing a random number generator that is badly flawed. >> >> In my version of Squeak (3.8) the class Random seems to be using >> floats. Uh oh. >> >> Can somebody comment? Has the Squeak random number generator ever >> been tested? (Knuth gives a whole raft of tests ...) >> > > -- > =========================================================================== > > John M. McIntosh <[hidden email]> > Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com > =========================================================================== > > > > > |
Free forum by Nabble | Edit this page |