Smalltalk › Squeak › Squeak - Dev

[squeak-dev] The Squeak Random Number Generator

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

5 messages Options

Jim Rosenberg

[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 ...)

johnmci

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
=
=
=
========================================================================

Nicolas Cellier-3

[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

Frank Caggiano

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

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:

Andres Valloud-3

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

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
> ===========================================================================
>
>
>
>
>