3 ms·
On most modern platforms, the cost of each operation, from smallest to largest, is roughly something like this[0]: 1. Bit shifting 2. Integer multiplication
by desdiv 10y ago
On most modern platforms, the cost of each operation, from smallest to largest, is roughly something like this[0]:
1. Bit shifting
2. Integer multiplication
3. Integer division
4. Floating point multiplication
The trick in the article works because the cost of 1 + 2 is still smaller than 3.
Multiplying with the inverse of 19, a floating point number, wouldn't work because 4 is more costly than 3.
[0] http://nicolas.limare.net/pro/notes/2014/12/12_arit_speed/ http://nicolas.limare.net/pro/notes/2014/12/12_arit_speed/
- kr7 10y agoThat page has a warning at the top: > IMPORTANT: Useful feedback revealed that some of these measures are seriously flawed. A major update is on the way. Looking over the results, some of the numbers are off. On Intel CPUs, FP multiplication is faster than integer division. Might not be true on ARM CPUs which generally have slower FPUs. On Skylake, for example, 32-bit unsigned integer division has a 26 cycle latency with a throughput of 1 instruction / 6 cycles, while 32/64-bit floating point multiplication has a 4 cycle latency with a throughput of 2 instructions / cycle. Source: http://agner.org/optimize/instruction_tables.pdf http://agner.org/optimize/instruction_tables.pdf
- yuriks 10y agoThe crucial point, however, is that while FP multiplication is faster than integer division, converting between a floating point and an integer is very slow: cvtsi2ss and cvtss2si have a latency of 6 cycles each. This adds a latency of 12 cycles for each of these multiplications. For divisions by a constant value that don't easily decompose into shifts you can fall back to multiplication by a magic constant which is the integer reciprocal. (This is also something compilers do and is what's being explained in the article.)
- caf 10y agoMultiplying by the integer reciprocal only works if the dividend is an integer multiple of the divisor. What's being explained in the article is multiplying by a fraction the value of which is close to the rational reciprocal of the divisor, and where the denominator of the fraction is an integer power of two (so dividing by the denominator can be done with a shift). The fraction in this case is (2938661835 + 2^32) / 2^37.