Copyright © 2004 Gene Michael Stover. All rights reserved. Permission to copy, store, & view this document unmodified & in its entirety is granted.
I fixed some link problems. I think the unit tests may be broken, but I probably won't have time to check & fix that until this weekend.
The Mersenne Twister is a pseudorandom number generation algorithm created by by Makoto Matsumoto. There is a Mersenne Twister home page, & the Mersenne Twister entry on Wikipedia provides a concise description & other links.
This article documents jmt.lisp, an implementation of the Mersenne Twister for Common Lisp. jmt.lisp was written by Jason H. Stover in 2002, then updated & documented by Gene Michael Stover in 2004.
I think the semantics of the state argument are slightly different from those of the corresponding argument of the Common Lisp RANDOM function. I should fix that. (G.M.S., 7 Feb 2004)
The source code in jmt.lisp, ref-c.c, ref-lisp.sh, ref.sh, test.lisp, testseed-c.c, testseed-lisp.sh, testseed.sh, & any other related files whose rights are held by Jason H. Stover or Gene Michael Stover is released in accordance with the GNU Lesser General Public License. There is also a copy at http://lisp-p.org/jmt/lgpl.txt.
This article is not covered by the Gnu Lesser General Public License. It is covered by its own copyright notice which is at the beginning of the article.
The source code files are all at http://lisp-p.org/jmt/. They are:
The only file you actually need is jmt.lisp. It contains the entire source code for an implementation of the Mersenne Twister. The other files are just for testing.
This section is a brief tutorial. The full reference manual is in Section 7.
The first step to using this Mersenne Twister is to load it. You could load it into Lisp with a literal pathname, like this:
> (load "jmt.lisp") ; load from a literal pathname
or you could load from a logical pathname, like this:
;; Assuming cl-library already has some translations
;; defined for it.
> (push '("stover;jason;jmt.lisp" "jmt.lisp")
(logical-pathname-translations "cl-library"))
> (load (translate-logical-pathname
"CL-LIBRARY:STOVER;JASON;JMT.LISP"))
T
The basic function for obtaining pseudoranom numbers from this Mersenne Twister is the MT-RANDOM function. It works like Common Lisp's RANDOM function.
With an integral argument 
, MT-RANDOM
returns an
pseudorandom integral number
such that
, like this:
> (loop for i from 1 to 5
collect (mt-random 6))
(0 4 0 5 1)
What computer programmer hasn't played a roll-playing game?1 Let's generate the six basic attributes for a character from an old edition of Dungeons & Dragons:
> (defun d6 () (1+ (mt-random 6)))
D6
> (defun roll-attr ()
(+ (d6) (d6) (d6)))
ROLL-ATTR
> (loop for i from 1 to 6 collect (roll-attr))
(4 14 14 11 13 10)
With a floating point argument , MT-RANDOM
returns a
floating point pseudorandom number
. Again, this is like the Common Lisp
RANDOM
function. Here is an
example:
> (loop for i from 1 to 10
collect (mt-random 1.0))
(0.03372876 0.2431892 0.99524146 0.0033221766
0.6445225 0.6361625 0.89716256 0.35805753
0.6595478 0.07814171)
Like the RANDOM function, MT-RANDOM allows an optional second argument. That second argument must be NIL or an instance of MT-RANDOM-STATE . If it is an MT-RANDOM-STATE , a copy of that state will be saved & used for future calls of MT-RANDOM unless you again use a state argument.
You can make a new MT-RANDOM-STATE with the MAKE-MT-RANDOM-STATE function. Let's make a pseudorandom random state now:
;; Use a PROGN so the random state isn't printed. ;; It's long & not pretty, I don't want to see it. > (progn (setq rs (make-mt-random-state t)) nil) NIL
Save a copy of the new random state so we can compare to it later:
> (progn (setq cs (make-mt-random-state rs)) nil) NIL
Generate a few numbers with the new random state, RS:
> (mt-random 10 rs) 5 > (loop for i from 1 to 3 collect (mt-random 10)) (0 4 8)
By specifying RS again, we can repeat that same sequence of numbers & demonstrate that the MT-RANDOM-STATE found to RS was copied & not altered by MT-RANDOM :
> (mt-random 10 rs) 5 > (loop for i from 1 to 3 collect (mt-random 10)) (0 4 8)
This Mersenne Twister stores its random state in the global variable *MT-RANDOM-STATE* much as the Common Lisp library stores its random state in *RANDOM-STATE* .
When you specify a non-NIL value as the second argument to MT-RANDOM-STATE , that value is bound to *MT-RANDOM-STATE* & used as the random state until you specify another value for it.
You may also use SETQ to bind an instance of MT-RANDOM-STATE to *MT-RANDOM-STATE* .
The *MT-RANDOM-STATE* global variable is specifically initiallized to a pseudorandom value when the library is loaded. Unless you need to recapture a sequence of random numbers or to continue a sequence from another process, it should not be necessary to initialize it specifically. I think this departs from Common Lisp's *RANDOM-STATE* global object, which is initialized to a constant value in many Lisp implementations.
A program might want to repeat a sequence of random numbers to repeat an output, possibly for legal reasons.
If many processes effectively share a random number generator, one process might want to load the generator's seed, use it for a while, & save it to a file before the process exited. That might be necessary for a web site implemented with CGI programs that needed to generate GUIDs.
For a given numeric seed value, the Lisp implementation should generate the same random state that the reference C version does. I wrote a short program to test it. You can see it run at http://CyberTiggyr.COM/gene/jmt/testseed.cgi. The source code for it is testseed.sh. The source code for the Lisp program it runs it testseed-lisp.sh. The source code for the C version is testseed-c.c; it is modified from mt19937int.c.
I modified the reference implementation in C, mt19937int.c to print its output with one random number on each line & with numbered lines. The new program is ref-c.c. Then I wrote a simple Lisp program, ref-lisp.sh, which produces output with the same format. If the Lisp implementation is correct, its output file will be identical to that of ref-c.c. A short script called ref.sh runs the two programs & compares their output with diff. You can run ref.sh & see its output at http://CyberTiggyr.COM/gene/jmt/ref.cgi.
There are also unit test programs in test.lisp.
make-mt-random-state &optional state 
new-state
Returns a new instance of MT-RANDOM-STATE .
If state is NIL (the default), new-state will be a copy of the MT-RANDOM-STATE that is bound to the *MT-RANDOM-STATE* global variable.
If state is T, new-state will be generated in a mostly pseudorandom way. For most programs, this will adequately approximate a randomly generated random state.
If state is an instance of MT-RANDOM-STATE , you'll get a copy of state.
If state is a non-negative integer, that integer will be expanded as controlled crap to make a new random state. The same integer used on different occasions in the same or in different processes, will create distinct but equivalent random states. In other words, if you use some integer N on one occasion & it gives you some sequence S of pseudorandom numbers, then if you use the same number N on some other occasion, you'll again get the sequence S.
If state is a sequence of non-negative integers, it must contain exactly 624 integers. Those integers will be converted directly into an MT-RANDOM-STATE object. This provides more precise control over the new MT-RANDOM-STATE object than when using a single integer for state.
The MAKE-MT-RANDOM-STATE function is analogous to the Common Lisp function MAKE-RANDOM-STATE , though it allows more types for its state argument than does the MAKE-RANDOM-STATE function. The MAKE-RANDOM-STATE allows NIL, T, or a RANDOM-STATE value, but the MAKE-MT-RANDOM-STATE function also allows a single integer argument or a sequence of 624 integers.
mt-random limit &optional state random-number
Returns a pseudo-random number. Uses the Mersenne Twister algorithm for generating the numbers.
Examples are in Section 5.
Modifies the random state that is bound to *MT-RANDOM-STATE* .
I think the semantics of the state argument are slightly different from those of the corresponding argument of the Common Lisp RANDOM function. I should fix that. (G.M.S., 7 Feb 2004)
MT-RANDOM-STATE, T
The state used by function MT-RANDOM to generate pseudorandom numbers.
MAKE-MT-RANDOM-STATE , MT-RANDOM , *MT-RANDOM-STATE*
a pseudorandom value derived from the universal time
The global *MT-RANDOM-STATE* variable is the default random state that is used by the MT-RANDOM-STATE function when it computes the next pseudorandom number.
*MT-RANDOM-STATE* is automatically initialized to a value which is hopefully unique, so many programs will not need to initialize it explicitly. The automatically initialized value is not guarranteed to be unique, & it's not deterministic, so programs that must guarrantee unique initial values or that must know the initial values should use their own systems for generating the initial random state; then those programs should use SETQ or SETF to bind that value to *MT-RANDOM-STATE*.
See Section 5.
MAKE-MT-RANDOM-STATE , MT-RANDOM , MT-RANDOM-STATE
This document is available in multi-file HTML format at http://lisp-p.org/jmt/.
This document is available in DVI format at http://lisp-p.org/jmt/jmt.dvi.
This document is available in PostScript format at http://lisp-p.org/jmt/jmt.ps.