Magic Division

Magic Division -- Or Division by Integer Multiplication

+ +

I noticed something strange in the assembly generated when compiling a program + using gcc an optimization turned off. Here it is in Figure 1 + (though using optimization level 3 just to simplify, but it still shows in level 0). + In this generated assembly, we see instead of using the div operator, + something strange is going on with the number 1717986919 and shifting. My first + attempts at searching for this phenomenon online were not helpful. The first result + for the number was on Amazon as a book identifier. This number also shows up on + stack overflow, however it is no more helpful. No one on the post is talking about + why this number is in the generated code (or perhaps they all know this arcane + secret and don’t wish share). Eventually, I found out what was going on. Even + with no optimization, the compiler prefers to generate multiplication operator + over the division operator. +

We will consider unsigned integer division first. Let + d + be some constant divisor, and n + our numerator (for now let’s make n + a multiple of d). We will assume + integers are 32 bits. In order to computer + n/d, + first we need to know the values l + and i where + d = l2ⁱ. + So to begin out division, we can shift n + by i bits. Now we must divide this result + be l. Since + l will be odd, there exists some + inverse of l, called + j where
+ lj = 1(mod 2³²)
+ So for any number x, + x/l = (xj)/(lj)=xj. + So now all that is left after the shift is to multiply by + j, and we will + have computed n/d.

Dealing with remainder can go pretty in depth, and I recommend + reading the chapter in Hacker’s Delight about this topic + [1]. Another write up can be found + in the MSDN blog archive [2]. +

+ +

Figure 1

+ Source: +


+int div20(int n){
+    return a/20;
+}
+

+ Compiled excerpt: +


+.cfi_startproc
+movl    %edi, %eax
+movl    $1717986919, %edx
+sarl    $31, %edi
+imull   %edx
+sarl    $3, %edx
+movl    %edx, %eax
+subl    %edi, %eax
+ret
+.cfi_endproc
+

+ +

References

1 Hacker’s Delight Chapter 10. + ( + http://www.hackersdelight.org/divcMore.pdf + + ) +

2 MSDN Blog Archive + ( + https://blogs.msdn.microsoft.com/devdev/2005/12/12/integer-division-by-constants/ + + ) +