4 ms·

PRNGs and CPUs are stupidly fast these days. I'm not really convinced that the problem is abundancy of pseudo-random bits, not at least for simulations. A well

PRNGs and CPUs are stupidly fast these days. I'm not really convinced that the problem is abundancy of pseudo-random bits, not at least for simulations. A well written PRNG should execute at the same speed as a memset in fact (at least, for the creation of PRNG-bits before processing) Massaging the bits into proper form: using modulus operator, requires like 80-cycles (aka: a division) on 5-year old CPUs and maybe 20-cycles on a very modern core (with the past 3 years, as Intel seems to have put a lot of work optimizing division). So the bulk of the time is on this massaging process actually. -------- Even if the bulk of the CPU time is spent converting the uniformly random bits into usable integers (division / modulus is really slow!!), or usable floats / normal distributions or whatever... I still expect the typical core to handle 100-million pseudo random numbers per second... __per core__. Seeding your PRNG with a true random seed every now and then will ensure large-scale randomness. I think cryptographers might need something higher quality, but key-generation is quite uncommon, so you wouldn't need to be doing millions-and-millions of keygens per second, would you? Simultaions need lots of random numbers, but those random numbers don't need to have entropy guarantees, but instead have weirder requirements (not only speed of generation, but also the ability to rerun your simulation... you actually want deterministic random-number-generators for simulations to verify your results). So in these cases, PRNGs are not only needed, but superior to a true RNG. There's also the weird case of quasi-random, a term I learned from the graphics community. You want your rays to be random-ish, but actually "more uniform" than actually random. Its a more pleasant randomish pattern to look at, leading to pleasant and artistic images (https://en.wikipedia.org/wiki/Halton_sequence https://en.wikipedia.org/wiki/Halton_sequence). Quasi-random raytracing is a so called "Biased" generator, because the physical light models are probably closer to true random. However, quasi-random sequences lead to far less noise in far less time / samples, so they're more useful in practice. -------- Ultimately, our x86 CPUs today have "true" RNGs built into the RDSEED instruction, pulling entropy from some kind of physical circuit that's highly sensitive to temperature conditions (thermal quantum noise generators inside of circuits. After all, heat is quantumly random as your electrons jump between states in the very small scale).

hinkley 5y ago
> Massaging the bits into proper form: using modulus operator, requires like 80-cycles (aka: a division) It's not uncommon to instead treat the RNG data as a floating point number between 0 and 1 and multiply it by the modulus (adding or subtracting 1 as appropriate depending on whether you want, say, 0-20 or 1-20 as the output). So that's a float multiplication, an addition, and a conversion to integer. Still probably cheaper than 80 cycles. But we're also burning 32bits of data to get 4.4 bits of output. When randomness was more expensive than CPU cycles they would throw a Linear Congruence Generator on top, which is a function can transform an input and achieve similar levels of entropy in the output. It might take 5 bits or 8 bits of data instead of 32, at least quadrupling the utility of your source. But that's mostly for historical purposes. As you say, the ratio of CPU to random decisions has shifted many orders of magnitude in the last 20 years.
- dragontamer 5y ago
  Daniel Lemire has an excellent blogpost + paper of this technique you describe, except using the 64-bit multiplier circuit of CPUs. https://lemire.me/blog/2019/06/06/nearly-divisionless-random-integer-generation-on-various-systems/ https://lemire.me/blog/2019/06/06/nearly-divisionless-random... The 64x64 bit multiplier outputs a 128-bit output in ARM and x86. You see the 64-bit number as a fixed-point integer between 0 and 1 (that is to say: 0xFFFFFFFF as a 32-bit number is .9999999...). Multiply by the 64-bit version, bit-shift the result down and bam, you've got a high-speed, low-bias result. ----- So you can see the 64-bit number is a number between 0 and .999999...., that number is multiplied with "6" or whatever you care about (assuming you want to make a dice roll from 0 to 5), and the results are in the top 64-bits of the 128-bit number the multiplier circuit created. Getting you slightly less bias, and losing the unnecessary int->float and float->int conversion. ----- A bit of the cutting edge, but I gave it a few experiments and it clearly worked. I was working on an SIMD-version of this technique a couple of years back and it definitely works. You can also SIMD-ify the integer->float conversion with some smart AND / OR instructions. (See the "toFloats" routine here: https://github.com/dragontamer/AESRand/blob/master/AESRand_Paper/AESRand.cpp https://github.com/dragontamer/AESRand/blob/master/AESRand_P...) Oh right, and you can also use the AES circuits to make random numbers, but that actually was really difficult for me to figure out just right (!!!). AES round function is surprisingly bad at shuffling bits around, but with enough effort I got something working (passes 8TB+ of PractRand tests and other statistical tests)

hinkley 5y ago

> Massaging the bits into proper form: using modulus operator, requires like 80-cycles (aka: a division) It's not uncommon to instead treat the RNG data as a floating point number between 0 and 1 and multiply it by the modulus (adding or subtracting 1 as appropriate depending on whether you want, say, 0-20 or 1-20 as the output). So that's a float multiplication, an addition, and a conversion to integer. Still probably cheaper than 80 cycles. But we're also burning 32bits of data to get 4.4 bits of output. When randomness was more expensive than CPU cycles they would throw a Linear Congruence Generator on top, which is a function can transform an input and achieve similar levels of entropy in the output. It might take 5 bits or 8 bits of data instead of 32, at least quadrupling the utility of your source. But that's mostly for historical purposes. As you say, the ratio of CPU to random decisions has shifted many orders of magnitude in the last 20 years.

dragontamer 5y ago
Daniel Lemire has an excellent blogpost + paper of this technique you describe, except using the 64-bit multiplier circuit of CPUs. https://lemire.me/blog/2019/06/06/nearly-divisionless-random-integer-generation-on-various-systems/ https://lemire.me/blog/2019/06/06/nearly-divisionless-random... The 64x64 bit multiplier outputs a 128-bit output in ARM and x86. You see the 64-bit number as a fixed-point integer between 0 and 1 (that is to say: 0xFFFFFFFF as a 32-bit number is .9999999...). Multiply by the 64-bit version, bit-shift the result down and bam, you've got a high-speed, low-bias result. ----- So you can see the 64-bit number is a number between 0 and .999999...., that number is multiplied with "6" or whatever you care about (assuming you want to make a dice roll from 0 to 5), and the results are in the top 64-bits of the 128-bit number the multiplier circuit created. Getting you slightly less bias, and losing the unnecessary int->float and float->int conversion. ----- A bit of the cutting edge, but I gave it a few experiments and it clearly worked. I was working on an SIMD-version of this technique a couple of years back and it definitely works. You can also SIMD-ify the integer->float conversion with some smart AND / OR instructions. (See the "toFloats" routine here: https://github.com/dragontamer/AESRand/blob/master/AESRand_Paper/AESRand.cpp https://github.com/dragontamer/AESRand/blob/master/AESRand_P...) Oh right, and you can also use the AES circuits to make random numbers, but that actually was really difficult for me to figure out just right (!!!). AES round function is surprisingly bad at shuffling bits around, but with enough effort I got something working (passes 8TB+ of PractRand tests and other statistical tests)