Hacker News Reader

Comment by kevinventullo | Hacker News Reader

Also, if you know ahead of time that it’s exact division, there is a similar approach that doesn’t even need widening multiplication!

View on HN

Yes, 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.

Theoretically, 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.

Can you provide an example with details? Thanks!

In 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).

Reply on news.ycombinator.com