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!

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

-- code removed at the request of @merwok.

Thanks for being on top of this !

that’s not relevant to OP’s question

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. :)

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:

prng_impl_test

Cart File | Forum Post |

	More cartridges by pancelor

More Cartridges [View All]

 

prng_impl_test

by pancelor

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))

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:

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:

prng_impl_test

by pancelor

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

2

I fixed some more edge cases with seeding, e.g. srand("cat") and srand(0) (both behave the same as srand(nil))

Here's the full code:

function init_rng(seed)
	local lo,hi
	local function _rnd(n)
		n=n or 1
		hi<<>=16
		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
	local function _srand(seed)
		seed = tonum(seed) or 0
		if seed==0 then
			hi,lo = 0x6000.9755,0xdead.beef
		else
			seed &= 0x7fff.ffff
			hi,lo = seed^^0xbead.29ba,seed
		end
		for i=1,32 do
			_rnd()
		end
	end

	_srand(seed)
	return {
		rnd=_rnd,
		srand=_srand,
		get_state=function() return hi,lo end, --compare peek4(0x5f44,2)
		set_state=function(nhi,nlo) hi,lo = nhi,nlo end,
	}
end

and if you'd rather a C implementation, see https://www.lexaloffle.com/bbs/?pid=81103#p (I guess the core algorithm hasn't changed since then! I assumed it had, but I guess just rnd(table) has changed)