2

私は、高速な整数演算とそれほど高速ではない浮動小数点演算を備えたマイクロプロセッサのコードを書いています。整数を 1 から 9 までの数値で割り、結果を整数に戻す必要があります。

0、1、0.5、0.3333 などのメンバーを持つ float 配列を作成しましたが、(1/3) 以外の数値には MAGIC 定数 (0x55555556 など) があると思います。

この数字は何ですか？

4

2 に答える 2

4

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

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

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

于 2009-10-21T12:47:11.683 に答える
1

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

良い開始点は、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
于 2009-10-21T12:44:52.047 に答える