質問

高速整数演算とそれほど高速ではない float演算を備えたマイクロプロセッサ用のコードを書いています。整数を1〜9の数値で除算し、結果を整数に戻す必要があります。

0、1、0.5、0.3333などのメンバーでfloat配列を作成しました。 しかし、（1/3）を除く数値にはMAGIC定数（0x55555556など）があると思います。

この数字は何ですか？

役に立ちましたか？

解決

マイクロコントローラの除算命令が十分に速い場合は、それを使用してください。結果の小数部が必要な場合は、残りを使用できる場合があります。ほとんどのアーキテクチャでは、除算命令は商を1つのレジスタに入れ、残りを別のレジスタに入れます。

除算命令の速度が十分ではなく、乗算命令の速度が速い場合は、次の手法を使用できます（これが目的の手法であるかのように聞こえます）。ほとんどのアーキテクチャでは、32ビットの数値に別の32ビットの数値を掛けると、64ビットの結果になります。上位半分は一方のレジスタに格納され、下位半分はもう一方のレジスタに格納されます。これを利用するには、数値nによる除算が（2 ^ 32）/ nを乗算することと同じであると認識し、結果の上位32ビットを取得します。つまり、3で除算する場合は、代わりに0x100000000 / 3 = 0x55555555を掛けて、結果の上位32ビットを取得できます。

ここで行っていることは、実際には固定小数点演算の形式です。詳細については、ウィキペディアの記事をご覧ください。

他のヒント

整数の整数定数による除算は、シフトと乗算の組み合わせで置き換えることができます。詳細については、この最適化ガイドをご覧ください。もちろん、これは対象のチップ上で実際に高速である場合に便利です。

マイクロコントローラータグに基づいて、高速整数除算は行わないと仮定しています。私の答えは符号なしの値でもあります-符号付きの値で動作します。以下のトリッキーなビットで使用される数値を制限する必要があります。

適切な開始点は、2、4、8で除算することです。これらは、CPUに論理右シフト命令がある場合、それぞれ1、2、3ビットの右シフトで実行できます。

第二に、1で割ると、数字がそのまま維持されます。 3、5、6、7、および9のままです。

トリッキーなビットはここから始まります：

その他の数値については、除算を乗算とシフトで置き換えることができるという事実を使用できます。

16ビットプロセッサを搭載しているとします。 Nで除算するには、256 / Nで乗算し、右に8ビットシフトします。

N = 3, multiply by 85
N = 5, multiply by 51
N = 6, multiply by 43
N = 7, multiply by 37
N = 9, multiply by 28

72/5のランダムな例を取り上げます。72を51で乗算して3672を取得し、次に8ビット右シフトして14を取得します。

これが機能するためには、使用している数字が16ビットをオーバーフローしてはいけません。最悪の場合は85で乗算されるため、771までの数値を処理できます。

これが機能する理由は、8ビットの右シフトが256で除算するのと同じだからです。

  m * (256 /  n) / 256
= m / (n /  256) / 256
= m /  n *  256  / 256
= m /  n * (256  / 256)
= m /  n

32ビットプロセッサを使用している場合、65536 / Nであるため、値と範囲は多少変更されます。

N = 3, multiply by 21,846, right shift 16 bits, max value roughly 196,600.
N = 5, multiply by 13,108.
N = 6, multiply by 10,923.
N = 7, multiply by  9,363.
N = 9, multiply by  7,282.

もう一度、ランダム20,000 / 7を選択しましょう：20,000に9,363を掛けると187,260,000になり、その16ビットを右にシフトすると2,857になります-実際の結果は2,857です。

次のCのテストプログラムは、指定された値の精度の数値を示しています。符号付きの値を使用するため、最大約98,000で十分ですが、最大のエラーは1であり、13,110の低いポイントで発生することがわかります（0.008％のエラーのみ）。

#include <stdio.h>
int res[5] = {0};
int low[5] = {-1,-1,-1,-1,-1};
int da[] = {3,5,6,7,9};
int ma[] = {21846,13108,10923,9363,7282};
int main (void) {
    int n, i;
    for (n = 0; n < 98000; n++) {
        for (i = 0; i < sizeof(da)/sizeof(da[0]); i++) {
            int r1 = n / da[i];
            int r2 = (n * ma[i])>>16;
            int dif = abs (r1-r2);
            if (dif >= 5) {
                printf ("%d / %d gives %d and %d\n", n, da[i], r1, r2);
                return 1;
            }
            res[dif]++;
            if (low[dif] == -1) {
                low[dif] = n;
            }
        }
    }
    for (i = 0; i < sizeof(res)/sizeof(res[0]); i++) {
        printf ("Difference of %d: %6d, lowest value was %6d\n", i, res[i], low[i]);
    }
    return 0;
}

この出力：

Difference of 0: 335874, lowest value was      0
Difference of 1: 154126, lowest value was  13110
Difference of 2:      0, lowest value was     -1
Difference of 3:      0, lowest value was     -1
Difference of 4:      0, lowest value was     -1
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top