Perform integer division using multiplication [duplicate]

Question

Looking at x86 assembly produced by a compiler, I noticed that (unsigned) integer divisions are sometimes implemented as integer multiplications. These optimizations seem to follow the form

value / n => (value * ((0xFFFFFFFF / n) + 1)) / 0x100000000

For example, performing a division by 9:

12345678 / 9 = (12345678 * 0x1C71C71D) / 0x100000000

A division by 3 would use multiplication with 0x55555555 + 1, and so on.

Exploiting the fact that the mul instruction stores the high part of the result in the edx register, the final result of the division can be obtained using a single multiplication with a magic value. (Though this optimization is sometimes used in conjunction with a bit-wise shift at the end.)

I would like some insight on how this actually works. When is this approach valid? Why must 1 be added to our "magic number"?

Answer 1

That method is called, "Division by Invariant Multiplication".

The constants that you're seeing are actually approximates of the reciprocal.

So rather than computing:

N / D = Q

you do something like this instead:

N * (1/D) = Q

where 1/D is a reciprocal that can be precomputed.

Fundamentally, reciprocals are imprecise unless D is a power-of-two. So there will some round-off error involved. The +1 that you see is there to correct for the round-off error.

---

The most common example is division by 3:

N / 3 = (N * 0xaaaaaaab) >> 33

Where 0xaaaaaaab = 2^33 / 3 + 1.

This approach will generalize to other divisors.