4 ms·
> In this case, a divide by 3 is equivalent to multiplying by 0x55555556 and then taking the top half of the output. What the fuck. That's amazing!
by libeclipse 9y ago
> In this case, a divide by 3 is equivalent to multiplying by 0x55555556 and then taking the top half of the output.
What the fuck. That's amazing!
- vardump 9y agoIn that case, fixed point arithmetic might blow your mind. :) https://en.wikipedia.org/wiki/Fixed-point_arithmetic https://en.wikipedia.org/wiki/Fixed-point_arithmetic
- chris_overseas 9y agoIn more general terms, take a look at Montgomery multiplication[1] which is where this trick originates. It's a common technique used by compilers to optimise away divisions. [1] https://en.wikipedia.org/wiki/Montgomery_modular_multiplication https://en.wikipedia.org/wiki/Montgomery_modular_multiplicat...