13

mod オペレーターが非常に遅い非常に限られたシステム用のコードを書いています。私のコードでは、モジュロを 1 秒あたり約 180 回使用する必要があり、それを可能な限り削除するとコードの速度が大幅に向上すると考えました。 2番目に必要です。乗算と除算で可能なように、ビットシフトのみを使用してモジュロを再実装できるかどうか疑問に思っていました。したがって、これまでの私のコードはC ++です（アセンブリを使用してモジュロを実行できれば、さらに良いでしょう）。除算や乗算を使用せずにモジュロを削除するにはどうすればよいですか?

    while(input > 0)
{
    out = (out << 3) + (out << 1);
    out += input % 10;

    input = (input >> 8) + (input >> 1);
}

編集：実際には、1秒間に180回以上行う必要があることに気付きました。入力の値は、最大 40 桁の非常に大きな数値になる可能性があります。

4

5 に答える 5

22

単純なビット演算でできることは、値 (被除数) の 2 のべき乗モジュロ (除数) を、除数 1 で AND 演算することです。いくつかの例:

unsigned int val = 123; // initial value
unsigned int rem;

rem = val & 0x3; // remainder after value is divided by 4. 
                 // Equivalent to 'val % 4'
rem = val % 5;   // remainder after value is divided by 5.
                 // Because 5 isn't power of two, we can't simply AND it with 5-1(=4).

なぜそれが機能するのですか？値 123 のビット パターンを考えてみましょう。1111011次に、除数 4 のビット パターンは00000100です。これまでにわかっているように、除数は 2 のべき乗 (4 のように) である必要があり、それを 1 減らす必要があります (10 進数で 4 から 3 に)。これにより、ビット パターンが得られます00000011。元の 123 と 3 の両方をビット単位で AND した後、結果のビット パターンは になります00000011。これは 10 進数で 3 になります。2 の累乗の除数が必要な理由は、除数を 1 減らすと、下位ビットがすべて に設定され1、残りが になるため0です。ビットごとの AND を実行すると、元の値から上位ビットが「取り消され」、元の値を除数で割った残りの部分だけが残ります。

ただし、任意の除数にこのような特定のものを適用しても、事前に除数を知っていない限り(コンパイル時に、さらに除数固有のコードパスが必要)、機能しません-実行時に解決することはできません。特にあなたの場合はそうではありませんパフォーマンスが重要な場合。

また、この件に関する以前の質問には、さまざまな観点から興味深い情報が含まれている可能性があります。

于 2012-06-18T05:05:24.667 に答える
4

実際、定数による除算はコンパイラーにとってよく知られた最適化であり、実際、gccはすでにそれを行っています。

この単純なコードスニペット：

int mod(int val) {
   return val % 10;
}

-O3を使用してかなり古いgccで次のコードを生成します。

_mod:
        push    ebp
        mov     edx, 1717986919
        mov     ebp, esp
        mov     ecx, DWORD PTR [ebp+8]
        pop     ebp
        mov     eax, ecx
        imul    edx
        mov     eax, ecx
        sar     eax, 31
        sar     edx, 2
        sub     edx, eax
        lea     eax, [edx+edx*4]
        mov     edx, ecx
        add     eax, eax
        sub     edx, eax
        mov     eax, edx
        ret

関数エピローグ/プロローグを無視すると、基本的に2つのmul（x86では幸運で1つにleaを使用できます）といくつかのシフトと追加/サブがあります。この最適化の背後にある理論をどこかですでに説明したことを知っているので、もう一度説明する前に、その投稿を見つけることができるかどうかを確認します。

現在、メモリへのアクセスよりも確かに高速な最新のCPUでは（キャッシュにアクセスした場合でも）、明らかにもう少し古いCPUの方が高速かどうかは、ベンチマークでしか答えられない質問です（また、コンパイラが実行していることを確認してください）。その最適化、そうでなければ、いつでもここでgccバージョンを「盗む」ことができます;））。特に、効率を上げるには、効率的なマルチ（つまり、乗算命令の上位ビット）に依存することを考慮してください。このコードはサイズに依存しないことに注意してください。正確には、マジックナンバーの変更（およびおそらく追加/シフトの一部）ですが、それは適応可能です。

于 2012-06-18T20:50:53.680 に答える
2

ビットシフトは本質的にバイナリであるため、ビットシフトでモジュロ10を実行するのは困難で醜いものになります（今日実行するマシンでは）。考えてみれば、ビット シフトは単純に 2 で乗算または除算するだけです。

しかし、ここで行うことができる明らかな時空取引があります。 と の値のテーブルを設定し、outそれout % 10を調べます。次に、行は次のようになります

  out += tab[out]

運が良ければ、それは 1 つの 16 ビット加算とストア操作であることが判明します。

于 2012-06-18T02:12:45.667 に答える
1

モジュロ 10 とシフトを実行したい場合は、必要に応じてダブル ダブル アルゴリズムを適用できますか?

このアルゴリズムは、モジュロまたは除算を使用せずに 2 進数を 10 進数に変換するために使用されます。

于 2012-06-18T05:43:31.337 に答える
1

すべての 16 の累乗は 6 で終わります。数値を 16 の累乗の和として表す (つまりニブルに分割する) 場合、各項は 1 の位を除き、同じように最後の桁に寄与します。

0x481A % 10 = ( 0x4 * 6 + 0x8 * 6 + 0x1 * 6 + 0xA ) % 10

6 = 5 + 1 であり、5 が偶数の場合は相殺されることに注意してください。したがって、ニブル (最後のニブルを除く) を合計し、結果が奇数の場合は 5 を追加します。

0x481A % 10 = ( 0x4 + 0x8 + 0x1 /* sum = 13 */
                + 5 /* so add 5 */ + 0xA /* and the one's place */ ) % 10
            = 28 % 10

これにより、16 ビットの 4 ニブル モジュロが最大で0xF * 4 + 5 = 65. バイナリでは、厄介なことにまだ 3 つのニブルがあるため、アルゴリズムを繰り返す必要があります (ただし、そのうちの 1 つは実際にはカウントされません)。

ただし、286 には、1 回のパスで合計を実行して結果を取得するために使用できる、合理的に効率的な BCD 加算が必要です。(これには、各ニブルを手動で BCD に変換する必要があります。プラットフォームについて、それを最適化する方法や問題があるかどうかを言うのに十分な知識はありません。)

于 2012-06-18T10:24:18.667 に答える