Pseudo random number generators 2
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 2n. 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 (xi = xi-55 + xi-119 + xi-179 + xi-256 mod 2n) 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 fi = gi + hi also have the flaw that fi – fi+p = hi – hi+p when p is the period of g. This also means that fi – fi+p – (fi+q – fi+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 (xi = xi-55 * xi-24 mod 2n) 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’ve always thought that the MT was the best in terms of randomness and speed (and I’ve long been wondering why rand() is implemented using a fairly poor method).
I’m not interested in cryptography, but simulations. Any special recommendation?
Comment by Cesar — 2008-11-30 @ 05:39
> Best but slow PRNGs
>
> “Anything†based on AES, SHA-1, MD5, …
So hash function is the best random number generator?
Comment by Kostya — 2008-11-30 @ 07:12
> I’ve always thought that the MT was the best in terms of randomness and speed
It surely isnt, it failed several tests of testu01 and is, as said purely linear (in GF(2)) that is its output bits are just xor of some previous bits. Also in my own tests (with code from libavutil) MT was alot slower than simpler generators like LFGs/LCGs.
> (and I’ve long been wondering why rand() is implemented using a fairly poor method).
Probably because thouse writing C libs cant be experts in everything. But then these poor methods are often good enough …
> I’m not interested in cryptography, but simulations. Any special recommendation?
I realize that ive filed this just under cryptanalysis, this was indeed just lazyness for not creating a better category :)
For simulations, it depends on how many numbers you need and how important the correctness of the result of the simultion is. I mean if its for a screensafer or game then the simplest and fastest generator might very well be the best choice, if its for testing some scientific theory id probably run the simulations with at least 2 different (good) PRNGs and check that the results are approximately the same. If they are not you can then publish a paper about a practically relevant flaw in a PRNG …
Also to pick actual PRNGs, i guess my 2 posts and the testu01 paper should give enough suggestions. The actual decission depends strongly on what percentage of cpu time is taken by building random numbers and how good the numbers need to be …
Comment by Michael — 2008-11-30 @ 13:23
> > Best but slow PRNGs
> >
> > “Anything†based on AES, SHA-1, MD5, …
> So hash function is the best random number generator?
IMHO, if its (lack of) speed is ok then yes.
The reason why, is simply that these cryptographic functions have been heavily tested to be free of any practical way to predict the cleartext/password from their output.
Thus when a AES(i++ (cleartext), seed (password)) would be found to be different from random data in some test or simulation, that effectively would leak information about the cleartext, that is it being i++ instead of truely random. This thus would be a weakness in AES.
Comment by Michael — 2008-11-30 @ 13:35
> AES(i++ (cleartext), seed (password))
Correct, but now you have the problem of selecting a password/seed.
That Mersene twister is not cryptographically secure is not a secret. It is warned that you should run its output through a hash or crypto function (for hash this kinda makes sense, for crypto it’s probably better to do what you said since it’s faster). Mersene’s strength is its very long period (there’s an implementation with period 2^19937-1), however I don’t know how the others compare or if it’s Mersene-specific.
Comment by - — 2008-11-30 @ 17:34
> > AES(i++ (cleartext), seed (password))
> Correct, but now you have the problem of selecting a password/seed.
For crypto yes but not for other puproses like some scientific simulation, for that seed=0, seed++ or time() should be fine.
> That Mersene twister is not cryptographically secure is not a secret. It is warned that you
> should run its output through a hash or crypto function (for hash this kinda makes sense, for
> crypto it’s probably better to do what you said since it’s faster).
You would also have to find a new way to initialize the twister, the currently standard 32bit seed + LCG is very bruteforceable.
Besides what point is there in using MT at all when you use a secure hash or crypto function anyway …
> Mersene’s strength is its
> very long period (there’s an implementation with period 2^19937-1), however I don’t know how
> the others compare or if it’s Mersene-specific.
looking at testu01, DX-1597-2-7 has a period of 2^49507 and brent-xor-4096s has one of 2^131072, both are faster than MT19937 according to testu01 and both also pass all tests of testu01 while MT19937 does not.
Beside this, IMHO what difference does it make if you have a 2^19937 or a 2^200 period PRNG? you are not going to be able to take enough samples to notice the difference anyway …
Comment by Michael — 2008-11-30 @ 19:29
Michael, regarding libc rand(), the reason it’s implemented with a poor algorithm is simple: traditionally it was always implemented with poor algorithms, and the relevant standards make no requirement that it use a good PRNG (in fact the ISO C standard has a lame sample implementation), so no sane program needing a good PRNG would depend on rand() for its random numbers. Therefore from an implementor’s standpoint, it makes sense to just have a fast-but-crappy algorithm for simple exercises where PRNG quality is irrelevant, and assume that all programs with specific requirements on their PRNG will include a PRNG appropriate for the specific application in question.
That was my reasoning in implementing my own libc. I actually just used the ISO C sample implementation because it’s a one-liner. :)
Comment by Rich — 2008-12-12 @ 03:50
Remember about ISAAC by Jenkins. It is derived from AES, is very good. And is probably even secure. And what is most interesting it is ultra fast.
Comment by Witek — 2010-01-24 @ 00:44
And about non power of 2 generators, ther is quite easy trick for modulo m=2^k-1 by Marsaglia. It is rearly know but can make algorithm something like 2.5 times faster.
Comment by Witek — 2010-01-24 @ 00:47
The following might make a serious candidate in the “good and fast” category, if cryptological security is not an issue. It is short, fast, with a IMHO beautiful underlying theory, and it passes SmallCrush.
/* MWC on 16 32-bit integers with a 21-bit multiplier. The temporary
result with the multiplication never exceeds 53 bits, for implementation
in javascript Numbers (“double-precision 64-bit binary format IEEE 754”).
The multiplier, a = 1994205, is the highest 21-bit integer such that
p = a * 2 ^ (32 * 16) – 1 is a safe prime. The period is (p – 1) / 2
(the corresponding Germain prime), close to 2 ^ 532 */
#include
static uint32_t s[16] = { // anything goes, except all zeros
// the values here come from Marsaglia’s CD
0x7cc41d3fUL, 0x16b21330UL, 0x1c01fd2dUL, 0x5f107963UL,
0xc907f813UL, 0xf62527cdUL, 0x25e7af78UL, 0x6a0517c0UL,
0x1ce4593cUL, 0x86af293aUL, 0xcee31109UL, 0x429bf39bUL,
0xd0fc2b62UL, 0x0eb12482UL, 0xd677a3d8UL, 0x09313e9fUL
};
static uint32_t c = 0;
static uint8_t k = 0;
static inline uint32_t mwc16(void) {
uint64_t t;
k = (k + 1) & 15;
t = 1994205 * (uint64_t) s[k] + c;
c = t >> 32;
return s[k] = t;
}
Comment by Johannes Baagoe — 2010-04-11 @ 18:42
I mostly agree with the original post.
Fastest PRNGs: If you really want all-out speed on a per-call basis and don’t care too much about speed on a per-bit basis, you can get a little extra speed by returning smaller numbers of bits out of the result. This is only efficient if the RNG in question naturally buffers up several results at a time, like a 2-tap LFIB or GFSR. Both of which are rather low quality, but you can insert a barrel shift to the LFIB operation to dramatically improve quality without really hurting speed.
Good and fast PRNGs: There are numerous good and fast PRNGs, but the one I usually prefer is Robert Jenkins small fast prng – it easily passes BigCrush and all similar tests, is significantly faster than MT19937, and it consists of only 4 32 bit integers using addition, xor, and barrel shifts. See it at http://www.burtleburtle.net/bob/rand/smallprng.html
Comments on preceding comments:
10. Johannes Baagoe: Preliminary results suggests it passes statistical tests with ease, but it’s not particularly fast as written. On my computer it is running slower than MT19937.
8. Witek: I am a fan of the ISAAC algorithm, but it has no relation to AES. Perhaps you are thinking of RC4, which it is distantly related to?
7. Rich: I agree that that is why things are that way, but I think that things should NOT be that way. There are RNGs as fast or faster than LCGs on either a per-call basis or a per-bit basis that produce substantially better results. This is especially true on low-end and embedded CPUs, where multiplication is often slow.
Comment by orz — 2011-04-02 @ 10:43
Watch this algorithm and let me know.
http://www.number.com.pt/index.html
Thanks.
Comment by Ribeiro Alvo — 2011-04-10 @ 16:59
Michael, have you seen the erratum of the paper? I quote:
‘The period of generator Brent-xor4096s in Table I should be 2^4128 and not 2^131072.’
Comment by Anonymous — 2016-02-26 @ 12:43