6 ms·

It is high time we let go of the Mersenne Twister (2019)

schoen 5y ago
(2019)
magicalhippo 5y ago
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. 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/ http://xoroshiro.di.unimi.it/ [2]: https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.html https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.... [3]: https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator
- wsc981 5y ago
  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-javascript-mirror https://github.com/nquinlan/better-random-numbers-for-javasc...
  - olliej 5y ago
    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.
  - ajuc 5y ago
    My master's thesis was about PRNGs in gaming, mostly about applications but I also did comparison of performance of several generators. Linear Congruential was the fastest of the ones I've tried. ~27 vs ~25 FPS over more complicated generators in a simple 2d arcade game where everything was randomly generated on the fly to showcase how you can use PRNGs in games. I don't remember if I tested xorshift or some other LFSR, it was back in 2009. The results were highly dependent on how many times you use the generator without changing the seed, and I think most games will have similar distribution (over 50% of the time you use the same seed less than 100 times without changing) or even more skewed. Thesis is in Polish so probably won't be of much use, but if anybody's interested: https://easyupload.io/ub59ej https://easyupload.io/ub59ej
- anewhnaccount2 5y ago
  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_line_of_fast_prngs_released_by_the_author_of/dyqu7dm/ https://www.reddit.com/r/programming/comments/8gx2d3/new_lin... For a bit of "social proof" xoshiro256++ is the default PRNG is Julia.
  - JoachimS 5y ago
    Sebastiano Vigna seems to have a beef. For all I've seen M.E. O'Neill has handled the situation really well. Taking Vignas claims and critique seriously. https://www.pcg-random.org/posts/on-vignas-pcg-critique.html https://www.pcg-random.org/posts/on-vignas-pcg-critique.html
    - jart 5y ago
      Here's Vigna's random function if anyone's curious. uint64_t vigna_r(uint64_t state[static 1]) { uint64_t z = (state[0] += 0x9e3779b97f4a7c15); z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; z = (z ^ (z >> 27)) * 0x94d049bb133111eb; return z ^ (z >> 31); } It passes bigcrush and practrand plus -ftree-vectorize makes it faster than xorshift.
      - deleted 5y ago
        [deleted]
  - sundarurfriend 5y ago
    My practical takeaway from these discussions is that for most people, in most situations, any of these modern choices are good enough for purpose - the differences (in whichever direction they lay) come in only when you're pushing the PRNG to its extremes, while operating with a specific set of constraints.
    - logos001 5y ago
- dpwm 5y ago
  > 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.
  - google234123 5y ago
    To be fair, you should expect to learn state of the art CS in a Computational Physics class. That’s not the goal..
    - google234123 5y ago
      Shouldn’t *
- WithinReason 5y ago
  For Monte Carlo integration you want low discrepancy sequences or blue noise, not random numbers.
  - steerablesafe 5y ago
    That's easier said then done, when you integrate over a high dimensional (possibly infinite) space.
- nsajko 5y ago
  > I found some discussion here[2] where it's suggested it has some fatal flaws as well The described flaws are not really flaws. The author of the blog post has a strange perspective on what a PRNG should be. > 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? Can't you just try different ones? E.g., try xoshiro256++, xoshiro256** and some CSPRNG, and compare for visible patterns. The reality is that AFAIK the state of the art doesn't exist, there seems to be little scientific interest for non-secure fast pseudo-random generators with good statistical properties. Usually one checks for bad statistical properties with ad-hoc tools like Practrand, basically test suites. But Practrand is buggy and unmaintained and there's no better option AFAIK. In summary, test the PRNG on a per-application basis yourself, or just use xoshiro256++. Just my impressions.
  - logos001 5y ago
    If performance is not as critical, I would probably pick AES or Chacha any day over those. Furthermore they make parallelizable reproducible streams trivial.
ur-whale 5y ago
There 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-random-number-generator-as-good-as-claimed https://stats.stackexchange.com/questions/337927/is-pcg-rand... [1] https://prng.di.unimi.it/ https://prng.di.unimi.it/ [2] https://www.pcg-random.org/posts/on-vignas-pcg-critique.html https://www.pcg-random.org/posts/on-vignas-pcg-critique.html [3] https://www.johndcook.com/blog/2021/04/29/reinventing-rng/ https://www.johndcook.com/blog/2021/04/29/reinventing-rng/
- logos001 5y ago
  I suppose the question is do you really need to get rid of the Mersenne-Twister? Most of the modern variants are good enough for most practical purposes. https://chasethedevil.github.io/post/war-of-the-random-number-generators/ https://chasethedevil.github.io/post/war-of-the-random-numbe...
