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?

0 Comments:

Post a Comment

Links to this post:

Create a Link

<< Home