23

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"?

user1421750
  • 1,200
  • 2
  • 9
  • 16
  • 2
    The constant that you multiply by is an approximation of the reciprocal. The random +/- 1's here and there are to make sure it's always "rounded" correctly. Proving that a particular method is correct can be done either mathematically, or by brute-force testing of all numerators. (For 32-bit, this is totally feasible.) – Mysticial Jun 11 '15 at 19:59
  • @Mysticial: That looks like an answer to me. – Scott Hunter Jun 11 '15 at 20:00
  • @ScottHunter Maybe later when I'm off of work. I don't have quite the tools here to give a comprehensive answer. – Mysticial Jun 11 '15 at 20:07
  • 1
    http://homepage.cs.uiowa.edu/~jones/bcd/divide.html – old_timer Jun 11 '15 at 20:21
  • @Mysticial: What you wrote as a comment looks better than a lot of answers I've seen (and some I've written). But I guess that's how one gets to a 200K+ rep. – Scott Hunter Jun 11 '15 at 20:43
  • I am pretty sure it's not doing `/ 0xFFFFFFFF` ... – Jester Jun 11 '15 at 23:40
  • @Mysticial - if done properly, the reciprocal is "exact". In some cases, such as dividing by 7, a 33 bit multiplier is emulated by doing a 5 instruction sequence, (mul, sub, shift right 1, add, shift right), versus the normal 2 instruction sequence (mul, shift right). This is explained in the [prior question](https://stackoverflow.com/questions/41183935) . – rcgldr Apr 22 '19 at 00:03

1 Answers1

26

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.

Mysticial
  • 464,885
  • 45
  • 335
  • 332
  • 8
    The canonical reference is: T. Granlund and P. L. Montgomery, “Division by invariant integers using multiplication,” in *Proceedings of the SIGPLAN ’94 Conference on Programming Language Design and Implementation*, 1994, pp. 61–72. – njuffa Jun 11 '15 at 21:45
  • 4
    Additional, more recent reference: N. Möller and T. Granlund, “Improved division by invariant integers,” *IEEE Transactions on Computers*, vol. 60, no. 2, pp. 165 –175, Feb. 2011. – njuffa Jun 11 '15 at 22:55
  • 1
    Your generalization and the proof is wrong. Also the 0x55555556 for division by 3 only works for the signed range, ie. up to 2^31. – Jester Jun 11 '15 at 23:46
  • @Jester I guess I suck at math. I've removed that part of the answer. – Mysticial Jun 11 '15 at 23:59
  • @Jester thanks for pointing out wrong generalization. A good way to disprove a general property is to exhibit a counter-example. Can you do that? – Stéphane Gourichon May 16 '18 at 16:01
  • 1
    @StéphaneGourichon - division by 7 and some other values requires special handling. The "exact" reciprocal requires 1 more bit than the number of bits in an integer. This is handled using a 32 bit value and a 5 instruction sequence (mul, sub, shift right 1, add, shift right ...) rather than the 2 instruction sequence (mul, shift right ...) . This is explained in the [prior question](https://stackoverflow.com/questions/41183935) . – rcgldr Apr 22 '19 at 00:05
  • This answer is pretty useless, but the reference to the paper by @njuffa is basically the answer. Someone should write an answer with that reference and it should be the accepted one. Alternatively, Mysitical should put the reference at the top of their answer, and leave the rest of the text for those who want to read it (not necessary.) – ldog Dec 10 '20 at 00:04
  • @ldog: this question was already closed as a duplicate of [Why does GCC use multiplication by a strange number in implementing integer division?](https://stackoverflow.com/q/41183935) which has answers with more details, including the links to papers I think. – Peter Cordes Feb 19 '21 at 03:32
  • @PeterCordes yes I've had a look, the answer with the paper reference is there, but unfortuantely it is not the accepted answer. I've actually spent some time investigating this topic and found that a combination of the paper & dissasembling optimized code (from your favorite compiler) is by far the most instructive answer. – ldog Feb 19 '21 at 03:41