Quote:

>Hello. I'm doing a Smalltalk program and I need to know how can I obtain a

>random number. Is there any reserved word? Other method?

>I'm programming in Smalltalk Express 2.0

(I hope this doesn't show up twice -- something seems to have eaten the

first one.)

The following is a standard answer I post to this question now and then...

--------------------------------------------------------------------------

"To the non-specialist, the construction of a random number generator

may appear to be the kind of thing that any good programmer can do

easily. Over the years many programmers have unwittingly demonstrated

that it is all to easy to 'hack' a procedure that will produce a strange

looking, apparently unpredictable sequence of numbers. It is

fundamentally more difficult, however, to write quality software which

produces what is really desired -- a virtually infinite sequence of

statistically independent random numbers, uniformly distributed between 0

and 1. This is a key point: strange and unpredictable is not necessarily

random."

-- Park & Miller

Notes on Random Number Generators

---------------------------------

Notes and commentary (c) Copyright 1995/6 by David N. Smith, All Rights

Reserved.

(The code itself is in the public domain.)

There are three critical things to understand about pseudo-random number

generators:

1) Virtually ALL pseudo-random number generators are terrible.

2) Pseudo-random number generators do not really produce random numbers,

but produce sequences of very NON-random, repeatable, deterministic

values. The 'good ones' let their users PRETEND that, for certain

applications, the deterministic sequences are random.

3) Thus, it is of critical importance to know what you want to do WITH

the pseudo-random numbers.

None of you would (I hope!) recommend a computer language to a stranger

without asking what they intended to DO with that language, or recommend

a vehicle without asking about how someone intends to use it. (Gee,

whatdya mean officer, my new John Deere tractor can't be driven down

Interstate 684? I asked this guy on the net what I should get and he said

John Deere made the best!) :-)

The same holds with random number generators. One might use a simple,

quick, and dirty generator to introduce some 'unpredictability' in an

action game where performance is critical. But that same generator would

be worse than useless with a card game where the user could readily see

patterns in the deal after playing a number of games.

A pseudo-random number generator that works well for card games may not

work well with a monte-carlo analysis of a large business, and a

generator that works for such analysis probably would be horrible for

cryptographic use.

-----

Most random number generators are mainly broken.

There is a paper that gives a minimal standard random generator. It is

'Random Number Generators: Good Ones Are Hard to Find', by Stephen K.

Park and Keith W. Miller (Communications of the ACM, 31(10):1192--1201,

1988).

P-M don't claim that theirs is good, but that any generator that is worse

should never be used. The meaning of 'good' depends too much on what the

generator is to be used for. Generators for Crypto use are orders of

magnitude more complex and 'many times' slower. Generators for modelling

have different needs than crypto.

-----

One can give no opinions without testing. The testing of random number

generators is described in Knuth Vol 2. (Knuth devotes a whole chapter,

ie, half of a book, to random number generators and their testing. If

Knuth spends 1/2 a book of his (projected) 7 volume set of The Art of

Computer Programming on the topic of random numbers, might one at least

suspect that the topic is of some importance??)

While there is much more recent literature than Knuth on RNGs, Knuth is

the fundamental place to start and the place that all others reference.

His contribution is huge and lasting. (And an update is due in the spring

of 1997!!)

Park&Miller defined a MINIMAL STANDARD RNG, not the greatest one. They

claim that one should never use one WORSE than theirs. The Park&Miller

RNG is quite suitable for everyday use; it has quite good statistical

qualities and no other should be used without knowing a LOT about it.

How does one know if one RNG is better than another? Knuth tells how, in

{*filter*}detail. His 'chapter' is highly recommended for anyone seriously

looking at RNGs, or trying to pick one.

The Park&Miller paper is:

Random Number Generators: Good Ones are Hard to Find

Stephen K. Park and Keith W. Miller

Communications of the ACM, October 1988, V31 N10, pp 1192-1201.

Knuth is:

Chapter 3: Random Numbers

which is the first chapter in:

The ART of Computer Programming, Volume II, 2nd Edition