unwind 5y ago
As 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. :) [1]: https://en.wikipedia.org/wiki/Xorshift https://en.wikipedia.org/wiki/Xorshift
- slavik81 5y ago
  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/a906355343dc0d320858a7b00504040d04c053f7/misc/rng.c https://github.com/cgmb/euler/blob/a906355343dc0d320858a7b00...
  - jart 5y ago
    It's unlikely xorshift64 top bits pass bigcrush. RNG_test using PractRand version 0.95 RNG = RNG_stdin32, seed = unknown test set = core, folding = standard (32 bit) rng=RNG_stdin32, seed=unknown length= 512 megabytes (2^29 bytes), time= 3.1 seconds Test Name Raw Processed Evaluation BRank(12):128(4) R= +2544 p~= 4e-1354 FAIL !!!!!!!! BRank(12):256(4) R= +8055 p~= 4e-4285 FAIL !!!!!!!! BRank(12):384(1) R= +6783 p~= 5e-2043 FAIL !!!!!!!! BRank(12):512(2) R=+13490 p~= 8e-4062 FAIL !!!!!!!! BRank(12):768(1) R=+15050 p~= 2e-4531 FAIL !!!!!!!! BRank(12):1K(2) R=+29077 p~= 4e-8754 FAIL !!!!!!!! BRank(12):1536(1) R=+31582 p~= 2e-9508 FAIL !!!!!!!! BRank(12):2K(1) R=+42604 p~= 0 FAIL !!!!!!!! [Low8/32]BRank(12):128(4) R= +2544 p~= 4e-1354 FAIL !!!!!!!! [Low8/32]BRank(12):256(4) R= +8055 p~= 4e-4285 FAIL !!!!!!!! [Low8/32]BRank(12):384(1) R= +6783 p~= 5e-2043 FAIL !!!!!!!! [Low8/32]BRank(12):512(2) R=+13490 p~= 8e-4062 FAIL !!!!!!!! [Low8/32]BRank(12):768(1) R=+15050 p~= 2e-4531 FAIL !!!!!!!! [Low8/32]BRank(12):1K(2) R=+29077 p~= 4e-8754 FAIL !!!!!!!! [Low8/32]BRank(12):1536(1) R=+31582 p~= 2e-9508 FAIL !!!!!!!! [Low1/32]BRank(12):128(4) R= +2544 p~= 4e-1354 FAIL !!!!!!!! [Low1/32]BRank(12):256(2) R= +5696 p~= 1e-1715 FAIL !!!!!!!! [Low1/32]BRank(12):384(1) R= +6783 p~= 5e-2043 FAIL !!!!!!!! [Low1/32]BRank(12):512(2) R=+13490 p~= 8e-4062 FAIL !!!!!!!! [Low1/32]BRank(12):768(1) R=+15050 p~= 2e-4531 FAIL !!!!!!!! ...and 160 test result(s) without anomalies Consider using this instead if you want a simple PRNG: uint64_t lemire64(void) { static uint128_t s = (uint128_t)426679527491843471 << 64 | 2131259787901769494; return (s *= 15750249268501108917ull) >> 64; }
bhaak 5y ago
My goto RNG for a small, supposedly cryptographical secure RNG is ISAAC. https://en.wikipedia.org/wiki/ISAAC_(cipher) https://en.wikipedia.org/wiki/ISAAC_(cipher) (There's a standalone C code implementation available at https://ccodearchive.net/info/isaac.html https://ccodearchive.net/info/isaac.html)
eternityforest 5y ago
Is there anything wrong with ARC4 as a fast non cryptographic generator?
- maskros 5y ago
  RC4 works fine. The only "problem" is its large state (2048) compared to the common LCG and Xorshift PRNGs which typically have anywhere between 32 and 256 bits of state. Sqlite3 uses RC4 for its random functions.
failrate 5y ago
For games, Squirrel Noise 3 is great.
37ef_ced3 5y ago
Use PCG: https://www.pcg-random.org/ https://www.pcg-random.org/ 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 } } }
- kloch 5y ago
  Multipliers for other widths: https://www.pcg-random.org/posts/does-it-beat-the-minimal-standard.html https://www.pcg-random.org/posts/does-it-beat-the-minimal-st...
