[erlang-questions] [ANN] Erlang UUID

Richard O'Keefe ok@REDACTED
Fri Mar 2 03:59:58 CET 2012

>>> I have not tried to track down the paper connected with the algorithm implemented within the random module (B.A. Wichmann and I.D.Hill, in 'An efficient and portable pseudo-random number generator', Journal of Applied Statistics. AS183. 1982, or Byte March 1987), so I am not sure if they were limited to 32 bit integers, but I assume they were.

In fact they were very explicitly concerned with generating good quality random numbers
on machines with 16-bit integers but able to do
	16 * 16 -> 32
	32 mod 16 -> 16
using register pairs (as you could on a PDP-11, for example).  AS183 basically uses three
independent linear congruential generators with 15 bits of state each, giving the equivalent
of one 45-bit linear congruential generator.  At the time, people normally expected to work
mostly with single-precision floats and this was ample to give you a 32-bit float result.

This was really exciting to me in DEC-10 Prolog, where integers were held to just eighteen
bits, although we did have the intermediate 36-bit results we needed to make AS183 work,
and which didn't actually have floating point anyway.  Here was something I could use on a
PDP-11, a VAX, or a DEC-10, and get the same answers on each.

As has been explained before in this mailing list, and also in a couple of Prolog mailing
lists, is that AS183 was a fine algorithm in its day, but that day has long passed.

Wichmann & Hill have since published a four-generator algorithm, see
    Wichmann and Hill have a new generator with a longer period.
    [2] B. A. Wichmann, I. D. Hill,
    Generating good pseudo-random numbers,
    Computational Statistics & Data Analysis, 51, 1614-1622 (2006).

In fact generating full-precision random doubles is something RNG writers often neglect.
As for generating random integers in the range [0,N) where N is a bignum, I would love
to be pointed to a paper on the subject.

More information about the erlang-questions mailing list