12

私の知る限り、ほとんどのコンパイラは、乗算してから右にビットシフトすることにより、高速除算を行います。たとえば、この SO スレッドを確認すると、Microsoft コンパイラに 10 で除算するように要求すると、被除数に 0x1999999A (2^32/10) を掛けてから、結果を 2^32 で除算します (右に 32 シフト)。

(編集者注: そのリンクされた回答は、それまでは間違っていました。コンパイラは、すべての入力に対して正確ではないため、それを行いません。コンパイラは乗算とシフトを行いますが、魔法の定数とシフト カウントを決定するより複雑な方法を使用します: なぜ GCC は整数除算の実装における奇妙な数による乗算? )

ここまでは順調ですね。

ただし、GCC を使用して ARM で同じ 10 除算をテストすると、コンパイラは少し異なる結果を示しました。最初に、被除数に 0x66666667 (2^34/10) を掛けてから、結果を 2^34 で割りました。これまでのところ、より高い乗数を使用することを除いて、Microsoft と同じです。ただし、その後、結果から (被除数/2^31) が減算されます。

私の質問:なぜ ARM バージョンで余分な減算があるのですか? その減算がなければ結果が間違っている数値例を教えてください。

生成されたコードを確認したい場合は、以下のとおりです (私のコメント付き):

        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>>2, then store in r1 (effectively >>34, since r3 was higher 32 bits of multiplication)
        asr     r3, r2, #31 @--dividend>>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)
4

2 に答える 2

12

ただし、その後、結果から (被除数/2^31) が減算されます。

実際にdividend >> 31は、負の整数の右シフトが算術右シフトである場合 (および 32 ビット幅) 、-1負の の場合は 、非負の被除数の場合は 0 を減算します。dividendint

0x6666667 = (2^34 + 6)/10

したがって、 については、でx < 0書きます。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

さて、負の整数の算術右シフトは の床をもたらすv / 2^nので、

(0x66666667 * x) >> 34

結果は

k + floor((6*k + (2^34+6)*r/10) / 2^34)

だから私たちはそれを見る必要があります

-2^34 < 6*k + (2^34+6)*r/10 < 0

右の不等式は簡単で、kとの両方rが非正であり、両方が 0 になるわけではありません。

左の不等式については、もう少し分析が必要です。

r >= -9

したがって、 の絶対値 (2^34+6)*r/10はせいぜい2^34+6 - (2^34+6)/10です。

|k| <= 2^31/10,

そう|6*k| <= 3*2^31/5。

そして、それを確認することは残っています

6 + 3*2^31/5 < (2^34+6)/10
1288490194   < 1717986919

うん、本当。

于 2013-04-25T15:27:36.957 に答える