Hacker News new | past | comments | ask | show | jobs | submit login

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



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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: