Rounding integer division by multiply-and-shift

Question

I learned about this trick the other day by inspecting the machine code generated by gcc. Dividing an integer a by a constant b can be optimized as follows:

x = a / b
x = a * (1 / b)
x = (a * (((1 << n) / b) + 1)) >> n

The reciprocal can be evaluated at compile-time, resulting in a multiply-and-shift operation that is more efficient than division.

c = ((1 << n) / b) + 1
x = (a * c) >> n

Now this has the same effect as plain integer division, it truncates the result (rounding towards zero). Is it possible to modify this algorithm to round towards the nearest value instead?

You don't need to care about that. Just do a normal division, with adjustments before or after for rounding. See [Rounding integer division (instead of truncating)](https://stackoverflow.com/q/2422712/995714), [Fast ceiling of an integer division in C / C++](https://stackoverflow.com/q/2745074/995714) — phuclv, Sep 04 '18 at 17:10
I'm writing a vector division routine using MMX, so I do care. — user5434231, Sep 04 '18 at 17:13
if the values fit in 24 bits then may be packed floats in SSE would work, and it'll also be easier to calculate the reciprocal in floating-point operations — phuclv, Sep 04 '18 at 17:26
Note that your trick doesn't work in many cases: e.g., suppose `a = 3`, `b = 3`. Let's pick `n = 32` (for the sake of argument, but actually any `n` will do here). Then your shortcut gives a result `x = 0` instead of the expected `x = 1`. There are many similar cases. So the statement "this has the same effect as plain integer division" isn't true. — Mark Dickinson, Sep 04 '18 at 20:14
@mark-dickinson - You're right, `c` is off by one. Fixed it. — user5434231, Sep 05 '18 at 15:49

user5434231 · Answer 1 · 2018-09-05T15:41:08.863

0

I came up with:

c = (1 << n) / b
d = a * c
x = ((d >> (n - 1)) & 1) + (d >> n)

Does the trick, but I wonder if there are more efficient methods.

edit: I posed the same question on reddit and got a better answer: https://www.reddit.com/r/AskProgramming/comments/9cx9dl/rounding_integer_division_by_multiplyandshift/

c = ((1 << n) + b - 1) / b;
x = (((a * c) >> (n - 1)) + 1) >> 1

One more shift can be removed by defining another constant:

e = 1 << (n - 1)
x = (a * c + e) >> 1

edited Sep 05 '18 at 15:41

answered Sep 04 '18 at 17:15

user5434231

579
3
16

2

calculating c as `(1 << n) / b` is not correct. For example to [divide by 5 you need to 0xCCCCCCCCCCCCCCCD instead of 0xCCCCCCCCCCCCCCCC](https://stackoverflow.com/q/41183935/995714). Same to [division by 10](https://stackoverflow.com/q/5558492/995714). The rounding is important and is described in the [hacker's delight book](http://www.hackersdelight.org/magic.htm) – phuclv Sep 04 '18 at 17:23

Rounding integer division by multiply-and-shift

1 Answers1