Log In  

I keep running into scenarios where knowing what algorithm pico-8 uses for random number generation would come in handy. Does anyone know what it is or how to get that info? Thanks!

P#124120 2023-01-12 05:51

4

Here's a re-implementation of PICO-8's RNG in PICO-8. Of note, the last line of rng.rnd is just returning rng.hi%n but with some modulo arithmetic to account for within-PICO-8-overflow and be 1:1 with calling the built-in rnd.

function init_rng(seed)
 local rng={}
 function rng.srand(seed)
  seed=seed or 0
  rng.hi,rng.lo=
   seed==0 and 0x6000.9755 or seed^^0xbead.29ba,
   seed==0 and 0xdead.beef or seed
  for i=1,0x20 do rng.rnd() end
 end
 function rng.rnd(n)
  n=n or 1
  rng.hi=(rng.hi<<0x10|rng.hi>>>0x10)+rng.lo
  rng.lo+=rng.hi
  return ((rng.hi<0 and 0x8000-n or 0)%n+(rng.hi&0x7fff.ffff)%n)%n
 end
 rng.srand(seed)
 return rng
end
P#124122 2023-01-12 06:14 ( Edited 2023-01-12 21:26)

-- code removed at the request of @merwok.

Thanks for being on top of this !

P#124123 2023-01-12 06:33 ( Edited 2023-01-12 18:51)
1

that’s not relevant to OP’s question

P#124148 2023-01-12 15:45
 
P#124156 [hidden by admin]

While I'm not 100% certain, PICO-8 does not seem to be using Lua's in-built PRNG. Doing a test with Lua's math.random() function and PICO-8's rnd() function, both with the same seed, gives different results. I know that doesn't give you a complete answer, but at least eliminates one possibility. :)

P#124226 2023-01-13 16:33

thanks @Meep, very helpful!

a small correction: negative seeds don't behave properly; I messed with the code a bit and this seems to fix it:
seed=(seed or 0)&0x7fff.ffff

edit: hmm I made an automatic test case and found more discrepancies; there's some issue that occurs only sometimes when the m in prng.rnd(m) is negative. it doesn't break the prng's state, but something about the return rng.hi%n replacement isn't working. here's a test cart:

Cart #prng_impl_test-0 | 2024-07-21 | Code ▽ | Embed ▽ | No License

and here's a minimal repro: (even after adding in my &0x7ff...)

cls()
s,m = -2319,0xdc19.beb0
srand(s)
prng=init_rng(s)
assert(rnd(m)==prng.rnd(m))
P#151580 2024-07-21 01:37
2

I figured it out! here's a repro with nicer numbers:

cls()
s,m = 1,-1
srand(s)
prng = init_rng(s)
r1 = rnd(m)
r2 = prng.rnd(m)
?tostr(r1,1)
?tostr(r2,1)
assert(r1==r2)

the issue boils down to trying to do hi%n while treating hi and n as u32s, but pico8 represents them as i32s. for example, hi%n has issues when n=0xffff -- as a u32, n is almost certainly higher than hi, so the result should be hi. but as an i32, n is -1, and so hi%n discards the integer part of hi, returning hi&0x0.ffff instead.

more details:


An example using u3s (0...7) and i3s (-4...3): (6 as u3)%(7 as u3) is 6%7 is 6. But (6 as i3)%(7 as i3) is (-2)%(-1), which is 0 in pico8.

There's also the issue that most modulus won't "wrap around" nicely -- (4 as u3)%3 is 4%3 is 1, but (4 as i3)%3 is (-4)%3 is 2. Meep already fixed this with the (0x8000-n)%n thing; I don't quite understand how it works so I replaced it with (0x7fff%n+1)%n

here's the fixed code:

    local function _rnd(n)
        n=n or 1
        hi<<>=0x10
        hi+=lo
        lo+=hi

        -- return hi%n, but treat hi and n as if they were u32 instead of i32
        if n<0 then
            return n<=hi and hi<0 and hi-n or hi
        end
        -- hi := hi8 + hi7
        -- hi%n = (hi8%n + hi7%n)%n
        return ((hi<0 and 0x7fff%n+1 or 0) + (hi&0x7fff.ffff)%n) % n
    end

and here it is in the test cart:

Cart #prng_impl_test-1 | 2024-07-21 | Code ▽ | Embed ▽ | No License
2

P#151593 2024-07-21 08:32 ( Edited 2024-07-21 20:57)

[Please log in to post a comment]