3 ms·
> 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 f
by 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 agoDaniel 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)