[HN Gopher] It is high time we let go of the Mersenne Twister (2...
___________________________________________________________________
It is high time we let go of the Mersenne Twister (2019)
Author : rdpintqogeogsaa
Score : 92 points
Date : 2022-03-09 07:06 UTC (15 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| magicalhippo wrote:
| 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/
|
| [2]: https://www.pcg-random.org/posts/a-quick-look-at-
| xoshiro256....
|
| [3]: https://en.wikipedia.org/wiki/Linear_congruential_generator
| WithinReason wrote:
| For Monte Carlo integration you want low discrepancy sequences
| or blue noise, not random numbers.
| steerablesafe wrote:
| That's easier said then done, when you integrate over a high
| dimensional (possibly infinite) space.
| wsc981 wrote:
| 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...
| ajuc wrote:
| 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
| olliej wrote:
| 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.
| dpwm wrote:
| > 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.
| nsajko wrote:
| > test suites like U01 Big Crush and PractRand should really
| help that situation out
|
| Reminder: the test suites are buggy and unmantained.
| sundarurfriend wrote:
| PractRand seems to have [1] last had a (pre-)release in
| 2019, and seems to have basic I/O problems that haven't
| been fixed [2]. There seem to be forks [3] and patches
| (mentioned in [2]) floating around, to fix such issues ad-
| hoc. But it seems unlikely that the rest of the code is
| free of bugs that need fixing too.
|
| And yet, it seems to be the tool that comes up in any
| discussion of tests of PRNG, and seems to be a fixture of
| the field. It's always a bit sad (and kind of weird) when
| core tools that a community depends upon are taken for
| granted and not given the support and attention they need.
|
| [1] https://sourceforge.net/projects/pracrand/files/ [2]
| https://www.johndcook.com/blog/2020/02/05/using-practrand-
| to... [3] https://github.com/MartyMacGyver/PractRand
| google234123 wrote:
| To be fair, you should expect to learn state of the art CS in
| a Computational Physics class. That's not the goal..
| JoachimS wrote:
| Also, one should compare the properties with the Mersenne
| Twister. The new PRNG proposals, algporitjms have better
| properties than the Mersenne Twister. Which one is best is a
| moving target. The point is that there are better to the
| Mersenne Twister alternatives today.
|
| It is a bit like people still choose to use MD5 or SHA-1.
| They are choosen because they are well known, easy to find
| info about and implementations to use.
| jart wrote:
| mt19937 is on the PractRand recommended list. https://githu
| b.com/MartyMacGyver/PractRand/blob/6ae26d8d4023... But it's
| last and his top recommendation is based on hc256
| https://github.com/peterferrie/hc256
| anewhnaccount2 wrote:
| 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.
| sundarurfriend wrote:
| 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.
| JoachimS wrote:
| 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
| jart wrote:
| 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]
| nsajko wrote:
| > 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.
| schoen wrote:
| (2019)
| unwind wrote:
| 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
| eternityforest wrote:
| Xorshift is one of my favorites.
|
| I always worry about default random numbers in the standard
| library, because there might still be that awful and badly
| performing(On embedded without multiply) LCG hiding.
| daneel_w wrote:
| https://github.com/stolendata/ranrot_bi
| slavik81 wrote:
| 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...
| jart wrote:
| 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; }
| slavik81 wrote:
| Thanks! It appears that Wikipedia has led me astray. The
| article in the top-level comment states, "if the generator
| is modified to return only the high 32 bits, then it passes
| BigCrush with zero failures."
|
| Following through to the document Wikipedia cites, I'm
| unable to find the original source for that claim. I
| suppose I'll look again after I have my coffee.
|
| Ah. Found it. From the PCG paper, "also of note, RanQ1[42]
| and XorShift* 64/32 are essentially the exact same
| generator, yet the former fails the test suite and the
| latter passes. The difference is that the former markets
| itself as a 64-bit generator and fails because its low-
| order bits are weak, whereas the latter only returns the
| top 32 bits." The claim of zero Big Crush failures also
| appears in Figure 2. http://www.pcg-random.org/pdf/hmc-
| cs-2014-0905.pdf
|
| I suppose the next question is if the claim is wrong or I
| screwed up the implementation.
| jart wrote:
| Here's pcg64 without seeding if anyone's curious.
| uint64_t pcg64(void) { static uint128_t s =
| ((uint128_t)10924776777348161541ull << 64 |
| 9024823012282619035ull); s = s *
| ((uint128_t)2549297995355413924ull << 64 |
| 4865540595714422341ull) + ((uint128_t)1 <<
| 64 | 15726070495360670683ull); uint64_t x =
| (uint64_t)(s >> 64) ^ (uint64_t)s; char e = s
| >> 122; return x >> e | x << (64 - e);
| }
|
| Not as fast and simple as lemur64 of course.
| bsder wrote:
| Can we get a reference on that lemire64 generator?
| jart wrote:
| It's Lemire's Lehmer Generator or LEMUR 64 for short
|
| https://arxiv.org/pdf/1805.10941.pdf
|
| https://archive.org/details/proceedings_of_a_second_sympo
| siu...
| enriquto wrote:
| where do these two constants come from? knuth?
| klaussilveira wrote:
| I'm assuming from here:
| https://lemire.me/blog/2019/06/06/nearly-divisionless-
| random...
| phkahler wrote:
| And if that's not random enough you should be able to fix
| it by applying a non-multiplicative function (shifts and
| booleans for example) to the output values. Feeding one
| random sequence into a different form of pseudo-random
| mapping has been shown to be highly effective even when the
| two functions themselves fail test of randomness.
|
| Edit: This is the concept I was thinking of: https://en.wik
| ipedia.org/wiki/Permuted_congruential_generato...
| somat wrote:
| if it needs to be the same, or repeatable, you don't actually
| want a random function, you want a hash function. might as well
| call it such.
| JoachimS wrote:
| No. The PRNG does not take an arbitrary large input and
| generates a digest/checksum.
|
| The PRNG accepts a single (short) input - a seed used to set
| the initial state. And can then generate a large number of
| values by updating the state.
|
| This is almost the opposite of a hash function.
|
| You could build the state update function using a hash
| function. But that does not make the PRNG a hash function.
| charcircuit wrote:
| >This is almost the opposite of a hash function.
|
| I would hesitate to say that. Look at hash functions built
| upon a sponge construction. One way to describe a sponge is
| that it absorbs a seed and then you can squeeze out random
| numbers. When building a hash function you absorb the input
| data and just squeeze out N bytes.
| JoachimS wrote:
| Yes, and no.
|
| The Sponge function in this context operates as a
| eXtended Output Function. It has an internal state and a
| state update function. But it does not in this context
| absorb a large input and output a digest.
|
| Sponges as a kernel/function that can be used to build
| hash functions, XOFs, PRNGs are interesting. That does
| not make the OP general statement that a PRNG should be
| called a hash function more correct. At least IMHO.
| charcircuit wrote:
| I am only pointing out the similarities between hash
| functions and PRNGs. I was not trying to disagree with
| your main point that a PRNG is a hash function. Though
| perhaps you could call them opposites in that usually you
| have a fixed input and infinite output for a PRNG and an
| infinite input and a fixed output for hash functions.
| [deleted]
| runxel wrote:
| 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.
| failrate wrote:
| For games, Squirrel Noise 3 is great.
| ur-whale wrote:
| 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-rand...
|
| [1] https://prng.di.unimi.it/
|
| [2] https://www.pcg-random.org/posts/on-vignas-pcg-critique.html
|
| [3] https://www.johndcook.com/blog/2021/04/29/reinventing-rng/
| 37ef_ced3 wrote:
| Use PCG: 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 } }
| }
| SamiPerttu wrote:
| 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 wrote:
| 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.
| kloch wrote:
| Multipliers for other widths: https://www.pcg-
| random.org/posts/does-it-beat-the-minimal-st...
| bhaak wrote:
| My goto RNG for a small, supposedly cryptographical secure RNG is
| ISAAC. https://en.wikipedia.org/wiki/ISAAC_(cipher) (There's a
| standalone C code implementation available at
| https://ccodearchive.net/info/isaac.html)
| eternityforest wrote:
| Is there anything wrong with ARC4 as a fast non cryptographic
| generator?
| maskros wrote:
| 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.
___________________________________________________________________
(page generated 2022-03-09 23:02 UTC)