Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

arxiv.org

Post reply on HN
Print view View original

11–20 of 56 posts

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

#11

Post by somat »

unwind wrote: post #7

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…

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.

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

#12

Post by JoachimS »

somat wrote: post #11
unwind wrote: post #7

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…

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.

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.

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

#13

Post by JoachimS »

dpwm wrote: post #8
magicalhippo wrote: post #3

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, 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…

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.

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

#14

Post by JoachimS »

anewhnaccount2 wrote: post #6
magicalhippo wrote: post #3

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, 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.

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

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

#15

Post by WithinReason »

magicalhippo wrote: post #3

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, f…

For Monte Carlo integration you want low discrepancy sequences or blue noise, not random numbers.

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

#16

Post by charcircuit »

JoachimS wrote: post #12
somat wrote: post #11

Earlier quoted context omitted.

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.

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.

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

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

#17

Post by ajuc »

wsc981 wrote: post #4
magicalhippo wrote: post #3

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, 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...

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

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

#18

Post by JoachimS »

charcircuit wrote: post #16
JoachimS wrote: post #12

Earlier quoted context omitted.

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.

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

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.

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

#19

Post by [deleted] »

somat wrote: post #11
unwind wrote: post #7

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…

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.

[deleted]

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

#20

Post by charcircuit »

JoachimS wrote: post #18
charcircuit wrote: post #16

Earlier quoted context omitted.

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

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.…

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.
Post reply on HN