# [squeak-dev] The Squeak Random Number Generator

5 messages
Open this post in threaded view
|

## [squeak-dev] The Squeak Random Number Generator

 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 ...)
Open this post in threaded view
|

## Re: [squeak-dev] The Squeak Random Number Generator

 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= = = ========================================================================
Open this post in threaded view
|

## [squeak-dev] Re: The Squeak Random Number Generator

 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