2 ms·
Also, if you know ahead of time that it’s exact division, there is a similar approach that doesn’t even need widening multiplication!
by kevinventullo 2y ago
Also, if you know ahead of time that it’s exact division, there is a similar approach that doesn’t even need widening multiplication!
- orlp 2y agoYes, if you know something is an exact multiple of n = r*2^k where r is odd, you can divide out the multiple by right-shifting k followed by modular multiplication by the modular multiplicative inverse of r.
- thaumasiotes 2y agoTheoretically, you could also take advantage of two's complement arithmetic: 00011011 (27) x 01010101 (-0.333...) ------------------------ 11110111 (-9) invert and add one: 00001001 (9, like we wanted) I'd be interested in extending this to non-exact multiples, but if that's possible I don't know how.
- Footkerchief 2y agoCan you provide an example with details? Thanks!
- kevinventullo 2y agoIn 8-bit arithmetic (i.e. mod 256), the multiplicative inverse of 11 is 163. So, if you take some multiple of 11, say 154, then you can compute 154/11 instead as 154*163. Indeed, 154*163 = 25102, and 25102 = 14 (mod 256).