Seminumerical Algorithms

Addison-Wesley. ISBN 0-201-03822-6

Pages 1-177.

-----

The code below is extracted from my random number generator test-bed,

part of an effort to explore random number generators which I started

some time ago and not yet quite finished. It implements the Park-Miller

generator.

The ParkMillerRNG is used like this:

| randy |

randy := ParkMillerRNG new.

10 timesRepeat: [

Transcript cr; show: randy next printString ].

Summary of methods ---

Creation:

randy := ParkMillerRNG new

Generation:

randy next -- Floating point value: [0.0,1.0)

randy nextInteger -- Integer value: [0,maxInt]

randy peek -- Peek at next float value

randy peekInteger -- Peek at next integer value

In the test bed, and in the code that I'll release (someplace, someday)

when it is done, there is a lot of support structure. This code is the

bare bones. It's unusual structure (having peek methods to answer the

next random number) is on purpose and makes more sense in 'the big

picture'.

I also have code to do shuffling -- a technique which seems to improve

all RNGs -- but it is harder to extract into standalone methods. If you

have a serious need for it, I'll do the extraction and share the whole

thing.

Please not that I do NOT recommend this generator for ANY particular

purpose. See the Park-Miller paper for their opinion on its usability.

But if you are going to just pick up some generator from some guy on the

net...

-----

Here are real versions for VisualWorks 2.5 and IBM Smalltalk 3.0. They

are virtually identical and should port to other systems easily. There is

a somewhat faster version of this code in Squeak Smalltalk, but as I am

not the sole author of it I don't distribute it directly. Most of the

bulk consists of two class testing methods.

After installation, be sure to execute:

ParkMillerRNG theItsCompletelyBrokenTest

See the comments in the code. It is also worthwhile running:

ParkMillerRNG bucketTest

Again, see the comments in the code

------------------------------ VW 2.5 ------------------------------

'From VisualWorks(R), Release 2.5 of September 26, 1995

on November 2, 1996 at 10:43:55 am'!

Object subclass: #ParkMillerRNG

instanceVariableNames: 'seed a m q r mu1 '

classVariableNames: ''

poolDictionaries: ''

category: 'Collections-Streams'!

!ParkMillerRNG methodsFor: 'all'!

initialize

" Set a reasonable Park-Miller starting seed "

seed := 2345678901.

a := 16r000041A7. " magic constant = 16807 "

m := 16r7FFFFFFF. " magic constant = 2147483647 "

q := 16r0001F31D. " quotient (m quo: a) It's 44488 in decimal "

r := 16r00000B14. " remainder (m \\ a). It's 2836 in decimal "

mu1 := 0.46566128752457969d-9. " Reciprocal of m (ie, mu1 == 'm under

1') "!

next

" This method generates random instances of Float in the interval 0 to

1. "

seed := self peekInteger.

^ seed * mu1!

nextInteger

" This method generates random instances of Integer

in the interval 0 to 16r7FFFFFFF. "

seed := self peekInteger.

^ seed!

peek

" This method answers the next random number that will be generated as

a Float in the range [0..1). It answers the same value for all successive

message sends. "

^ self peekInteger * mu1!

peekInteger

" This method generates random instances of Integer

in the interval 0 to 16r7FFFFFFF.

This method does NOT update the seed; repeated sends answer the same

value.

The algorithm is described in detail in 'Random Number Generators:

Good Ones Are Hard to Find' by Stephen K. Park and Keith W. Miller

(Comm. Asso. Comp. Mach., 31(10):1192--1201, 1988). "

| lo hi aLoRHi answer |

hi := seed quo: q.

lo := seed rem: q.

aLoRHi := (a * lo) - (r * hi).

answer := (aLoRHi > 0)

ifTrue: [ aLoRHi ]

ifFalse: [ aLoRHi + m ].

^ answer!

seed: anInteger

seed := anInteger! !

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!

ParkMillerRNG class

instanceVariableNames: ''!

!ParkMillerRNG class methodsFor: 'testing'!