[erlang-questions] New random module?
Thu Nov 25 00:14:21 CET 2010
> * Current random module (Wichmann-Hill 1982, state: 6 bytes: period: ~ 10^13)
I should provide a bit of background here.
More years ago than I care to remember, I needed a random number
generator for Prolog. I wanted something tolerably portable.
This meant that
- the stored integers had to fit into 18 bits (DEC-10 Prolog)
- the intermediate integers had to fit into 28 bits
- it had to be possible to generate random integers, random
lists, and so on without floating point.
At the time I was aware of fancier RNGS, like the lagged Fibonacci
ones discussed in Knuth vol. 2. But they didn't meet these criteria.
Algorithm AS183 was *new* and fitted these criteria perfectly.
When at Quintus I revised library(random) to use C code for the
actual numeric calculations. This got the speed up to a blazing
1ms per random number on a Sun-3/50. (The figure is written in
the source code!) At that speed, a period of 10^13 takes 10^10
seconds to exhaust, or about 317 years, so the period looked pretty
Erlang probably got it from Prolog.
Now, the SC-40 ran at 12 MIPS and was 8 times as fast as a KL10,
so that's 1.5 MIPS for a KL-10, which we thought was fast back
in the days of DEC-10 Prolog. The Sun-3/50, pretty much the latest
and greatest in the early days of Quintus, was also 1.5MIPs (and
the best keyboard I've ever used). The 3/50 didn't have floating
On a 500 MHz UltraSPARC II, market value today probably 0, the
same AS183 code takes 0.3 usec. That's 333 times faster. The
period would be exhausted in a year. An Intel Core 2 Duo running
at 2.66 GHz does it another 10 times faster still, which would
exhaust the period in a little over 36 days. We do have a 16-core
machine that I have an account on a quarter of (it's a long story),
so that could use up a full period of AS183 in a little over 2 days.
So what *used* to be an excellent choice is so no longer.
The 2006 Wichmann-Hill algorithm not only has a longer period,
but has the relevant-to-Erlang property of letting you set up
*multiple* streams quite straightforwardly, as discussed in the
paper. It also has a small state, which is nice for keeping
Erlang processes that use random numbers small.
It really is time that the Erlang library used something other than
AS183, and this looks like a good choice.
More information about the erlang-questions