|
|
|
|
|
|
by ridiculous_fish
1048 days ago
|
|
|
For flooring integer division with a bounded dividend and known constant, the idea is to multiply by a scaled reciprocal. For example with 32 bit division by 3, you might precompute 2^32 / 3, multiply by that, and then flooring-divide by 2*32 (right shift). It gets tricky because 2^32/3 is not an integer, so you must round it. This introduces error; the idea is to show that the error is wiped out by the flooring divide. I did the monster math here: https://ridiculousfish.com/blog/posts/labor-of-division-epis... |
|
|