[erlang-questions] All possible internal states of Erlang/OTP random module are practically computable
Tue Dec 23 08:30:36 CET 2014
I know there's NOTHING NEW on this from academic viewpoints. This is
just a brute-force scanning of the problem space. The reason why I wrote
this on the mailing list was to show the practicality of this rather
primitive brute-force computation method.
I've proposed and implemented five alternatives for this in Erlang (the
algorithms are of other math geniuses):
SFMT19937: https://github.com/jj1bdx/sfmt-erlang (Period: 2^19937-1)
TinyMT: https://github.com/jj1bdx/tinymt-erlang (Period: 2^127-1)
Xorshift*64: https://github.com/jj1bdx/exs64 (Period: 2^64-1)
Xorshift+128: https://github.com/jj1bdx/exsplus (Period: 2^128-1)
Xorshift*1024: https://github.com/jj1bdx/exs1024 (Period: 2^1024-1)
I agree that at least one algorithm should be in Erlang VM as a BIF
(Xorshift*64 will be a practical candidate because it's small and is
fast on a 64-bit machine, and will provide a sufficient long period).
More details on Xorshift*/Xorshift+: http://xorshift.di.unimi.it/
++> Richard A. O'Keefe <ok@REDACTED> [2014-12-23 17:14:39 +1300]:
> On 23/12/2014, at 1:46 pm, Kenji Rikitake <kenji@REDACTED> wrote:
> > This is a preliminary result of a brute-force check of the AS183 algorithm
> > looping period, using a C program running in the exactly same algorithm as in
> > the Erlang/OTP random module.
> The result is anything but surprising.
> > Conclusion: I have to say that Erlang/OTP "random" module should be
> > revised ASAP.
> We have known this for some time.
> There is a 4-generator version of the Wichmann-Hill idea; there is some
> IP restriction on it which I do not understand. The point is that the
> inventors of AS183 themselves believe it is past its use-by date.
> AS183 was an excellent choice for a 4 mB 20 MHz machine that secretly
> wanted to be a 16-bit machine. Those days are long past.
> George Marsaglia’s “Random Number Generators” is a good survey of
> the 2003 state of the art.
> Many of the good ones (not excluding the Mersenne Twister) require
> large mutable tables, so are best done in the VM.
> There is code for a Complementary-Multiply-With-Carry generator
> in the right column of page 9, and a table that can be used to
> shrink the table size to something lighter weight.
More information about the erlang-questions