assembly - Fast Division on GCC/ARM -
as far know compilers fast division multiplying , bit shifting right. instance, if check this thread says when ask microsoft compiler division 10 multiply dividend 0x1999999a (which 2^32/10) , divide result 2^32 (using 32 shifts right).
so far good.
once tested same division 10 on arm using gcc, though, compiler did different. first multiplied dividend 0x66666667 (2^34/10), divided result 2^34. far it's same microsoft, except using higher multiplier. after that, however, subtracted (dividend/2^31) result.
my question: why on arm version there's subtraction? can give me numeric example without subtraction result wrong?
if want check generated code, it's below (with comments):
ldr r2, [r7, #4] @--this loads dividend memory r2 movw r3, #:lower16:1717986919 @--moves lower 16 bits of constant movt r3, #:upper16:1717986919 @--moves upper 16 bits of constant smull r1, r3, r3, r2 @--multiply long, put lower 32 bits in r1, higher 32 in r3 asr r1, r3, #2 @--r3>>2, store in r1 (effectively >>34, since r3 higher 32 bits of multiplication) asr r3, r2, #31 @--dividend>>31, store in r3 rsb r3, r3, r1 @--r1 - r3, store in r3 str r3, [r7, #0] @--this stores result in memory (from r3)
after that, however, subtracted (dividend/2^31) result.
actually, subtracts dividend >> 31, -1 negative dividend, , 0 non-negative dividend, when right-shifting negative integers arithmetic right-shift (and int 32 bits wide).
0x6666667 = (2^34 + 6)/10 so x < 0, have, writing x = 10*k + r -10 < r <= 0,
0x66666667 * (10*k+r) = (2^34+6)*k + (2^34 + 6)*r/10 = 2^34*k + 6*k + (2^34+6)*r/10 now, arithmetic right shift of negative integers yields floor of v / 2^n, so
(0x66666667 * x) >> 34 results in
k + floor((6*k + (2^34+6)*r/10) / 2^34) so need see that
-2^34 < 6*k + (2^34+6)*r/10 < 0 the right inequality easy, both k , r non-positive, , not both 0.
for left inequality, bit more analysis needed.
r >= -9 so absolute value of (2^34+6)*r/10 @ 2^34+6 - (2^34+6)/10.
|k| <= 2^31/10, so |6*k| <= 3*2^31/5.
and remains verify that
6 + 3*2^31/5 < (2^34+6)/10 1288490194 < 1717986919 yup, true.
