## Monday, December 11, 2006

### Random Number Generation

The Scheme Cookbook has a few recipes on random number generation. Why not turn them into a library?

Once upon a time I got bitten by the random number generation bug and did just that. I wrote large parts of the random.plt library available through PLaneT.

"Huh - where exactly?", I hear you say. Well, the library were submitted when PLaneT were in its infancy, so it appears under the 2xx-page. After two major updates since the 200-series no one checks the old libraries (not even the PLT Source Browser), so not surprisingly the random number library is forgotten.

After "porting" (well, I *did* change a single line) it is now available again.

The documentation contains the gory details, so I'll just give a few examples:
`> (require (planet "random.ss" ("schematics" "random.plt" 1 0))); Good old Gaussian distribution> (random-gaussian)0.7386912134436788; A "stochastic variable"> (define X (random-source-make-gaussians default-random-source))> (X)0.5826066449247809> (X)0.7865269446783535; Other stuff> (random-gamma 1)0.013863292728449427> (random-permutation 5)#5(3 1 2 4 0)> (random-chi-square 1)1.1334523156657883`

The source contains an implementation by Sebastian Egner of a very interesting algorithm. It is the generation of random number following a discrete distribution, which surprisingly can be implemented efficiently.

(random-source-make-discretes s w)
given a source s of random bits in the sense of SRFI-27
and a vector w of n >= 1 non-negative real numbers,
this procedure constructs and returns a procedure rand
such that (rand) returns the next integer x in {0..n-1}
from a pseudo random sequence with

Pr{x = k} = w[k] / Sum(w[i] : i)

for all k in {0..n-1}.

Think about it - how would you implement it?