title: Fast Division on GCC/ARM
body: <p>As far as I know most compilers will do fast division by multiplying and then bit shifting to the right. For instance, if you check <a href="https://stackoverflow.com/questions/5558492/divide-by-10-using-bit-shifts">this SO thread</a> it says that when you ask the Microsoft compiler to do division by 10 it will multiply the dividend by 0x1999999A (which is 2^32/10) and then divide the result by 2^32 (using 32 shifts to the right).</p>
  
  <p>(Editor's note: that linked answer was wrong until.  Compilers don't do that because it's not exact for all inputs.  Compilers do multiply and shift, but with a more involved way of determining the magic constant and shift counts:  <a href="https://stackoverflow.com/questions/41183935/why-does-gcc-use-multiplication-by-a-strange-number-in-implementing-integer-divi">Why does GCC use multiplication by a strange number in implementing integer division?</a>)</p>
  
  <hr>
  
  <p>So far so good.</p>
  
  <p>Once I tested the same division by 10 on ARM using GCC, though, the compiler did something slightly different. First it multiplied the dividend by 0x66666667 (2^34/10), then it divided the result by 2^34. Thus far it's the same as Microsoft, except using a higher multiplier. After that, however, it subtracted (dividend/2^31) from the result. </p>
  
  <p><strong>My question</strong>: why on the ARM version there's that extra subtraction? Can you give me an numeric example where without that subtraction the result will be wrong? </p>
  
  <p>If you want to check the generated code, it's below (with my comments):</p>
  
  <pre><code>        ldr     r2, [r7, #4] @--this loads the dividend from memory into r2
          movw    r3, #:lower16:1717986919 @--moves the lower 16 bits of the constant 
          movt    r3, #:upper16:1717986919 @--moves the upper 16 bits of the constant
          smull   r1, r3, r3, r2 @--multiply long, put lower 32 bits in r1, higher 32 in r3
          asr     r1, r3, #2 @--r3&gt;&gt;2, then store in r1 (effectively &gt;&gt;34, since r3 was higher 32 bits of multiplication)
          asr     r3, r2, #31 @--dividend&gt;&gt;31, then store in r3
          rsb     r3, r3, r1 @--r1 - r3, store in r3
          str     r3, [r7, #0] @--this stores the result in memory (from r3) 
  </code></pre>