3 ms·
A history about random number generation isn't complete without mentioning George Marsaglias work. He is responsible for multiply-with-carry, xorshift (the ori
by camel-cdr 1y ago
A history about random number generation isn't complete without mentioning George Marsaglias work.
He is responsible for multiply-with-carry, xorshift (the original version), KISS (a high quality generator predating the mersene twister) , the Ziggurat algorithm, diehard
Fun fact, one of the earliest methods for generating random mumbers, the middle square method, actually still passes all moderm statistical randomness test suites, if you hook up a weyl sequence to it: https://arxiv.org/abs/1704.00358 https://arxiv.org/abs/1704.00358
This, the middle square weyl sequence PRNG is my favoeite PRNG, because it's simple enough to implement from memory:
uint64_t x, weyl;
uint32_t msws(void) {
x = x * x + (weyl += CONSTANT);
return x = (x >> 32) | (x << 32);
}
You just take a number, square it, advace and add the weyl sequence to it amd finally swap the lower and upper bits, using the trucated result as the output.
The CONSTANT is pretty much arbitrary, it just needs to be odd and not too regular.
A good rule of thumb is to have no repeating or zero nibbles in each group of 4 bytes, e.g. 0xB5AD4ECEDA1CE2A9.
- LPisGood 1y agoThe Ziggurat algorithm is very important and widely used. There are some side channel vulnerabilities in differential privacy applications based on the details of this algorithm.
- avadodin 1y agoThat paper doesn't mention how many rounds it passed on the statistical tests, just that they tested 25000 seeds. They also don't definitely state a period but 2^64 with 192 or 384 bits of state is not that impressive. Furthermore, your version here uses only 128 bits so it is not clear to me that it is equivalent to the ones presented in the paper.
- camel-cdr 1y agomsws32() from the paper is the exact code I wrote above. The "s = 0xb5ad4eceda1ce2a9" is not part of the state, it's the CONSTANT. I've tested msws32 it passes TestU01s BigCrush and didn't fail in >=1 TB of PractRand (I stopped after that). A scaled down msws16 fails PractRand after 2 GB, a msws24() variant passes >=256 GB (I stopped after that). It's certainly not as good as more state of the art PRNGs like PCG, xoshiro, romu, sfc64, tylo64, but it is very simple and has quite high quality output, much better than any similarly simple to construct PRNG I know of.
- avadodin 1y agoSorry for misrepresenting it a bit. The renaming and the having the constant be a variable confused me when skimming for the parts that I was looking for. So, the state is 128 or 256 for the versions presented and 64 for msws16. I don't remember if running PractRand in word mode changes the way it reports results but either way failing at 2GB would mean it failed even before going through the whole Weyl sequence although the period itself isn't necessarily reduced. I'm not sure if the middle-square is acting as a decent non-linear scrambler on the poor adder state or if both combined manage to hold 30 bits worth of state. Swapping the adder with an lcg or lfsr on msws16 would provide an answer. PractRand has the benefit that we can look at where and how failure happens in these reduced versions so I think the criticism ultimately stands regarding the paper.