# Random Numbers in Common Lisp

31 Jul 2014(This article has a follow up.)

An overview of *random numbers* in Common Lisp. What functionality is available, what are the best libraries, and what’s missing?

# Random Numbers

I think there are 3 application domains of random numbers each with its specific requirements: science, cryptography, and day-to-day use. The latter is definitely the least requiring. You may need to generate random numbers to shuffle a playlist. As long as it looks random to the user, it’s OK.

Scientific applications are a bit more demanding. You may want to generate lots of random numbers fast and the stream of random numbers shouldn’t just look random, it should pass most statistical tests (like the Diehard tests and TestU01). The Mersenne Twister is such a random number generator. Most programming languages (also Common Lisp) allow you to generate random numbers from uniform distributions (where all numbers have equal probability) but you may want to generate random numbers from many other distributions (binomial, gaussian, beta, …) as well. Finally, you may need access to statistical functions of random distributions (mean, skewness, probability density function, cumulative density function, …).

Cryptographic applications (for example to create keys) demand the most of random number generators. The generators used for day-to-day use or scientific applications—usually called *pseudo*-random number generators—are not good enough for cryptographic means. What you need is a *cryptographically secure* pseudo-random number generator but you probably need no more than streams of uniformly random bits. (Correct me if I am wrong, I am not a cryptography expert.)

Given these use cases, let’s see what Common Lisp provides.

# What’s available

## Common Lisp spec.

Every Common Lisp implementation provides basic means to generate random numbers. `(random limit)`

returns a uniformly distributed random number between `0`

(incl.) and `limit`

(excl.) of the same type as `limit`

.

The state of the random number generator changes each time you call `random`

and is of type `random-state`

. You can optionally supply a `random-state`

when you call `random`

. By default, `random`

uses the global variable `*random-state*`

. You can clone a `random-state`

in case you want to regenerate a stream of random numbers: `(make-random-state state)`

and you can create a randomly seeded `random-state`

: `(make-random-state T)`

.

Obviously this is limited. For day-to-day use this is probably enough. Scientific applications requiring several random number distributions will rely on dedicated libraries as is the case in all general purpose programming languages. But there are two more problems:

- the choice of pseudo-random number generator is left to the implementation and
- there is no option to provide a seed.

The first is not a problem in itself, but obviously leads to questionable implementations. Luckily some implementations (SBCL, CMU CL, any others?) provide the Mersenne Twister which is excellent for scientific applications.

The second problem can be solved by writing `random-state`

s, then reuse them whenever you want to repeat a scientific experiment, recreate a random graph, … SBCL provides a better solution: `sb-ext:seed-random-state`

provides the missing function.

## Alexandria

For day-to-day use, Alexandria (named after the city with the first library) provides some useful functions: `(shuffle sequence)`

shuffles `sequence`

, `(random-elt sequence)`

returns a random element from `sequence`

, and `(gaussian-random)`

returns noise (a random number distributed according to the Gaussian distribution). Finally, it provides the macro `whichever`

which evaluates one of several possibilities chosen at random.

Unfortunately, none of these allow to supply a `random-state`

thereby breaking with the Common Lisp’s `random`

. Though this is only problematic if you want to regenerate the same stream of random numbers.

The following are Common Lisp libraries dedicated to random numbers. Each of them has its pros and cons.

## cl-random

Pro:

- Nice interface for random distributions. You can draw random numbers from a distribution with the function
`draw`

and there’s access to the following statistical functions:`cdf`

,`pdf`

,`quantile`

,`mean`

,`variance`

, and`stdev`

. - Many distributions: discrete, uniform, exponential, normal, truncated-normal, t, log-normal, gamma, inv-gamma, chi-square, inv-chi-square, and beta. There are some functions for drawing Bernoulli distributed random numbers but these are not yet integrated into the above interface.

Contra:

- Relies on the built-in random number generator.
- Depends on
`libRmath`

for some statistical functions. - Lacks some well-known discrete distributions: binomial, geometric, …

## cl-randist

Pro:

- Includes the Mersenne Twister generator. This is good for portability to other Common Lisp implementations.
- You can draw numbers from many distributions: normal, bivariate normal, gamma, dirichlet, beta, binomial, negative binomial, poisson, multinomial, and discrete.
- No dependencies.

Contra:

- Lacks statistical functions.
- Lacks many continuous distributions: exponential, beta, …

## cl-variates

Pro:

- Has an interface for random number generators and implements:
`ran1`

and`ranq1`

. - You can draw random numbers according to some distributions. Mostly the naming is more user-oriented than distribution-oriented. For example, you call
`random-boolean`

or`flip`

instead of`random-bernoulli`

when you want a Bernoulli distributed random number (or variable). - Has some higher-level functionality:
`shuffle-elements!`

,`sample-sequence`

, …

Contra:

- No longer maintained.
- Lacks many important distributions.
- Lacks statistical functions.

## GSLL, GNU Scientific Library for Lisp

Finally, there is one library that provides it all: `GSLL`

. But it’s very slow (at generating random numbers). It is a wrapper around the GNU Scientific Library (GSL), a very popular numerical library written in C.

Pro:

- Has all you need: lots of different generators, you can draw random numbers according to many distributions, and has many statistical functions.

Contra:

- Depends on
`GSL`

. - Generating a random number is slow. I tested this some time ago. Drawing a random number from the Common Lisp’s built-in generator is 5 times faster and conses only half as much than from
`GSLL`

. (I used the same SBCL on a Mac and chose the same generator for`GSLL`

as the one built into SBCL, the Mersenne Twister.)

# Conclusion

For day-to-day use, Common Lisp’s built-in generator and functionality combined with `Alexandria`

is probably sufficient.

For cryptographic applications, none of these libraries provide what you need. Though, there is `secure-random`

, a wrapper around OpenSSL’s cryptographically secure pseudo-random number generator.

For scientific simulations, `GSLL`

provides all you need except speed. So, you may want to choose a Common Lisp implementation that provides

- a strong generator such as the Mersenne Twister and
- a way to seed the generator.

SBCL fulfills these requirements. For additional functionality (draw random numbers from distributions different than uniform and statistical functions for these distributions), I think `cl-random`

is the best options.

As often with Common Lisp libraries, effort is scattered. In my opinion, the 3 libraries `cl-random`

, `cl-randist`

, and `cl-variates`

should be merged providing the best of each:

`cl-random`

’s interface for distributions,`cl-randist`

’s Mersenne Twister and the distributions`cl-random`

doesn’t provide, and`cl-variates`

’s interface for random generators.

I started by branching `cl-random`

. Let’s see what time permits.