C/C++ で % (モジュラス) を使用する代わりに何か方法はありますか?

https://stackoverflow.com/questions/48053

09-06-2019
|

質問

整数除算命令を持たない 8 ビットマイクロコントローラーのような小型の組み込みデバイスでは、モジュラス演算子は非効率的であるとどこかで読んだことがあります。おそらく誰かがこれを確認できるでしょうが、その違いは整数の除算演算よりも 5 ～ 10 倍遅いと思いました。

カウンタ変数を保持し、mod ポイントで手動で 0 にオーバーフローする以外にこれを行う別の方法はありますか?

const int FIZZ = 6;
for(int x = 0; x < MAXCOUNT; x++)
{
    if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}

対:

私が現在それを行っている方法:

const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x < MAXCOUNT; x++)
{
    if(fizzcount >= FIZZ) 
    {
        print("Fizz\n");
        fizzcount = 0;
    }
}

解決

ああ、ビット単位の算術演算の楽しさ。多くの除算ルーチンの副作用は係数です。したがって、実際には除算が係数よりも高速になることはほとんどありません。この情報を入手した情報源を知りたいです。乗算器を備えたプロセッサには、乗算器を使用した興味深い除算ルーチンがありますが、さらに 2 つのステップ (乗算と減算) だけで除算結果から係数を取得できるため、比較可能です。プロセッサに除算ルーチンが組み込まれている場合は、それが剰余も提供することがわかります。

それでも、数論には次のことに特化した小さな分野があります。モジュラー演算モジュラス演算を最適化する方法を本当に理解したい場合は、勉強が必要です。たとえば、モジュラー算術は生成に非常に便利です。魔方陣.

それで、その流れで、ここに非常に低レベルな見た目 x の例の法を計算すると、割り算と比較していかに簡単であるかがわかります。

おそらく、問題について考えるより良い方法は、数字と弾性算術の観点からです。たとえば、あなたの目標は、Dow Mod 7を計算することです。ここで、Dowは曜日の16ビット表現です。これは次のように記述できます。

 DOW = DOW_HI*256 + DOW_LO

 DOW%7 = (DOW_HI*256 + DOW_LO) % 7
       = ((DOW_HI*256)%7  + (DOW_LO % 7)) %7
       = ((DOW_HI%7 * 256%7)  + (DOW_LO%7)) %7
       = ((DOW_HI%7 * 4)  + (DOW_LO%7)) %7

この方法で表現すると、高および低バイトのModulo 7結果を個別に計算できます。結果の結果を4を掛け、それを低い値に加算し、最後に結果modulo 7を計算します。

8ビット番号のMOD 7の結果を計算することも、同様の方法で実行できます。次のように 8 ビット数値を 8 進数で書くことができます。

  X = a*64 + b*8 + c

ここで、a、b、c は 3 ビットの数値です。

  X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
      = (a%7 + b%7 + c%7) % 7
      = (a + b + c) % 7

以来 64%7 = 8%7 = 1

もちろん、a、b、cは

  c = X & 7
  b = (X>>3) & 7
  a = (X>>6) & 7  // (actually, a is only 2-bits).

可能な最大値 a+b+c は 7+7+3 = 17. 。したがって、もう1つのオクタルステップが必要です。完全な（テストされていない）Cバージョンは次のように書くことができます。

unsigned char Mod7Byte(unsigned char X)
{
    X = (X&7) + ((X>>3)&7) + (X>>6);
    X = (X&7) + (X>>3);

    return X==7 ? 0 : X;
}

私は少し時間をかけて PIC バージョンを作成しました。実際の実装は、上記の説明とはわずかに異なります

Mod7Byte:
       movwf        temp1        ;
       andlw        7        ;W=c
       movwf        temp2        ;temp2=c
       rlncf   temp1,F        ;
       swapf        temp1,W ;W= a*8+b
       andlw   0x1F
       addwf        temp2,W ;W= a*8+b+c
       movwf        temp2   ;temp2 is now a 6-bit number
       andlw   0x38    ;get the high 3 bits == a'
       xorwf        temp2,F ;temp2 now has the 3 low bits == b'
       rlncf   WREG,F  ;shift the high bits right 4
       swapf   WREG,F  ;
       addwf        temp2,W ;W = a' + b'

 ; at this point, W is between 0 and 10


       addlw        -7
       bc      Mod7Byte_L2
Mod7Byte_L1:
       addlw        7
Mod7Byte_L2:
       return

これはアルゴリズムをテストするための小さなルーチンです

       clrf    x
       clrf    count

TestLoop:
       movf        x,W
       RCALL   Mod7Byte
       cpfseq count
        bra    fail

       incf        count,W
       xorlw   7
       skpz
        xorlw        7
       movwf   count

       incfsz        x,F
       bra        TestLoop
passed:

最後に、16ビットの結果（私はテストしていない）については、次のことを書くことができます。

uint16 Mod7Word(uint16 X)
{
 return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}

スコット

他のヒント

2 の累乗を乗じた数値を計算する場合は、ビット単位の and 演算子を使用できます。2 番目の数値から 1 を引くだけです。例えば：

x % 8 == x & 7
x % 256 == x & 255

いくつかの注意点:

