1

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

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

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 ▽ | 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 ▽ | No License
2

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