This are my personal requirements for picking a default small PRNG. It seems like we should have some set of requirements to apply to #52, beyond benchmarks.
@dhardy, @vks: What do you think?
A user should not need to worry about:
- speed and memory;
- not consuming to many results;
- independently initialized RNGs having a chance of producing similar streams;
- whether statistical biases it contains may or may not matter.
This translates to the following requirements, in RNG terms:
- for small chaotic RNGs:
- minimal cycle length: ~2^50
- minimal state size: 128 bits
- minimal seed size: 128 bits, unless with a proven initialization routine.
- for fixed-period RNGs: minimal period
- minimal period: ~2^128, or 2^64 with ~2^64 streams
- minimal seed size: 128 bits, unless with a proven initialization routine.
- passes PractRand and BigCrush
Other qualities to look for are:
- not being trivially predictable;
- reproducible results also on architectures with a different endianness;
- reasonably good theoretical basis;
- license that can be used in Rand.
Speed and memory
This seems like a clear requirement. What differentiates small fast RNGs from cryptographic ones, is that they are very fast and / or use much less memory. Between a dozen and up to twenty instructions seem to be the norm. Also a state of about 16 bytes is usually enough, and using more memory is wasting.
Not consuming to many results
What should be the minimum amount of results that can be consumed?
On today's hardware, a fast RNG can generate about 2^32 results in just 4 seconds. In most cases it is not reasonable to expect a process to do little else than generate random numbers, at least not without also requiring them to be cryptographically secure. With the exception of simulations maybe. 2^47 results take about a day to be generated. It seems anything that can generate a usable range close to 2^50 seems good enough.
- For small chaotic RNGs this means the minimal cycle length should be guaranteed to be greater than ~2^50. Not all designs have enough theory behind them to give guarantees about the minimal cycle length.
- For RNGs with a fixed period, not the entire period can be returned as results. As argued in the PCG paper chapter 3.1 that would mean all results appear exactly the same number of times, while because of the generalized birthday problem there should be variations.
- Also for the same problem the RNG needs more bits of state then the number of bits it outputs.
Independently initialized RNGs having a chance of producing similar streams
Many RNGs have only one period. When you pick some random initial state, there is a chance to end up in the same range as the results of another generator. Lets take a period of 2^128, and 2^48 as an upper limit for the expected amount of used results. It then takes about 2^32 random initializations to have a chance of 1 in a million to repeat part of an already used stream. See this comment, although some numbers are off by a factor 1000. So a period of 128 bits seems like a minimum requirement.
An alternative is RNGs with a small period and support for multiple streams, like PCG (when using LCG as a base generator) and SplitMix offer. A period of only 2^64 is just about enough to have a chance of 1 in 2000 for one new RNG to end up within the stream of one other RNG. If the RNG has 2^63 possible streams like PCG, 2^27 initializations are possible before the stream has a change of 1 in 1000 of being the same. Conclusion: support for ~2^64 streams is just enough to make a period of ~2^64 good enough for worry-free initialization.
All the above relies on the RNG taking a seed that has as many bits as the log2 of the period, 128. If the RNG can only take less bits, initialization may still be worry-free if the RNG has a proven method to map that seed to a state that can not be in the usable range of another seed. An example could be initializing PCG with a fixed state, and a random u64 for the stream. With just a u64 it is possible to guarantee 2^22 initializations and still having a change of only 1 in a million of ending up in the same stream. I am not aware of any RNG that offers this, besides it being quite pointless.
For small chaotic RNGs it is not really possible to talk about periods. The sizes calculated above for periods should map to state sizes if the RNG is perfect. So the state of chaotic RNGs should be at least 128 bits. I am not yet clear on what guarantees are available for this category of RNGs. Especially how cycles effect the birthday problem when initializing.
Whether statistical biases it contains may or may not matter
The standard way to evaluate the statistical quality of RNGs is through test suites, with PractRand and the BigCrush test from TestU01 being the current state of the art.
Many small chaotic RNGs pass without problems, and are quite fast.
For RNG's with a fixed period the recipe seems to be: take a fast, low quality RNG as a base generator, and apply a permutation function. Only the simple base generators like Xorshift, LCG or a Wehl sequence fail quickly.
Whether a statistical biases of an RNG matter, depends on how the generated values get used. For many uses a little bias of patterns does not matter. On the other hand, when it does matter but someone does not realize so, it is very hard to notice. The values appear random after all.
RNGs that have a clear bill from BigCrush and PractRand can be used without worry. At least for all situations where there is no adversary that tries to predict the RNG, use cryptographic RNGs in such a case.
Not being trivially predictable
On the PCG blog a post about trivial predictability is worth a read. For some algorithms cryptographically secure PRNG are unnecessary heavy, while some difficulty predicting the next results is enough to deter adversaries. One example is randomized quicksort. Not being trivially predictable can be seen as a plus, but not a requirement.
Reproducable results also on architectures with a different endianness
Even more then cryptographic RNGs, simple RNGs are used in many situations that need reproducible results. Then endianness should not be a worry.
Reasonably good theoretical basis
If the RNG has at least some theoretical background, requirements like the period size or cycle length can be proven. I would say we need those guarantees for the RNG do be made a default in Rand. While a published paper is nice, even comments in the source code with math that makes sense seem good enough for me.
License that can be used in Rand.
Our licenses are MIT and Apache 2.0. For RNGs that means they should have compatible licenses, like MIT or public domain. Anything higher like BSD or GPL would need permission from the author.
This are my personal requirements for picking a default small PRNG. It seems like we should have some set of requirements to apply to #52, beyond benchmarks.
@dhardy, @vks: What do you think?
A user should not need to worry about:
This translates to the following requirements, in RNG terms:
Other qualities to look for are:
Speed and memory
This seems like a clear requirement. What differentiates small fast RNGs from cryptographic ones, is that they are very fast and / or use much less memory. Between a dozen and up to twenty instructions seem to be the norm. Also a state of about 16 bytes is usually enough, and using more memory is wasting.
Not consuming to many results
What should be the minimum amount of results that can be consumed?
On today's hardware, a fast RNG can generate about 2^32 results in just 4 seconds. In most cases it is not reasonable to expect a process to do little else than generate random numbers, at least not without also requiring them to be cryptographically secure. With the exception of simulations maybe. 2^47 results take about a day to be generated. It seems anything that can generate a usable range close to 2^50 seems good enough.
Independently initialized RNGs having a chance of producing similar streams
Many RNGs have only one period. When you pick some random initial state, there is a chance to end up in the same range as the results of another generator. Lets take a period of 2^128, and 2^48 as an upper limit for the expected amount of used results. It then takes about 2^32 random initializations to have a chance of 1 in a million to repeat part of an already used stream. See this comment, although some numbers are off by a factor 1000. So a period of 128 bits seems like a minimum requirement.
An alternative is RNGs with a small period and support for multiple streams, like PCG (when using LCG as a base generator) and SplitMix offer. A period of only 2^64 is just about enough to have a chance of 1 in 2000 for one new RNG to end up within the stream of one other RNG. If the RNG has 2^63 possible streams like PCG, 2^27 initializations are possible before the stream has a change of 1 in 1000 of being the same. Conclusion: support for ~2^64 streams is just enough to make a period of ~2^64 good enough for worry-free initialization.
All the above relies on the RNG taking a seed that has as many bits as the log2 of the period, 128. If the RNG can only take less bits, initialization may still be worry-free if the RNG has a proven method to map that seed to a state that can not be in the usable range of another seed. An example could be initializing PCG with a fixed state, and a random u64 for the stream. With just a u64 it is possible to guarantee 2^22 initializations and still having a change of only 1 in a million of ending up in the same stream. I am not aware of any RNG that offers this, besides it being quite pointless.
For small chaotic RNGs it is not really possible to talk about periods. The sizes calculated above for periods should map to state sizes if the RNG is perfect. So the state of chaotic RNGs should be at least 128 bits. I am not yet clear on what guarantees are available for this category of RNGs. Especially how cycles effect the birthday problem when initializing.
Whether statistical biases it contains may or may not matter
The standard way to evaluate the statistical quality of RNGs is through test suites, with PractRand and the BigCrush test from TestU01 being the current state of the art.
Many small chaotic RNGs pass without problems, and are quite fast.
For RNG's with a fixed period the recipe seems to be: take a fast, low quality RNG as a base generator, and apply a permutation function. Only the simple base generators like Xorshift, LCG or a Wehl sequence fail quickly.
Whether a statistical biases of an RNG matter, depends on how the generated values get used. For many uses a little bias of patterns does not matter. On the other hand, when it does matter but someone does not realize so, it is very hard to notice. The values appear random after all.
RNGs that have a clear bill from BigCrush and PractRand can be used without worry. At least for all situations where there is no adversary that tries to predict the RNG, use cryptographic RNGs in such a case.
Not being trivially predictable
On the PCG blog a post about trivial predictability is worth a read. For some algorithms cryptographically secure PRNG are unnecessary heavy, while some difficulty predicting the next results is enough to deter adversaries. One example is randomized quicksort. Not being trivially predictable can be seen as a plus, but not a requirement.
Reproducable results also on architectures with a different endianness
Even more then cryptographic RNGs, simple RNGs are used in many situations that need reproducible results. Then endianness should not be a worry.
Reasonably good theoretical basis
If the RNG has at least some theoretical background, requirements like the period size or cycle length can be proven. I would say we need those guarantees for the RNG do be made a default in Rand. While a published paper is nice, even comments in the source code with math that makes sense seem good enough for me.
License that can be used in Rand.
Our licenses are MIT and Apache 2.0. For RNGs that means they should have compatible licenses, like MIT or public domain. Anything higher like BSD or GPL would need permission from the author.