これ のみ機能します 2 番目の数値が 2 の累乗の場合。
係数が常に正の場合のみ同等です。C および C++ 標準では、最初の数値が負の場合の係数の符号は指定されていません (C++11 まで)。する負の値になることが保証されています。これは、ほとんどのコンパイラーがすでに行っていたことです)。ビット単位で符号ビットが削除されるため、常に正になります (つまり、)。これは真の係数であり、剰余ではありません)。とにかくそれがあなたが望んでいることのように聞こえます。
おそらく、コンパイラは可能な場合にはすでにこれを実行しているため、ほとんどの場合、手動で実行する価値はありません。

2 の累乗ではないモジュロを使用すると、ほとんどの場合オーバーヘッドが発生します。(私の知る限り) モジュラス演算子を備えたプロセッサであっても、マスク演算とは対照的に除算では数サイクル遅いため、これはプロセッサには関係ありません。

ほとんどの場合、これは検討する価値のある最適化ではなく、独自のショートカット演算を計算する価値もありません (特に、それでも除算や乗算が含まれる場合)。

ただし、経験則の 1 つは、配列サイズなどを選択することです。2の累乗になります。

したがって、曜日の計算の場合、約100のエントリの円形バッファーを設定した場合に関係なく、％7を使用することもできます...なぜ128にしないのか。その後、% 128 と書くと、ほとんど (すべて) のコンパイラがこれを & 0x7F にします。

複数の組み込みプラットフォームで高いパフォーマンスが本当に必要な場合を除き、プロファイリングを行うまではパフォーマンス上の理由でコーディング方法を変更しないでください。

パフォーマンスを最適化するためにぎこちなく書かれたコードは、デバッグも保守も困難です。テストケースを作成し、ターゲット上でプロファイリングします。係数の実際のコストがわかったら、代替ソリューションをコーディングする価値があるかどうかを判断します。

@マシューは正しいです。これを試して：

int main() {
  int i;
  for(i = 0; i<=1024; i++) {
    if (!(i & 0xFF)) printf("& i = %d\n", i);
    if (!(i % 0x100)) printf("mod i = %d\n", i);
  }
}

x%y == (x-(x/y)*y)

お役に立てれば。

埋め込まれた世界では、あなたがする必要がある「モジュラス」操作は、多くの場合、「＆」と「|」でできるビット操作にうまく分解されるものです。そして時々 '>>'。

組み込みデバイス上のプログラム可能なハードウェアにアクセスできますか?カウンターとかそういうの？その場合、シミュレートされた % を使用する代わりに、ハードウェアベースの MOD ユニットを作成できる可能性があります。（VHDLで一度やりました。ただし、コードがまだ残っているかどうかはわかりません。）

念のため言っておきますが、除算は 5 ～ 10 倍高速だと言いましたね。MOD をシミュレートするために除算、乗算、減算を実行することを検討しましたか?（編集：元の投稿を誤解しました。除算が mod よりも速いのは奇妙だと思いました。同じ演算です。)

ただし、あなたの特定のケースでは、mod 6 をチェックしています。6 = 2*3。したがって、最初に最下位ビットが 0 であるかどうかを確認すると、多少の改善が得られる可能性があります。何かのようなもの：

if((!(x & 1)) && (x % 3))
{
    print("Fizz\n");
}

ただし、それを行う場合は、プロファイラーの皆さん、何らかの利益が得られることを確認することをお勧めします。そして、いくつかのコメントをしています。そうしないと、次にコードを見なければならない人が気の毒になるでしょう。

必要な組み込みデバイスを実際に確認する必要があります。私が見たすべてのアセンブリ言語 (x86、68000) は、除算を使用してモジュラスを実装しています。

実際には、除算アセンブリ演算は、除算の結果と残りを 2 つの異なるレジスタに返します。

これが必ずしも良いというわけではありませんが、常に FIZZ まで進む内側のループと、それをすべて一定の回数繰り返す外側のループを設けることもできます。MAXCOUNT が FIZZ で割り切れない場合は、最後のいくつかの手順を特殊にする必要があるかもしれません。

そうは言っても、対象のプラットフォームでリサーチとパフォーマンスプロファイリングを実行して、下にあるパフォーマンスの制約を明確に把握することをお勧めします。最適化の取り組みをより生産的に行える場所があるかもしれません。

@ジェフV:それには問題があるようです!(さらに、元のコードは mod 6 を探していましたが、現在は基本的に mod 8 を探していることになります)。追加 +1 を続けます。コンパイラがそれを最適化してくれることを願っていますが、2 から開始して MAXCOUNT までテストしてみてはどうでしょうか?最後に、(x+1) が 8 で割り切れないたびに true を返します。それがあなたが望むことですか？（そうなのだと思いますが、確認させていただきたいです。）

モジュロ 6 の場合は、Python コードを C/C++ に変更できます。

def mod6(number):
    while number > 7:
        number = (number >> 3 << 1) + (number & 0x7)
    if number > 5:
        number -= 6
    return number

print ステートメントは、最も遅いモジュラス演算子の実装よりも桁違いに時間がかかります。したがって、基本的に、「一部のシステムで遅い」というコメントは「すべてのシステムで遅い」となるはずです。

また、提供されている 2 つのコードスニペットは同じことを行いません。2 番目の行では、

if(fizzcount >= FIZZ)

は常に false であるため、「FIZZ 」は出力されません。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow