Fast PRNG in pure Lua

Showcase your libraries, tools and other projects that help your fellow love users.
Post Reply
User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Fast PRNG in pure Lua

Post by airstruck » Fri Aug 07, 2015 1:23 am

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 <baagoe@baagoe.com>, 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

User avatar
markgo
Party member
Posts: 189
Joined: Sat Jan 05, 2013 12:21 am
Location: USA

Re: Fast PRNG in pure Lua

Post by markgo » Sat Aug 08, 2015 6:53 pm

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

User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Re: Fast PRNG in pure Lua

Post by airstruck » Sat Aug 08, 2015 9:46 pm

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.

Post Reply

Who is online

Users browsing this forum: No registered users and 4 guests