Magic Division

Magic Division -- Or Division by Integer Multiplication

I noticed something strange in the assembly generated when compiling a program +

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 + 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 +

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 + 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 +

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: -


+            
+                Figure 1
+            
+            Source:
+            
+                
 int div20(int n){
     return a/20;
 }
-        
-        Compiled excerpt:
-        
-            
+        
+            
+            Compiled excerpt:
+            
+                
 .cfi_startproc
 movl    %edi, %eax
 movl    $1717986919, %edx
@@ -74,22 +79,24 @@ movl    %edx, %eax
 subl    %edi, %eax
 ret
 .cfi_endproc
-        
+

References

1 Hacker’s Delight Chapter 10. +

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

2 MSDN Blog Archive +

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