Re: Just how predictable is Lua's random function

On Feb 21, 2007, at 11:05 PM, Gé Weijers wrote:

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

Gé Weijers

ge@weijers.org