4 ms·
That depends on what you use the PRNG for. For cryptographic applications what you want is as previously noted just some arbitrary secure stream function (with
by dfox 7y ago
That depends on what you use the PRNG for.
For cryptographic applications what you want is as previously noted just some arbitrary secure stream function (with block cipher in OFB or CTR mode being particularly convenient way to obtain such cipher). Bear in mind that for cryptographic applications it is often important whether the state can be determined by observing the output and whether the state can be rewound back (which then necessitates choosing stream cipher that satisfies these requirements or using more complex construction. Most notably block ciphers in CTR/OFB mode does not satisfy this and ChaCha/Salsa also does not as it is essentially block cipher in CTR mode). Interesting modern construction would involve Keccak-style sponge functions, which are kind of universal cryptographic primitive that is usable as hash, MAC and PRNG/stream cipher all at once depending on mode of operation.
For monte-carlo simulations you want something that is reasonably fast and has large state space. Mersenne Twister is common choice, although XorShift is significantly faster and usually has state space that is large enought.
For randomized distributed simulations (read: lock-step realtime multiplayer games) you don't care about the output quality of the output that much and LCG tends to be sufficient, althought also in this case XorShift would be probably better as it has comparable performance and significantly better output quality.
All the mentioned algorithms are by definition deterministic and discounting implementation errors platform independent.
- tptacek 7y agoPlenty of CSRNGs are built from AES-CTR and ChaCha20. There's probably no good reason to prefer XorShift over a cryptographic random bit generator that you can seed directly.
- pcwalton 7y agoFor Monte Carlo simulations, CSRNGs are too slow. Xorshift is incredibly fast. You wouldn't want to use a CSRNG for path tracing rendering, for example; you're calling the RNG many times per ray and shooting dozens or hundreds of rays per pixel. We've dealt with this in Rust—people love to write Monte Carlo simulations as language benchmarks, and Rust used to get dinged for preferring CSRNGs.
- enriquto 7y agoIt's not only monte-carlo simulations. You may want to add a bit of random noise to a high-resolution video sequence, for example. It is impractical to do so with a slow PRNG.
- throw0101a 7y ago> For Monte Carlo simulations, CSRNGs are too slow. What kind of speed needs are we talking about? With AES-NI in most modern CPUs you can get many MB/s or GB/s. * https://calomel.org/aesni_ssl_performance.html https://calomel.org/aesni_ssl_performance.html (I don't do MC, so have no idea.)
- pcwalton 7y agoXorshift is like 10 cycles. AES-NI can take hundreds, depending on the number of rounds. In the case of brute force Monte Carlo path tracing, the speed of the RNG is important, because you have dozens or hundreds of rays per pixel, each with multiple bounces, and every bounce samples from your RNG. When your render times are 6 hours per frame to begin with, you really don't want to mess around.
- e12e 7y agoCycles pr what? Not bit, byte? If you generate a gig of random data (repeat when you read to the end) - is ares still too slow?
- wolf550e 7y agoAES-128-CTR on my laptop is 4.8GB/sec per core. I'm sure something producing random enough output for simulation can be built that is as fast as memcpy, but would anything real be affected by the difference?
- dragontamer 7y agohttps://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand Yes, it is possible but its difficult to do it right. I ran into at least 3 or 4 "roadblocks" while designing this algorithm, fortunately I managed to get through all of them. I've got an unrolled dual-stream going at 37.1 GBps on Threadripper 1950x (which has 2x AES pipelines). ~29.2 GBps for more "typical" usage (but still impractical). The issue with this is that random-bits of this speed are almost useless. A division or modulus operation takes 80-cycles (~20 nanoseconds) so as soon as you do "rand() % 6" (assuming you wanted a 6-sided dice roll), you've completely wreaked the bit-generator. A branch-misprediction is like 15-cycles, so that singular if-statement in your code that uses the RNG-number would be 5x slower than the generator itself. Its fast, but I don't know how practical it is. There's no practical way to use all of these random bits that I'm aware of. I did get a bit-compatible POWER9 version running by the way. So its portable across systems (at least, systems with an AES-encoder. ARM, Power9, and 2010-era x86.). Rasp. Pi doesn't have a CPU-AES engine however (its outside of the core), so Rasp. Pi can't use this methodology. -------------- If I were to actually push forward with this project more, I'd need to study on whole-program optimization, so that the (rarely used) XMM registers can be pragmatically used in a lot of code. The entirety of this RNG fits inside a single XMM register, so it'd benefit grossly from whole-program optimization. The XMM-data should also be fed into SIMD somehow, some kind of engine into ispc or OpenMP SIMD code. A bunch of raw-bits coming in through assembly commands is somewhat impractical, no matter how you look at it. Dan Lemire informed me of an amazing algorithm (that does work with AES XMM registers) that creates uniform random numbers out of a few multiply instructions. So I can get XMM-registers full of arbitrary integers with very low bias. (ex: numbers between 0 and 100) out of the bitstream. I also managed to convert the numbers into single-precision floats and double-precision floats between 0 and 1.0 uniformly. Still, this only really seems practical if you have SIMD-code that actually consumes all of these bits. Converting from XMM-registers into RAX registers has quite a bit of slowdown. I don't think the typical simulation code is actually limited by the speed of RNGs at all.