4 ms·
To give you a sense of how tiny and simple this excellent pseudorandom number generator is, here is a stand-alone implementation of PCG32 in Go: package pcg3
by 37ef_ced3 5y ago
To give you a sense of how tiny and simple this excellent pseudorandom number generator is, here is a stand-alone implementation of PCG32 in Go:
package pcg32
type Src [2]uint64
func New(bits1, bits2 uint64) *Src {
return &Src{bits1, bits2 | 1}
}
func (s *Src) Uint32() uint32 {
var (
x = s[0]
y = uint32(x >> 59)
z = uint32((x>>18 ^ x) >> 27)
)
s[0] = s[1] + x*6364136223846793005
return z>>y | z<<(-y&31)
}
func (s *Src) LessThan(n uint32) uint32 {
for min := -n % n; ; {
r := s.Uint32()
if r >= min {
return r % n
}
}
}
- aappleby 5y agoI predict that prng will totally fail the DieHard tests.
- 37ef_ced3 5y agoAnd you'd be wrong Here: https://www.johndcook.com/blog/2017/07/07/testing-the-pcg-random-number-generator/ https://www.johndcook.com/blog/2017/07/07/testing-the-pcg-ra...
- aappleby 5y agoI could very well be wrong, I haven't checked yet. That said, I have done a bit of work with these sort of things.
- aappleby 5y agoI'll read the paper.
- aappleby 5y agoAh, I missed that there was a data-dependent rotation applied in the output. So it's a lcg plus xorshift plus ddr. Still weaker than I'd like, but if it passes DieHard etc then it passes.
- 37ef_ced3 5y agoYeah, that pseudorandom rotation is what makes PCG novel
- TapamN 5y agoDoes it need to pass them? A stronger algorithm wouldn't hurt, but it's not being used for cryptography or scientific simulations. It's just for games. With the goal of having sharable seeds, the smaller space could be considered beneficial. The right tool for the job is more important. Even an 8-bit LFSR is good for certain tasks, like randomizing particle effects for an NES game.
- 37ef_ced3 5y agoPCG is a top-quality pseudorandom number generator, suitable for all non-crypto prng applications Here are the DIEHARDER results: https://www.johndcook.com/blog/2017/07/07/testing-the-pcg-random-number-generator/ https://www.johndcook.com/blog/2017/07/07/testing-the-pcg-ra...
- dwohnitmok 5y agoNot quite "all prng applications." As TapamN points out it is not cryptographically secure and can be broken. https://hal.inria.fr/hal-02700791/ https://hal.inria.fr/hal-02700791/ But it's probably fine for non-crytographic uses (and indeed is widely used for such). [parent comment has now added "non-crypto" to the original quote so that "all prng applications" is now moot]
- bawolff 5y agoUsually people say CSPRNG if its secure for crypto applications. Just saying PRNG kind of implies its not cryptographically secure
- dwohnitmok 5y agoFair enough.
- bhaak 5y ago> It's just for games. http://taeb-nethack.blogspot.com/2009/03/predicting-and-controlling-nethacks.html http://taeb-nethack.blogspot.com/2009/03/predicting-and-cont... https://pellsson.github.io/ https://pellsson.github.io/ Of course, nobody is in danger because your game's random state can be deduced. But it can disrupt online play quite a bit. Just imagine what this can mean for tournaments.
- VHRanger 5y agoAnd here's a threadsafe C++ one in <30 lines of meaningful code: https://github.com/VHRanger/pcg.h/blob/master/pcg.h https://github.com/VHRanger/pcg.h/blob/master/pcg.h