- SamiPerttu 5y ago
  Unfortunately, any PCG code is not complete without a seeding procedure. That is, if you enter non-random seeds, you can get correlated streams, which is very bad for randomness.
  - 37ef_ced3 5y ago
    You need 128 random bits to seed the generator (i.e., two uint64 variables). The bits1 and bits2 arguments to pcg32.New() should each be 64 bits of "noise". They may be drawn from /dev/urandom or whatever. You can use crypto/rand.Read() from Go's standard library, for example. Just read 16 bytes using crypto/rand.Read() and use encoding/binary.LittleEndian.Uint64() to produce bits1 and bits2. Or you can use a hash to produce bits1 and bits2. If you want to use a constant seed, take 32 hex digits from an arbitrary git commit id. Like this: bits1=0xd240853866f20fc3 bits2=0xe536cb3bca86c86c It's an orthogonal issue.
runxel 5y ago
Just a few days ago I had the need to implement a random function with a niche proprietary language, where you have no binary data type. Only strings, integers, and floats. Thats fun! I instead used a Lehmer generator with 32-bit arithmetics. I also wondered if there are any better solutions.
rurban 5y ago
my latest PRNG's shootout is here https://rurban.github.io/dieharder/QUALITY.html https://rurban.github.io/dieharder/QUALITY.html with quality and speed comparison of all known implementations.
rogue7 5y ago
The approach JAX takes regarding PRNG for numerical computing is worth a look: https://github.com/google/jax/blob/main/docs/design_notes/prng.md https://github.com/google/jax/blob/main/docs/design_notes/pr...
logos001 5y ago
This is an interesting paper, but it has been posted to hacker news in 2020 already: https://news.ycombinator.com/item?id=25166095 https://news.ycombinator.com/item?id=25166095 I had written about it around that time on my blog, for the curious: https://chasethedevil.github.io/post/war-of-the-random-number-generators/ https://chasethedevil.github.io/post/war-of-the-random-numbe... and the sequel https://chasethedevil.github.io/post/more-on-random-number-generators/ https://chasethedevil.github.io/post/more-on-random-number-g... A neat remark from the above: Monte-Carlo simulations run at the Los Alamos National Laboratory relied on a relatively simple linear congruential generator (LCG) producing 24- or 48-bits integers for at least 40 years

(2019)

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. 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/ http://xoroshiro.di.unimi.it/ [2]: https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.html https://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.... [3]: https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator

wsc981 5y ago
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-javascript-mirror https://github.com/nquinlan/better-random-numbers-for-javasc...
- olliej 5y ago
  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.
- ajuc 5y ago
  My master's thesis was about PRNGs in gaming, mostly about applications but I also did comparison of performance of several generators. Linear Congruential was the fastest of the ones I've tried. ~27 vs ~25 FPS over more complicated generators in a simple 2d arcade game where everything was randomly generated on the fly to showcase how you can use PRNGs in games. I don't remember if I tested xorshift or some other LFSR, it was back in 2009. The results were highly dependent on how many times you use the generator without changing the seed, and I think most games will have similar distribution (over 50% of the time you use the same seed less than 100 times without changing) or even more skewed. Thesis is in Polish so probably won't be of much use, but if anybody's interested: https://easyupload.io/ub59ej https://easyupload.io/ub59ej
anewhnaccount2 5y ago
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_line_of_fast_prngs_released_by_the_author_of/dyqu7dm/ https://www.reddit.com/r/programming/comments/8gx2d3/new_lin... For a bit of "social proof" xoshiro256++ is the default PRNG is Julia.
- JoachimS 5y ago
  Sebastiano Vigna seems to have a beef. For all I've seen M.E. O'Neill has handled the situation really well. Taking Vignas claims and critique seriously. https://www.pcg-random.org/posts/on-vignas-pcg-critique.html https://www.pcg-random.org/posts/on-vignas-pcg-critique.html
  - jart 5y ago
    Here's Vigna's random function if anyone's curious. uint64_t vigna_r(uint64_t state[static 1]) { uint64_t z = (state[0] += 0x9e3779b97f4a7c15); z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; z = (z ^ (z >> 27)) * 0x94d049bb133111eb; return z ^ (z >> 31); } It passes bigcrush and practrand plus -ftree-vectorize makes it faster than xorshift.
    - deleted 5y ago
      [deleted]
