[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