Re: Lua 5.4 random number generator

[Coda Highland <chighland@...>]

On Mon, Mar 26, 2018 at 12:01 PM, albertmcchan <albertmcchan@yahoo.com> wrote:
> On Mar 26, 2018, at 11:34 AM, Coda Highland <chighland@gmail.com> wrote:
>
> On Mar 26, 2018 9:38 AM, "albertmcchan" <albertmcchan@yahoo.com> wrote:
>
>
> I tried print out 128 last bits (128 math.random calls), but I do not
> see the pattern.  How does the prediction work ?
>
> You can try it on lua 5.4.0-work1
>
> function last128()
>     for i=1,128 do io.write(math.random(0) & 1) end
> end
>
>
> It's not trivial. There's not a visible pattern but you can do math to
> reverse-engineer the internal state with that data. I don't know the
> technique myself.
>
> /s/ Adam
>
>
> If what you are saying is true, period of last128() is also 2^128 - 1, all
> unique.
>
> Each last128() map 1-to-1 to 2^128 - 1 internal states.
>
> one last128() pattern will never occurs. (all zeroes ?)

Not "all unique" because the output of the PRNG isn't 128 bits -- by
the pigeonhole principle, some of the function outputs will be
duplicated along the way, but importantly the SEQUENCE of those
outputs will NOT be repeated.

It's not impossible that the period will be less than 2^128-1. It
depends on the specific implementation of the algorithm and on the
chosen seed value. We already know that there's one
obviously-degenerate seed: zero. But there may be other seeds that
have short periods, and if even one such weak seed exists, then even
the best seed cannot possibly have the full theoretical period.

One possible PRNG design that would guarantee that every internal
state is reachable from every other internal state would be one that
uses a strict linear counter, just adding 1 to the state each time and
then performing some sort of strong hash function on the output. Even
this design wouldn't guarantee good results, though.

Ultimately, 128 bits is just way too small of a state vector if you
need GOOD random numbers. (Mersenne Twister uses something like
2.5KB.) But if you need FAST random numbers with minimal code and RAM
footprint, and you don't mind if they're kinda weak, Lua's choice
makes a lot of sense.

/s/ Adam