53

純粋なビットシフト、加算、減算、そしておそらく乗算を使用して、符号なし整数を10で除算することは可能ですか？リソースが非常に限られており、分割が遅いプロセッサを使用する。

4

9 に答える 9

65

編集者注: これは実際にはコンパイラが行うことではなく、107374182以外で始まる 9 で終わる大きな正の整数に対して間違った答えdiv10(1073741829) = 107374183を返します。しかし、これはより小さな入力に対しては正確であり、一部の用途には十分な場合があります。

コンパイラ (MSVC を含む) は定数除数に固定小数点乗法逆数を使用しますが、別のマジック定数を使用し、上位半分の結果をシフトして、C 抽象マシンが必要とするものと一致する、すべての可能な入力の正確な結果を取得します。アルゴリズムに関する Granlund & Montgomery の論文を参照してください。

整数除算の実装で GCC が奇妙な数による乗算を使用するのはなぜですか?を参照してください。実際の x86 asm gcc、clang、MSVC、ICC、およびその他の最新のコンパイラが作成する例については、.

これは、大規模な入力に対して不正確な高速近似です。

コンパイラが使用する乗算 + 右シフトによる正確な除算よりもさらに高速です。

小さな整数定数による除算には、乗算結果の上位半分を使用できます。32 ビット マシンを想定します (コードはそれに応じて調整できます)。

int32_t div10(int32_t dividend)
{
    int64_t invDivisor = 0x1999999A;
    return (int32_t) ((invDivisor * dividend) >> 32);
}

ここで行っていることは、1/10 * 2^32 の近似値を掛けてから、2^32 を削除していることです。このアプローチは、さまざまな除数とさまざまなビット幅に適用できます。

IMUL 命令は 64 ビット製品を edx:eax に配置し、edx 値が必要な値になるため、これは ia32 アーキテクチャに最適です。Viz (被除数が eax で渡され、商が eax で返されると仮定)

div10 proc 
    mov    edx,1999999Ah    ; load 1/10 * 2^32
    imul   eax              ; edx:eax = dividend / 10 * 2 ^32
    mov    eax,edx          ; eax = dividend / 10
    ret
    endp

乗算命令が遅いマシンでも、これはソフトウェアまたはハードウェアの除算よりも高速です。

于 2011-04-05T21:14:32.017 に答える
42

これまでの回答は実際の質問と一致していますが、タイトルと一致していません。これは、実際にはビット シフトのみを使用するHacker's Delightに大きく影響されたソリューションです。

unsigned divu10(unsigned n) {
    unsigned q, r;
    q = (n >> 1) + (n >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;
    r = n - (((q << 2) + q) << 1);
    return q + (r > 9);
}

これは、乗算命令がないアーキテクチャにとって最適なソリューションだと思います。

于 2013-09-29T08:56:52.213 に答える
21

もちろん、多少の精度の低下を許容できれば可能です。入力値の値の範囲がわかっている場合は、ビット シフトと正確な乗算を行うことができます。このブログで説明されているように、可能な限り最速の方法で時間をフォーマットする方法の例をいくつか紹介します。

temp = (ms * 205) >> 11;  // 205/2048 is nearly the same as /10
于 2011-04-05T21:12:48.740 に答える
5

アロイスの答えを少し拡張するy = (x * 205) >> 11ために、さらにいくつかの倍数/シフトの提案を拡張できます。

y = (ms *        1) >>  3 // first error 8
y = (ms *        2) >>  4 // 8
y = (ms *        4) >>  5 // 8
y = (ms *        7) >>  6 // 19
y = (ms *       13) >>  7 // 69
y = (ms *       26) >>  8 // 69
y = (ms *       52) >>  9 // 69
y = (ms *      103) >> 10 // 179
y = (ms *      205) >> 11 // 1029
y = (ms *      410) >> 12 // 1029
y = (ms *      820) >> 13 // 1029
y = (ms *     1639) >> 14 // 2739
y = (ms *     3277) >> 15 // 16389
y = (ms *     6554) >> 16 // 16389
y = (ms *    13108) >> 17 // 16389
y = (ms *    26215) >> 18 // 43699
y = (ms *    52429) >> 19 // 262149
y = (ms *   104858) >> 20 // 262149
y = (ms *   209716) >> 21 // 262149
y = (ms *   419431) >> 22 // 699059
y = (ms *   838861) >> 23 // 4194309
y = (ms *  1677722) >> 24 // 4194309
y = (ms *  3355444) >> 25 // 4194309
y = (ms *  6710887) >> 26 // 11184819
y = (ms * 13421773) >> 27 // 67108869

各行は単一の独立した計算であり、コメントに示されている値で最初の「エラー」/不正確な結果が表示されます。(x * 13) >> 7通常、特定のエラー値に対して最小のシフトを行う方が良いでしょう。これにより、計算で中間値を格納するために必要な余分なビットが最小限に抑えられます(x * 52) >> 9。 68以上で間違った答えをする。

これらをさらに計算したい場合は、次の (Python) コードを使用できます。

def mul_from_shift(shift):
    mid = 2**shift + 5.
    return int(round(mid / 10.))

そして、この近似がうまくいかなくなるときを計算するために、私は明らかなことをしました：

def first_err(mul, shift):
    i = 1
    while True:
        y = (i * mul) >> shift
        if y != i // 10:
            return i
        i += 1

//（ 「整数」除算に使用されることに注意してください。つまり、切り捨て/ゼロに向かって丸められます）

エラーの「3/1」パターン (つまり、8 回の繰り返しの後に 9 回) の理由は、塩基の変化によるものと思われます。つまりlog2(10)、~3.32 です。エラーをプロットすると、次のようになります。

エラー

ここで、相対誤差は次の式で与えられます。mul_from_shift(shift) / (1<<shift) - 0.1

于 2019-05-20T09:15:19.527 に答える
2

割り算は引き算なので、そうです。右に 1 シフトします (2 で割ります)。次に、結果から 5 を引きます。値が 5 未満になるまで引き算を行った回数を数えます。結果は、行った引き算の回数です。ああ、分割はおそらく高速になるでしょう。

右にシフトしてから通常の除算を使用して 5 で除算するハイブリッド戦略では、除算器のロジックがまだこれを行っていない場合、パフォーマンスが向上する可能性があります。

于 2011-04-05T21:12:46.010 に答える
0

lsr/ror と sub/sbc のみを使用して、AVR アセンブリで新しいメソッドを設計しました。8 で割り、64 と 128 で割った数を引き、1,024 と 2,048 を引きます。非常に信頼性が高く (正確な丸めを含む)、高速 (1 MHz で 370 マイクロ秒) に動作します。16 ビット数のソース コードはこちら: http://www.avr-asm-tutorial.net/avr_en/beginner/DIV10/div10_16rd.asm このソース コードをコメントするページはこちら: http://www .avr-asm-tutorial.net/avr_en/beginner/DIV10/DIV10.html 10 年前の質問ですが、お役に立てば幸いです。BRGS、GSC

于 2021-06-20T06:54:32.127 に答える