Re: Just how predictable is Lua's random function

The BBS generator is not useful when p * q is smaller than, say, 2^1024. It's for cryptographic purposes only.

You could try this one. The period is about 2^185.

-- P. L'Ecuyer, "Combined Multiple Recursive Random Number Generators"

-- Operations Research, 44, 5 (1996), 816–822.

-- generates a 'random' number x, 0 <= x < 1

local random

do

    -- fill these two arrays with start values in [0..2^31-1)

    local X = {990831825, 586698796, 1722973357}

    local Y = {239391773, 1747290357, 373426315}

    -- moduli

    local M1 = 2147483647

    local M2 = 2145483479

    function random()

        local xn = (63308*X[2] - 183326*X[3]) % M1

        local yn = (86098*Y[1] - 539608*Y[3]) % M2

        X = {xn, X[1], X[2]}

        Y = {yn, Y[1], Y[2]}

        return ((xn - yn) % M1)/M1

    end

end

for i = 1, 10000 do

    local r = random()

    print(r)

end

On Feb 21, 2007, at 1:37 PM, Jerome Vuarand wrote:

Rici Lake wrote:

On 21-Feb-07, at 12:25 PM, Jeremy Darling wrote:

Just as the subject says, I'm curious just exactly how predictable

the random function is given a known seed.  If I use the same seed

on all platforms (Windows, Linux, and Mac) can I expect the next N

calls to random to always generate the same values?  This seems to

be the case on Windows, but I can't validate it on the other

platforms (yet). 

Lua uses the standard C library random function, which is

deterministic. However, it might not be the same implementation on

all platforms; i.e. you might get a different sequence starting from

the same seed on a 64-bit platform than on a 32-bit platform (for

example), or with different C standard library implementations.    

If portability of the pseudo-random sequence is important to you you can simply roll your own random function. Some pseudo-random generators have very basic implementations:

http://en.wikipedia.org/wiki/List_of_pseudorandom_number_generators

For example here is an example implementation (took me 5 minutes) of the first one on the list above (Blum Blum Shub) in Lua:

do

local p = 7907 -- 11 in wikipedia example, but has a too short cycle

local q = 7919 -- 19 in wikipedia example

local s = 3

local xn = s

assert(p%4==3)

assert(q%4==3)

function randombit()

    xn = xn^2 % p*q

    return xn % 2

end

function randomseed(seed)

    xn = seed

end

function random()

    local n = 0

    for i=0,31 do

        n = n*2 + randombit()

    end

    return n

end

end

randomseed(37)

for i=1,10 do

    print(string.format("%08X", random()))

end

print("------------------------")

randomseed(37)

for i=1,10 do

    print(string.format("%08X", random()))

end

--

Gé Weijers

ge@weijers.org