3 ms·
> Marsaglia is most famous for the diehard suite of RNG tests, so he knows his stuff. Fame is relative, for my part Marsaglia is most famous for The Ziggurat M
by defrost 3y ago
> Marsaglia is most famous for the diehard suite of RNG tests, so he knows his stuff.
Fame is relative, for my part Marsaglia is most famous for The Ziggurat Method for Generating Random Variables and numerous other PRNG delights .. the testsuite comes way down the list.
* https://www.jstatsoft.org/article/view/v005i08 https://www.jstatsoft.org/article/view/v005i08
* https://en.wikipedia.org/wiki/Ziggurat_algorithm https://en.wikipedia.org/wiki/Ziggurat_algorithm
Once upon a time I made a branchless generator of large blocks of random points on S2 (the surface of a unit sphere) for an astrophysics sim, it was a fun exercise
- camel-cdr 3y agoMarsaglia was also behind the MWC, SWB, xorshift and KISS PRNGs. Edit: removed a bit because I confused the polar with the ratio method
- gcr 3y agoOooo post it post it! Was it “generate a multivariate Gaussian distribution and then divide each point by its norm”?
- whyever 3y agoThat works for N dimensions, but for N=2 or 3 there are faster methods: For N=3, there is a method by Marsaglia: https://doi.org/10.1214/aoms/1177692644 https://doi.org/10.1214/aoms/1177692644 For N=2, there is a method by von Neumann: https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf All of these use rejection sampling, so they are not branchless.
- defrost 3y agoI'm staying vague for the sake of anybody noodling away at this, it's fun but not deep. It's a twofer, first there's a choice of algo to choose an unbiased unit vector (or point on sphere), then there's implementing it on a particular vector RISC architecture to avoid stutters from branch prediction gone awry - constant steady performance being desirable (in this and all the other parts of the larger program). "Branchless" decisions are possible; Compute D = decision = 0 or 1 as result (no branch, just arithmetic) Compute R = result = DA + (!D)B = result A OR result B depending on D with no jumps or decision penalties. It's an implementation hack and one dependant on architecture, some chips are fancy enough to pursue two branch in parallel and using the correct choice without have to suffer a time costly pipeline flush for path better not taken. DSP architectures have long pipes and consistent timing, complex arithmetic statements (once setup) take a single clock cycle; interate result vector = modulo scalar vector1 * input vector1 + modulo scaler vector2 * input vector2 type FFT "atomics" are a single clock .. you can push inputs once per clock and extract ouputs once per clock (with a delay of time to fill pipe).
- seanhunter 3y agoThe Ziggurat algorithm is fantastic, and is way faster than the conventional methods (like Box-Muller) for generating normally-distributed variants from a uniform pseudorandom source. I implemented it a while back and it was one of those things that was a great pleasure to do. I have also used the diehard suite a while back to convince myself that a random mixer thing I came up with was suitably random. Basically I wrote a thing to read from various sources of entropy, bleach them a bit and then mix them all together in a way that was extremely chaotic before feeding them into the kernel entropy pool. This was because it used to be a problem (back circa 1998 or so) that if you had headless servers serving a lot of ssl sessions they would run out of entropy and block from time to time. At the time, diehard had been implemented in fortran and then compiled to C using a gnu fortran transpiler so it was completely impossible to understand what each of the tests were actually doing. On the topic of tfa, one of the most practical “RNG in your brain” techniques I heard of was suggested by the poker player Dan Harrington in his books, which is for sampling at random with some probability between some discrete choices. So say you have something you want to do at random 1/3rd of the time and the other 2/3rds of the time you’re going to do another thing[1], the way he says to do this is base it on your watch face. So you decide [2] that if the second hand of your watch is between 1 and 20 then you will do thing A and if it’s between 20 and 60 you’ll do thing B. Then you look and you do whatever thing. The good part about this is clearly even if people know you’re doing it they can’t exploit it because they don’t know the set of choices you’ve given yourself, what the boundaries are where you choose between strategies etc. It doesn’t work if you need to sample rapidly but in the context he gave it (tournament poker) you would have a random amount of time more than a minute between decisions anyway so its fine in that context. [1] From a game theory point of view, it can be shown that in games with randomness and hidden information like poker, the optimal strategy is a Nash equilibrium in mixed strategies which means you need to sample a probability distribution to choose your actions in this way. [2] before looking. This is important.
- bno1 3y agoIsn't inverse transform sampling even faster than ziggurat? Most languages have an approximate erf^-1 implementation, everything is straight forward from there. I needed to generate random numbers from a truncated normal distribution and found inverse transform sampling easier to implement than trying to understand and adapt the ziggurat algorithm. A nice blog on this: https://stackedboxes.org/2017/05/01/acklams-normal-quantile-function/ https://stackedboxes.org/2017/05/01/acklams-normal-quantile-...