4 ms·
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
by 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)