7 ms·

So you need a large stream of random numbers to seed your random number generator? Seems like a bizarre chicken and egg problem... If I had a source for large q

So you need a large stream of random numbers to seed your random number generator? Seems like a bizarre chicken and egg problem... If I had a source for large quantities of random numbers, why would I even need the second random number generator?

ChrisSD 6y ago
If you have a stream of random numbers it can be expanded it to a gigantic stream of random numbers. A good pseudo-random number generator can give you a ZiB of random data from a 128bit or 256bit number.
gnulinux 6y ago
Because one of them can be slower than the other? Let's assume random.org gives true quantum randomness. Let's assume it's acceptable for my program to make an api call to random.org to get some random numbers. That doesn't mean I want to go to internet every time I need a random number. I'd much rather get something like 256 random bits from random.org and create the rest with Mersenne Twister which has an insanely large period.
kevin_thibedeau 6y ago
You might want the second generator to be deterministic. Consider a fuzzing testcase that generates randomized inputs. When a failure is hit the seed is recorded and someone can reproduce it for debugging.
_wldu 6y ago
On Unix systems, you can use /dev/urandom to do this.
loeg 6y ago
The use case here is basically simulations, where cryptographic RNG quality is not needed but a lot of pseudo-random numbers are. Even the fastest CSPRNGs (e.g., bulk Chacha20 keystream) are much much slower than good non-cryptographic PRNGs such as PCG or a 128-bit LCG. (Note that Mersenne Twister is an awful PRNG despite its enduring popularity.) If you play around with Chacha rounds, the minimal number of rounds necessary to provide "good", but non-cryptographic, results is 4[1], and Chacha4 (with dolbeau AVX acceleration) is still substantially slower than PCG or 128-bit LCG with 4 rounds (something like 30-50% slower than pcg64_fast, as I measure it). (Full-round AES w/ AES-NI is about 30% slower than Chacha4 w/ AVX on my hardware, but I did not test a reduced-round AES with AES-NI acceleration; that might be interesting and competitive.) [1]: https://crypto.stackexchange.com/a/57672/51869 https://crypto.stackexchange.com/a/57672/51869
- bsder 6y ago
  > Note that Mersenne Twister is an awful PRNG despite its enduring popularity. References? I'm not being snide. I need to save those for future arguments.
  - loeg 6y ago
    "Awful" was maybe hyperbole; mea culpa. I should have said: it's not great compared to other options available today. It shouldn't be your first choice anywhere. In short: * It has a huge state (~2kB per instance); compare 128-bit LCG at 128 bits or even a cryptographic PRF like Chacha at 64 bytes. This is a factor of 128x larger overhead (or 32x bigger than Chacha!) and hurts, say, L1 cache of more important data, especially with multiple instances. * It has mediocre statistical properties (fails TestU01 BigCrush, fails PractRand). (128-bit LCG passes both.) * And it has mediocre performance. (In the PCG benchmark, pg. 35: ~2.17 ns/op vs 128/64 LCG at ~1.05 ns/op. In that diagram, labelled "MCG" — but MCGs are just a subset of LCGs.) Ref: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf See also: https://en.wikipedia.org/wiki/Mersenne_Twister#Disadvantages https://en.wikipedia.org/wiki/Mersenne_Twister#Disadvantages
    - VHRanger 6y ago
      PCG is incredibly simple as well. I made a 100 line with ~10sloc (most of it is comments). It too has a 128bit state and has a hard to beat speed for such a naive implementation https://github.com/VHRanger/pcg.h https://github.com/VHRanger/pcg.h
      - loeg 6y ago
        > PCG is incredibly simple as well Yes and no. There are a lot of different functions in the PCG umbrella and that adds some mental complexity IMO. Some of the functions are very simple, including the 128-bit LCG I am referring to above ("pcg64_fast", IIRC). It is almost trivial; basically a single LoC to generate the next state and a single LoC to produce the output from that state: https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L2408 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L2225-L2228 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L618 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L243 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... Or condensed from several composed inline functions: uint64_t my_pcg64_fast(uint128_t *state) { // Multiplier: (2549297995355413924ULL << 64) + 4865540595714422341ULL *state *= PCG_DEFAULT_MULTIPLIER_128; // Output is XOR-condensed state rotated right by the high 6 bits of state. return pcg_rotr_64(((uint64_t)(*state >> 64u)) ^ (uint64_t)*state, *state >> 122u); }
HelloNurse 6y ago
Apart from performance reasons, a truly random seed ensures that there is no bias and the computation can be easily rerun with a different seed, but it can also be recorded and used later to regenerate the same vastly larger sequence of pseudorandom numbers (useful, for example, for regression testing of the main computation code).

ChrisSD 6y ago

If you have a stream of random numbers it can be expanded it to a gigantic stream of random numbers. A good pseudo-random number generator can give you a ZiB of random data from a 128bit or 256bit number.

gnulinux 6y ago

Because one of them can be slower than the other? Let's assume random.org gives true quantum randomness. Let's assume it's acceptable for my program to make an api call to random.org to get some random numbers. That doesn't mean I want to go to internet every time I need a random number. I'd much rather get something like 256 random bits from random.org and create the rest with Mersenne Twister which has an insanely large period.

kevin_thibedeau 6y ago

You might want the second generator to be deterministic. Consider a fuzzing testcase that generates randomized inputs. When a failure is hit the seed is recorded and someone can reproduce it for debugging.

_wldu 6y ago

On Unix systems, you can use /dev/urandom to do this.

loeg 6y ago

The use case here is basically simulations, where cryptographic RNG quality is not needed but a lot of pseudo-random numbers are. Even the fastest CSPRNGs (e.g., bulk Chacha20 keystream) are much much slower than good non-cryptographic PRNGs such as PCG or a 128-bit LCG. (Note that Mersenne Twister is an awful PRNG despite its enduring popularity.) If you play around with Chacha rounds, the minimal number of rounds necessary to provide "good", but non-cryptographic, results is 4[1], and Chacha4 (with dolbeau AVX acceleration) is still substantially slower than PCG or 128-bit LCG with 4 rounds (something like 30-50% slower than pcg64_fast, as I measure it). (Full-round AES w/ AES-NI is about 30% slower than Chacha4 w/ AVX on my hardware, but I did not test a reduced-round AES with AES-NI acceleration; that might be interesting and competitive.) [1]: https://crypto.stackexchange.com/a/57672/51869 https://crypto.stackexchange.com/a/57672/51869

bsder 6y ago
> Note that Mersenne Twister is an awful PRNG despite its enduring popularity. References? I'm not being snide. I need to save those for future arguments.
- loeg 6y ago
  "Awful" was maybe hyperbole; mea culpa. I should have said: it's not great compared to other options available today. It shouldn't be your first choice anywhere. In short: * It has a huge state (~2kB per instance); compare 128-bit LCG at 128 bits or even a cryptographic PRF like Chacha at 64 bytes. This is a factor of 128x larger overhead (or 32x bigger than Chacha!) and hurts, say, L1 cache of more important data, especially with multiple instances. * It has mediocre statistical properties (fails TestU01 BigCrush, fails PractRand). (128-bit LCG passes both.) * And it has mediocre performance. (In the PCG benchmark, pg. 35: ~2.17 ns/op vs 128/64 LCG at ~1.05 ns/op. In that diagram, labelled "MCG" — but MCGs are just a subset of LCGs.) Ref: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf See also: https://en.wikipedia.org/wiki/Mersenne_Twister#Disadvantages https://en.wikipedia.org/wiki/Mersenne_Twister#Disadvantages
  - VHRanger 6y ago
    PCG is incredibly simple as well. I made a 100 line with ~10sloc (most of it is comments). It too has a 128bit state and has a hard to beat speed for such a naive implementation https://github.com/VHRanger/pcg.h https://github.com/VHRanger/pcg.h
    - loeg 6y ago
      > PCG is incredibly simple as well Yes and no. There are a lot of different functions in the PCG umbrella and that adds some mental complexity IMO. Some of the functions are very simple, including the 128-bit LCG I am referring to above ("pcg64_fast", IIRC). It is almost trivial; basically a single LoC to generate the next state and a single LoC to produce the output from that state: https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L2408 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L2225-L2228 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L618 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L243 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... Or condensed from several composed inline functions: uint64_t my_pcg64_fast(uint128_t *state) { // Multiplier: (2549297995355413924ULL << 64) + 4865540595714422341ULL *state *= PCG_DEFAULT_MULTIPLIER_128; // Output is XOR-condensed state rotated right by the high 6 bits of state. return pcg_rotr_64(((uint64_t)(*state >> 64u)) ^ (uint64_t)*state, *state >> 122u); }

HelloNurse 6y ago

Apart from performance reasons, a truly random seed ensures that there is no bias and the computation can be easily rerun with a different seed, but it can also be recorded and used later to regenerate the same vastly larger sequence of pseudorandom numbers (useful, for example, for regression testing of the main computation code).