dcatteeu     About     Tags  

Backup of my ideas, thoughts, how-tos, open source software, reviews, ...

Random Numbers in Common Lisp

(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 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-states, 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

web

Pro:

Contra:

cl-randist

web

Pro:

Contra:

cl-variates

web

Pro:

Contra:

GSLL, GNU Scientific Library for Lisp

web

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:

Contra:

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

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:

I started by branching cl-random. Let’s see what time permits.