Re: All possible internal states of Erlang/OTP random module are practically computable

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/

Kenji Rikitake

++> Richard A. O'Keefe <[email protected]> [2014-12-23 17:14:39 +1300]:
> On 23/12/2014, at 1:46 pm, Kenji Rikitake <[email protected]> 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 Marsaglias 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.