Page 1 of 1

Fast PRNG in pure Lua

Posted: Fri Aug 07, 2015 1:23 am
by airstruck
A port of Johannes Baagøe's Alea.

It's faster than Love's love.math.random and love.math.randomNormal, but slower than Lua's math.random.

It has a nice even distribution. The "Mash" function might also be useful as a general purpose hash function.

Code: Select all

-- A LuaJIT port of Johannes Baagøe's Alea

-- From http://baagoe.com/en/RandomMusings/javascript/
-- Johannes Baagøe <[email protected]>, 2010

-- Mirrored at:
-- https://github.com/nquinlan/better-random-numbers-for-javascript-mirror

local rshift, bor, floor = bit.rshift, bit.bor, math.floor

local function Mash ()
  local n = 0xefc8249d

  local function mash (data)
    data = tostring(data)
    
    for i = 1, data:len() do
      n = n + data:byte(i)
      local h = 0.02519603282416938 * n
      n = rshift(floor(h), 0)
      h = h - n
      h = h * n
      n = rshift(floor(h), 0)
      h = h - n
      n = n + h * 0x100000000 -- 2^32
    end
    return rshift(floor(n), 0) * 2.3283064365386963e-10 -- 2^-32
  end

  -- mash.version = 'Mash 0.9';
  return mash
end

local function Alea (...)
  return (function (args)
    local s0 = 0
    local s1 = 0
    local s2 = 0
    local c = 1

    if #args == 0 then
      args = { os.time() }
    end
    local mash = Mash()
    s0 = mash(' ')
    s1 = mash(' ')
    s2 = mash(' ')

    for i = 1, #args do
      s0 = s0 - mash(args[i])
      if s0 < 0 then
        s0 = s0 + 1
      end
      s1 = s1 - mash(args[i])
      if s1 < 0 then
        s1 = s1 + 1
      end
      s2 = s2 - mash(args[i])
      if s2 < 0 then
        s2 = s2 + 1
      end
    end
    mash = nil

    local random = {}
    local function _random ()
      local t = 2091639 * s0 + c * 2.3283064365386963e-10 -- 2^-32
      s0 = s1
      s1 = s2
      c = bor(floor(t), 0)
      s2 = t - c
      return s2
    end
    function random.uint32 ()
      return random() * 0x100000000 -- 2^32
    end
    function random.fract53 ()
      return random() + 
        bor(floor(random() * 0x200000), 0) * 1.1102230246251565e-16 -- 2^-53
    end
    random.version = 'Alea 0.9'
    random.args = args
    return setmetatable(random, { __call = _random })

  end)({ ... })
end

return Alea
https://gist.github.com/airstruck/7e4f03bee327e5e7e5e4

Re: Fast PRNG in pure Lua

Posted: Sat Aug 08, 2015 6:53 pm
by markgo
It's faster than Love's love.math.random and love.math.randomNormal, but slower than Lua's math.random.
I request a benchmark

Re: Fast PRNG in pure Lua

Posted: Sat Aug 08, 2015 9:46 pm
by airstruck
markgo wrote:I request a benchmark
Here you go.

Needs to be run separately for each test, because tests can cause LuaJIT to bail out to interpreter and screw up other tests.

Run it like this:

Code: Select all

love . Alea
love . love.math.random
love . love.math.randomNormal
love . math.random
As far as I can tell, Alea is faster because LuaJIT can compile it. Interestingly, though, if the JIT has bailed out then Alea, love.math.random, and math.random all perform about the same, with Alea being slightly faster (not shown in this perf). I guess this is because Alea was designed to perform well in JavaScript, and Lua has similar characteristics regarding numbers and bitwise operations. The randomNormal function is slower in all cases.