4 ms·
What's not mentioned is that in most cases you have a constant divisor which lets you replace division by multiplication with the reciprocal. The reciprocal can
by orlp 2y ago
What's not mentioned is that in most cases you have a constant divisor which lets you replace division by multiplication with the reciprocal. The reciprocal can be rounded to a nearby dyadic rational, letting you do the division with a right-shift.
For example, 8-bit division by 3 is equivalent to widening multiplication by 171 followed by a right-shift of 9, as 171/2^9 = 0.333984375 which is close enough to 1/3 that the results match exactly.
- edflsafoiewq 2y agoA shift of 16 is enough for every 8-bit numerator, ie. x/a is (u32(x)*b)>>16 for some b depending only on a. You could precompute b for each a and store it a lookup table. The largest b is b=65536 for a=1 and the smallest is b=258 for a=255, so b fits in a u16 if stored with a 1-offset. Not sure it's worth it unless you reuse the denominator many times though.
- deleted 2y ago[deleted]
- thaumasiotes 2y ago> For example, 8-bit division by 3 is equivalent to widening multiplication by 171 followed by a right-shift of 9, as 171/2^9 = 0.333984375 which is close enough to 1/3 that the results match exactly. Is this related to the fact that 171 is the multiplicative inverse of 3 (mod 256), or is that a coincidence?
- orlp 2y agoIt's not entirely a coincidence but also not a general result that one should use the modular inverse as multiplier. 171 * 3 = 2^9 + 1, which is not surprising as we know that 171 * 3 = 1 (mod 2^8). So rearranged we have 171 / 2^9 = 1/3 + 1/(2^9*3) which shows it's a close approximation of 1/3.
- zahlman 2y agoSort of. (After all, a "reciprocal" for our purposes is just a multiplicative inverse in the reals, so it makes sense that it would be related to the multiplicative inverse in other domains.) 3 times 171 is 513. So to divide by 3, we could multiply by 171 and then divide by 513. Dividing by 513... isn't any easier, but 513 is close to 512, so we hope that dividing by 512 (which is trivial - just a right-shift) gets us close enough. Suppose for a moment we try dividing 3 by 3 using this trick. First we'll multiply by 171 to get 513. Consider that value in binary: 1000000001 ^^^^^^^^^ ~~~~~~~~ Dividing by 512 will shift away the ^ bits. For floor division, we therefore want the ^ underlined value to be close to zero. (That way, when we divide 255 (say) by 3, the error won't be big enough to overflow into the result bits.) The multiplicative inverse fact is equivalent to telling us that the ~ underlined bits are exactly 1. Conveniently, that's close to 0 - but we didn't account for all the ^ underlined bits. For example, the multiplicative inverse of 7 (mod 256) is 183, but 7 times 183 is 1281. That's close to 1280, but that doesn't really help us - we could right-shift by 8 but then we still have to divide by 5. If we just ignore the problem and divide by 1024 (right-shift by 10), of course we get a lot of wrong results. (Even 6 / 7 would give us 1 instead of 0.) It also turns out that we'll need more bits for accurate results in the general case. I think it's possible without overflowing 16-bit numbers, but it definitely requires a bit more trickery for problematic divisors like (from my testing) 195. I thought I remembered the details here but proved myself wrong at the Python REPL :(
- kevinventullo 2y agoAlso, 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).
- 15155 2y agoThese methods are especially useful in hardware/FPGA implementations where it's infeasible to have a ton of fully pipelined dividers.
- andrepd 2y agoThey are actually useful for optimising compilers too! Mul or mul+shifts is often faster than div
- deleted 2y ago[deleted]
- godsmokescrack 2y ago[flagged]
- uticus 2y agoDoes this approach still support modulo?
- dzaima 2y agoWorst-case, you just multiply the result by the divisor and subtract that from the dividend.
- titzer 2y agoThe article might have been updated since you read it, but this is in there: > We try to vectorize the following C++ procedure. The procedure cannot assume anything about dividends, especially if they are all equal. Thus, it is not possible to employ division by a constant.
- ndesaulniers 2y agoProbably could teach LLVM these tricks. Last I checked, division by double word was problematic.
- vrighter 2y agoI wrote a blog post about this a long time ago: https://vrighter.livejournal.com/5582.html https://vrighter.livejournal.com/5582.html