- sundarurfriend 5y ago
  My practical takeaway from these discussions is that for most people, in most situations, any of these modern choices are good enough for purpose - the differences (in whichever direction they lay) come in only when you're pushing the PRNG to its extremes, while operating with a specific set of constraints.
  - logos001 5y ago
dpwm 5y ago
> 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.
- google234123 5y ago
  To be fair, you should expect to learn state of the art CS in a Computational Physics class. That’s not the goal..
  - google234123 5y ago
    Shouldn’t *
WithinReason 5y ago
For Monte Carlo integration you want low discrepancy sequences or blue noise, not random numbers.
- steerablesafe 5y ago
  That's easier said then done, when you integrate over a high dimensional (possibly infinite) space.
nsajko 5y ago
> I found some discussion here[2] where it's suggested it has some fatal flaws as well The described flaws are not really flaws. The author of the blog post has a strange perspective on what a PRNG should be. > 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? Can't you just try different ones? E.g., try xoshiro256++, xoshiro256** and some CSPRNG, and compare for visible patterns. The reality is that AFAIK the state of the art doesn't exist, there seems to be little scientific interest for non-secure fast pseudo-random generators with good statistical properties. Usually one checks for bad statistical properties with ad-hoc tools like Practrand, basically test suites. But Practrand is buggy and unmaintained and there's no better option AFAIK. In summary, test the PRNG on a per-application basis yourself, or just use xoshiro256++. Just my impressions.
- logos001 5y ago
  If performance is not as critical, I would probably pick AES or Chacha any day over those. Furthermore they make parallelizable reproducible streams trivial.

ur-whale 5y ago

There 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-random-number-generator-as-good-as-claimed https://stats.stackexchange.com/questions/337927/is-pcg-rand... [1] https://prng.di.unimi.it/ https://prng.di.unimi.it/ [2] https://www.pcg-random.org/posts/on-vignas-pcg-critique.html https://www.pcg-random.org/posts/on-vignas-pcg-critique.html [3] https://www.johndcook.com/blog/2021/04/29/reinventing-rng/ https://www.johndcook.com/blog/2021/04/29/reinventing-rng/

logos001 5y ago
I suppose the question is do you really need to get rid of the Mersenne-Twister? Most of the modern variants are good enough for most practical purposes. https://chasethedevil.github.io/post/war-of-the-random-number-generators/ https://chasethedevil.github.io/post/war-of-the-random-numbe...

unwind 5y ago

As 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. :) [1]: https://en.wikipedia.org/wiki/Xorshift https://en.wikipedia.org/wiki/Xorshift

slavik81 5y ago
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/a906355343dc0d320858a7b00504040d04c053f7/misc/rng.c https://github.com/cgmb/euler/blob/a906355343dc0d320858a7b00...
- jart 5y ago
  It's unlikely xorshift64 top bits pass bigcrush. RNG_test using PractRand version 0.95 RNG = RNG_stdin32, seed = unknown test set = core, folding = standard (32 bit) rng=RNG_stdin32, seed=unknown length= 512 megabytes (2^29 bytes), time= 3.1 seconds Test Name Raw Processed Evaluation BRank(12):128(4) R= +2544 p~= 4e-1354 FAIL !!!!!!!! BRank(12):256(4) R= +8055 p~= 4e-4285 FAIL !!!!!!!! BRank(12):384(1) R= +6783 p~= 5e-2043 FAIL !!!!!!!! BRank(12):512(2) R=+13490 p~= 8e-4062 FAIL !!!!!!!! BRank(12):768(1) R=+15050 p~= 2e-4531 FAIL !!!!!!!! BRank(12):1K(2) R=+29077 p~= 4e-8754 FAIL !!!!!!!! BRank(12):1536(1) R=+31582 p~= 2e-9508 FAIL !!!!!!!! BRank(12):2K(1) R=+42604 p~= 0 FAIL !!!!!!!! [Low8/32]BRank(12):128(4) R= +2544 p~= 4e-1354 FAIL !!!!!!!! [Low8/32]BRank(12):256(4) R= +8055 p~= 4e-4285 FAIL !!!!!!!! [Low8/32]BRank(12):384(1) R= +6783 p~= 5e-2043 FAIL !!!!!!!! [Low8/32]BRank(12):512(2) R=+13490 p~= 8e-4062 FAIL !!!!!!!! [Low8/32]BRank(12):768(1) R=+15050 p~= 2e-4531 FAIL !!!!!!!! [Low8/32]BRank(12):1K(2) R=+29077 p~= 4e-8754 FAIL !!!!!!!! [Low8/32]BRank(12):1536(1) R=+31582 p~= 2e-9508 FAIL !!!!!!!! [Low1/32]BRank(12):128(4) R= +2544 p~= 4e-1354 FAIL !!!!!!!! [Low1/32]BRank(12):256(2) R= +5696 p~= 1e-1715 FAIL !!!!!!!! [Low1/32]BRank(12):384(1) R= +6783 p~= 5e-2043 FAIL !!!!!!!! [Low1/32]BRank(12):512(2) R=+13490 p~= 8e-4062 FAIL !!!!!!!! [Low1/32]BRank(12):768(1) R=+15050 p~= 2e-4531 FAIL !!!!!!!! ...and 160 test result(s) without anomalies Consider using this instead if you want a simple PRNG: uint64_t lemire64(void) { static uint128_t s = (uint128_t)426679527491843471 << 64 | 2131259787901769494; return (s *= 15750249268501108917ull) >> 64; }

bhaak 5y ago

My goto RNG for a small, supposedly cryptographical secure RNG is ISAAC. https://en.wikipedia.org/wiki/ISAAC_(cipher) https://en.wikipedia.org/wiki/ISAAC_(cipher) (There's a standalone C code implementation available at https://ccodearchive.net/info/isaac.html https://ccodearchive.net/info/isaac.html)

eternityforest 5y ago

Is there anything wrong with ARC4 as a fast non cryptographic generator?

maskros 5y ago
RC4 works fine. The only "problem" is its large state (2048) compared to the common LCG and Xorshift PRNGs which typically have anywhere between 32 and 256 bits of state. Sqlite3 uses RC4 for its random functions.

failrate 5y ago

For games, Squirrel Noise 3 is great.

37ef_ced3 5y ago

Use PCG: https://www.pcg-random.org/ https://www.pcg-random.org/ 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 } } }

kloch 5y ago
Multipliers for other widths: https://www.pcg-random.org/posts/does-it-beat-the-minimal-standard.html https://www.pcg-random.org/posts/does-it-beat-the-minimal-st...
SamiPerttu 5y ago
Unfortunately, any PCG code is not complete without a seeding procedure. That is, if you enter non-random seeds, you can get correlated streams, which is very bad for randomness.
- 37ef_ced3 5y ago
  You need 128 random bits to seed the generator (i.e., two uint64 variables). The bits1 and bits2 arguments to pcg32.New() should each be 64 bits of "noise". They may be drawn from /dev/urandom or whatever. You can use crypto/rand.Read() from Go's standard library, for example. Just read 16 bytes using crypto/rand.Read() and use encoding/binary.LittleEndian.Uint64() to produce bits1 and bits2. Or you can use a hash to produce bits1 and bits2. If you want to use a constant seed, take 32 hex digits from an arbitrary git commit id. Like this: bits1=0xd240853866f20fc3 bits2=0xe536cb3bca86c86c It's an orthogonal issue.

runxel 5y ago

Just a few days ago I had the need to implement a random function with a niche proprietary language, where you have no binary data type. Only strings, integers, and floats. Thats fun! I instead used a Lehmer generator with 32-bit arithmetics. I also wondered if there are any better solutions.

rurban 5y ago

my latest PRNG's shootout is here https://rurban.github.io/dieharder/QUALITY.html https://rurban.github.io/dieharder/QUALITY.html with quality and speed comparison of all known implementations.

rogue7 5y ago

The approach JAX takes regarding PRNG for numerical computing is worth a look: https://github.com/google/jax/blob/main/docs/design_notes/prng.md https://github.com/google/jax/blob/main/docs/design_notes/pr...

logos001 5y ago

This is an interesting paper, but it has been posted to hacker news in 2020 already: https://news.ycombinator.com/item?id=25166095 https://news.ycombinator.com/item?id=25166095 I had written about it around that time on my blog, for the curious: https://chasethedevil.github.io/post/war-of-the-random-number-generators/ https://chasethedevil.github.io/post/war-of-the-random-numbe... and the sequel https://chasethedevil.github.io/post/more-on-random-number-generators/ https://chasethedevil.github.io/post/more-on-random-number-g... A neat remark from the above: Monte-Carlo simulations run at the Los Alamos National Laboratory relied on a relatively simple linear congruential generator (LCG) producing 24- or 48-bits integers for at least 40 years