Lair Of The Multimedia Guru

After the little bit of analysing PRNGs in the last blog post, which PRNGs exactly seem good?

Fastest PRNGs

If one either needs a very fast PRNG or one has some means to easily test that the output is good enough (like looking to see if a noise filter produces no vissible aritifacts) then folllowing could be considered.
Linear congruential generators, Additative lagged fibbonacci generators or even just an array of random numbers that gets used repeatedly, …
Each of these has its serious flaws, LCGs have very poorly performing LSBs, that is the lowest n bits never have a period larger than 2ⁿ. ALFGs contain number triplets (the ones spaced like the taps used in the PRNG) that when used as coordinates in a cube would all fall in a single plane. Still these generators are often good enough, and have been used for a long time and are widespread, that is all C libs ive seen use either of them for rand() for examle.

Good and fast PRNGs

If one wants a generator free of big flaws and that is still reasonably fast then the number of choices goes down, first there is
4 tap additative LFG (x_i = x_i-55 + x_i-119 + x_i-179 + x_i-256 mod 2ⁿ) this one passed all of testu01 but has a obvious linear dependancy between its values.
Combined generators, these generators combine the output of several simple generators and generally pass all tests, many of them though are slow like CLCG4 which combines 4 LCGs, combined generators like f_i = g_i + h_i also have the flaw that f_i – f_i+p = h_i – h_i+p when p is the period of g. This also means that f_i – f_i+p – (f_i+q – f_i+p+q) = 0 when p and q are the periods of h and g. Thus all combined generators which are made of constituent generators with “bruteforceable periods” are cryptographically likely very weak. A combined generator that is reasonable fast is KISS99.
Multiplicative lagged fibonacci generators, like for example (x_i = x_i-55 * x_i-24 mod 2ⁿ) these generators also tend to pass all tests as long as only the most significant bits are used, that is for example the top 32 bit of a 64 bit generator. The least significant bit of such a generator is always 1, its next bit behaves like a LFSR identically to the least significant of an additative or xor based LFG. One trick to get rid of the least significant bit without ending up with just 31 or 63 bits is to use 2*a*b+a+b instead of a*b, this works because a and b are (have to be) odd in a normal MLFG and (2*A+1)(2*B+1) = 4AB + 2A + 2B + 1

Best but slow PRNGs

“Anything” based on AES, SHA-1, MD5, …

Bad PRNGs

These are PRNGs that are both slower and worse in terms of their output than others, examples are
Mersene twister, becuase its output is purely based on the XOR of previous bits thus being not nearly as good as some pretend it to be while it also isnt nearly as fast compared to other properly implemented PRNGs.
Combined generators with lots of modulo by non power of 2, these are slow …
Weak generators from which many output values are thrown away, again these are slow …

I guess most developers have once or more than once run into the question of, “which PRNG should one use”. The awnser, or more precissely my awnser to this, would be it really depends on for what one plans to use it.
There is no perfect generator, there are fast ones, and there are good ones, but the best arent the fastest. One has to choose depending on ones needs

• If one wants to generate white noise for a human listener then the best generator simply is the fastest that produces perfectly sounding white noise, it really doesnt matter if it has some statistical defects or not.
• If one wants to use the random numbers for cryptographic purposes, a perfect generator that has been extensively tested and no flaws found is needed.
• If one wants to test a scientific theory by simulation, one needs a generator that doesnt cause a wrong result from the simulation, but as the correct result isnt known, one cant easily pick based on this criteria. Thus one has little alternative to picking a generator that has few statistical defects and is fast enough for the amount of numbers needed. Or better even run the simulation 2-3 times with very different generators

So which generators are there and what defects do they have? This actually is rather easy to awnser, or then maybe not ;) well, there is George Marsaglias Diehard and Pierre L’Ecuyers
TestU01 both contain code to test PRNGs, later also contains a paper describing the results of these tests for most recent and popular PRNGs.

In an ideal world one would just have to look at the TestU01 paper And pick a generator that has the amount of defects and speed one wants. At least thats what i thought before testing a few generators myself, more precissely i took a few of the generators that passed all tests in TestU01 and run 2 (to me obvious) tests against them

1. Use a gaussian like algorithm to find out if any bits in the output are just a linear (mod 2) combination of previous output bits
2. Use a gaussian like algorithm to find out if any scalars in the output are just a linear (mod maxoutput+1) combination of previous output scalars
3. Use a gaussian like algorithm to find out if any bits (only considering the least significant of each scalar) in the output are just a linear (mod 2) combination of previous such output bits

The first 2 of these tests in the way i implemented them only consider outputs surrounding a scalar with 20 zero LSBs, though as far as i tested it this 20bit trick only made a difference for the additative LFG with only the 32MSB used, but i did not test all without this 20bit check

Failing either of these tests makes the PRNG at least unsuitable for linear algebra under the same modulo, so its certainly a statistical defect. All linear congruential generators have to fail at least the test that works in their own modulo, after all they are linear, but actually all i tested failed both tests. Lagged fibonacci generators based on addition or xor similarly must fail and do. All multiplicative Lagged fibonacci generators fail as well due to linear dependancies in their lower bits. All linear feedback shift register based generators like the mersene twister very obviously have to fail too, i did not test any of them though as none passed TestU01.

The actual generators that passed TestU01 and failed mine where:
superduper64, Marsa-lfib4, DX-47-3, MRGk5_93, Lfib(2^64,55,24,*), brent-xor4096s

The actual generators that passed TestU01 and passed mine where:
brent-xor4096s, MRG31k3p, CombMRG96, ran2, CLCG4, KISS99

Note1, there are more generators that passed TestU01 but i did not test them

Note2, The first 2 tests where only searching for linear dependancies within 512 consecutive scalars, that is 32kbit for a 64bit PRNG, the 3rd test was considering 32kbit of LSBs

In addition to that, limiting the output to just 32MSB of 64 made the multiplicative LFG 2^64,55,24,* pass mine while the same trick with a additative one was not helping, KISS99 also passed when SHR3 or CONG was droped but not when both or MWC alone was droped

No source code this time though because i randomly copied PRNGs from various places, but if there is interrest i could throw all but my own code out and post that

To be continued when iam less tired … ;)