It is high time we let go of the Mersenne Twister (2019)
1–10 of 56 posts
Re: It is high time we let go of the Mersenne Twister (2019)
#2(2019)
Re: It is high time we let go of the Mersenne Twister (2019)
#3The author of this paper suggests their xoshiro256 from the Xoshiro family[1] as an alternative. I found some discussion here[2] where it's suggested it has some fatal flaws as well, though I'm no expert.
Back when I wrote a path tracer, the quality of the random number generator was visible. The poor LCG[3] that my programming language sported resulted in obvious patterns in what should have been random noise.
So, for simulations where predictability etc is not a concern, what's the state of the art? And since I'm into microcontrollers, what's a decent choice when you only got a 8-bit CPU and very limited space (both code and memory)?
[1]: http://xoroshiro.di.unimi.it/
[2]: https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256....
[3]: https://en.wikipedia.org/wiki/Linear_congruential_generator
Re: It is high time we let go of the Mersenne Twister (2019)
#4The author of this paper suggests their xoshiro256 from the Xoshiro family[1] as an alternative. I found some discussion here[2] where it's suggested it has some fatal flaws as well, though I'm no expert. Back when I wrote a path tracer, the quality of the random number generator was visible. The poor LCG[3] that my programming language sported resulted in obvious patterns in what should have been random noise. So, f…
I am not really sure what is best and I am mostly interested in PRNGs for gaming anyways (which might optimise for performance over randomness, perhaps?), but with that said ...
I recently came across this discussion on RNG algorithms in JavaScript. Perhaps this short article has some good suggestions on algorithms that improve over Mersenne Twister: https://github.com/nquinlan/better-random-numbers-for-javasc...
Re: It is high time we let go of the Mersenne Twister (2019)
#5There has been a long discussion about the respective merits of modern replacements for the twister, such as PCG [1][2][3]
IMO, for monte-carlo type stuff (like your path tracer), PCG is good enough.
Here's another discussion: https://stats.stackexchange.com/questions/337927/is-pcg-rand...
[2] https://www.pcg-random.org/posts/on-vignas-pcg-critique.html
[3] https://www.johndcook.com/blog/2021/04/29/reinventing-rng/
Re: It is high time we let go of the Mersenne Twister (2019)
#6The author of this paper suggests their xoshiro256 from the Xoshiro family[1] as an alternative. I found some discussion here[2] where it's suggested it has some fatal flaws as well, though I'm no expert. Back when I wrote a path tracer, the quality of the random number generator was visible. The poor LCG[3] that my programming language sported resulted in obvious patterns in what should have been random noise. So, f…
I would take that with a pinch of salt. The PCG and Xoshiro guys seem to have some kind of feud so some of the criticisms might not be as big a problem as they are made out to be in practice. Here's a partial rebuttal:
https://www.reddit.com/r/programming/comments/8gx2d3/new_lin...
For a bit of "social proof" xoshiro256++ is the default PRNG is Julia.
Re: It is high time we let go of the Mersenne Twister (2019)
#7As just a datapoint from some random person, I needed a pseudo-random number generator just last week.
My use-case is semi-embedded, with two applications running on different hardware and operating systems, that both needed to generate streams of the same random data. I first naively went with just rand() to get it running, but obviously there's no guerantee that two completely different platforms' C libraries have the same PRNGs. So that didn't work.
Like many (?), the Mersenne Twister is the first name that pops into my head if I think of "known" PRNG implementations, so I investigated it. I quickly came to the conclusion that it was kind of large in terms of amount of code and state for many applications, so I kept looking.
Eventually I went with xorshift32 [1] and am very happy with that choice. The core of the implementation is ~10 lines of C, and my entire module (header+implementation, with mild commenting and a faux-main() test "driver") is sitting at 60 lines. It needs a whopping 32 bits of state, which I could manage to squeeze in just fine. :)
Re: It is high time we let go of the Mersenne Twister (2019)
#8The author of this paper suggests their xoshiro256 from the Xoshiro family[1] as an alternative. I found some discussion here[2] where it's suggested it has some fatal flaws as well, though I'm no expert. Back when I wrote a path tracer, the quality of the random number generator was visible. The poor LCG[3] that my programming language sported resulted in obvious patterns in what should have been random noise. So, f…
> The author of this paper suggests their xoshiro256 from the Xoshiro family[1] as an alternative. I found some discussion here[2] where it's suggested it has some fatal flaws as well, though I'm no expert.
PRNGs are complicated, and sometimes we don’t find out flaws in them until long after they are widely deployed – although test suites like U01 Big Crush and PractRand should really help that situation out. Part of the problem is that some people just keep doing what they’ve always done and don’t want to see that the building is on fire.
I took a Computational Physics class in 2011 that was still advocating Mersenne Twister as state of the art, despite the widely publicised flaws and much better generators being around at the time. Others were fine with just using a Linear Congruential Generator with decent constants. We did have one class that encouraged us to plot RANDU and see the pattern, but I recall the resolution was to use an LCG with better constants.
I spent a while looking into PRNGs then, particularly the test suites available then. At the time, I think two approaches stood out as being fast and suitably random: xorshift plus weyl function (apparently now used in CUDA toolkit) and AES with reduced rounds.
Sometimes it’s important to recognise that there are possibly people still doing science with Linear Congruential Generators, and we can do a lot better even if a PRNG doesn’t pass every test. These test suites are designed to catch PRNGs out. It’s an adversarial situation, where better tests lead to better generators that lead to better tests – and it’s worth pointing out that some tests are so sensitive that they will give false positives by chance alone.
> So, for simulations where predictability etc is not a concern, what's the state of the art? And since I'm into microcontrollers, what's a decent choice when you only got a 8-bit CPU and very limited space (both code and memory)?
I don’t think this is going to be the same generator as used in MCMC experiments, but I would imagine a xorshift generator could be implemented in 8 bits with a bit of thought or research.
Re: It is high time we let go of the Mersenne Twister (2019)
#9The author of this paper suggests their xoshiro256 from the Xoshiro family[1] as an alternative. I found some discussion here[2] where it's suggested it has some fatal flaws as well, though I'm no expert. Back when I wrote a path tracer, the quality of the random number generator was visible. The poor LCG[3] that my programming language sported resulted in obvious patterns in what should have been random noise. So, f…
I am not really sure what is best and I am mostly interested in PRNGs for gaming anyways (which might optimise for performance over randomness, perhaps?), but with that said ... I recently came across this discussion on RNG algorithms in JavaScript. Perhaps this short article has some good suggestions on algorithms that improve over Mersenne Twister: https://github.com/nquinlan/better-random-numbers-for-javasc...
The core RNGs of the three main JS engines are I believe at this point all Xorshift variants (same core structure, slightly different code interfaces).
They also seed (or should seed, I know JSC does) per-global object from a CSRNG.
If you have an application that really does need secure random the Dom specifies crypto.getRandomValues, which is specified as requiring a cryptographically secure implementation.
Re: It is high time we let go of the Mersenne Twister (2019)
#10As just a datapoint from some random person, I needed a pseudo-random number generator just last week. My use-case is semi-embedded, with two applications running on different hardware and operating systems, that both needed to generate streams of the same random data. I first naively went with just rand() to get it running, but obviously there's no guerantee that two completely different platforms' C libraries have…
I came to a similar conclusion when I was looking for a simple RNG. I chose the top 32 bits of xorshift64* [1], as it was noted that it passes BigCrush. Of course, that probably comes at a performance cost.
[1]: https://github.com/cgmb/euler/blob/a906355343dc0d320858a7b00...