80

多くの場合、内部ループでは、「ラップアラウンド」方式で配列にインデックスを付ける必要があります。たとえば、配列サイズが100で、コードが要素-2を要求する場合、要素98を指定する必要があります。 Pythonなどの高級言語では、これを簡単に行うことができますmy_array[index % array_size]が、何らかの理由で、Cの整数演算は（通常）一貫して切り捨てるのではなくゼロに向かって丸められます。その結果、そのモジュロ演算子は、負の最初の引数が与えられると負の結果を返します。

index多くの場合、それは以上になることを知っていますが-array_size、これらの場合は単にそうしますmy_array[(index + array_size) % array_size]。ただし、これが保証されない場合もあります。そのような場合は、常に正のモジュロ関数を実装するための最速の方法を知りたいと思います。分岐せずにそれを行うためのいくつかの「賢い」方法があります。

inline int positive_modulo(int i, int n) {
    return (n + (i % n)) % n;
}

また

inline int positive_modulo(int i, int n) {
    return (i % n) + (n * (i < 0));
}

もちろん、これらのプロファイルを作成して、システムで最速のものを見つけることはできますが、より良いものを見逃した可能性があることや、別のマシンで高速なものが遅い可能性があることを心配せずにはいられません。

それで、これを行うための標準的な方法、または私が見逃したいくつかの巧妙なトリックがありますか？それは可能な限り最速の方法である可能性がありますか？

また、それはおそらく希望的観測だと思いますが、自動ベクトル化できるこれを行う方法があれば、それは驚くべきことです。

4

9 に答える 9

86

私が学んだ標準的な方法は

inline int positive_modulo(int i, int n) {
    return (i % n + n) % n;
}

absこの関数は、基本的に（実際には、間違った結果を返すようにする）を含まない最初のバリアントです。最適化コンパイラがこのパターンを認識し、「符号なしモジュロ」を計算するマシンコードにコンパイルできたとしても、私は驚かないでしょう。

編集：

2番目のバリアントに移ります。まず、バグも含まれていn < 0ますi < 0。

このバリアントは分岐しているようには見えないかもしれませんが、多くのアーキテクチャでは、i < 0は条件付きジャンプにコンパイルされます。いずれにせよ、乗算を回避するため(n * (i < 0))に、少なくとも同じくらい速く置き換えることができます。i < 0? n: 0さらに、boolをintとして再解釈することを回避するため、「よりクリーン」です。

これらの2つのバリアントのどちらが高速であるかについては、おそらくコンパイラとプロセッサのアーキテクチャに依存します。2つのバリアントの時間を計ってください。ただし、これら2つのバリアントのどちらよりも速い方法はないと思います。

于 2013-02-21T08:13:09.587 に答える
30

モジュロは2の累乗であり、次のように機能します（2の補数表現を想定）。

return i & (n-1);
于 2013-02-21T08:02:31.793 に答える
24

ほとんどの場合、コンパイラーはコードの最適化に非常に優れているため、通常はコードを読みやすくするのが最善です（コンパイラーと他の開発者の両方があなたが何をしているかを知ることができます）。

配列サイズは常に正なので、商をとして定義することをお勧めしますunsigned。コンパイラは、小さなif / elseブロックを、分岐のない条件付き命令に最適化します。

unsigned modulo( int value, unsigned m) {
    int mod = value % (int)m;
    if (mod < 0) {
        mod += m;
    }
    return mod;
}

これにより、ブランチのない非常に小さな関数が作成されます。

modulo(int, unsigned int):
        mov     eax, edi
        cdq
        idiv    esi
        add     esi, edx
        mov     eax, edx
        test    edx, edx
        cmovs   eax, esi
        ret

たとえば、をmodulo(-5, 7)返します2。

残念ながら、商は不明であるため、整数除算を実行する必要があります。これは、他の整数演算に比べて少し遅いです。配列のサイズが2の累乗であることがわかっている場合は、これらの関数定義をヘッダーに保持して、コンパイラーがそれらをより効率的な関数に最適化できるようにすることをお勧めします。これが関数unsigned modulo256(int v) { return modulo(v,256); }です：

modulo256(int):                          # @modulo256(int)
        mov     edx, edi
        sar     edx, 31
        shr     edx, 24
        lea     eax, [rdi+rdx]
        movzx   eax, al
        sub     eax, edx
        lea     edx, [rax+256]
        test    eax, eax
        cmovs   eax, edx
        ret

アセンブリを参照してください：https ：//gcc.godbolt.org/z/DG7jMw

最も投票された回答との比較を参照してください：http：//quick-bench.com/oJbVwLr9G5HJb0oRaYpQOCec4E4

ベンチマークの比較

編集：Clangは、条件付きの移動命令なしで関数を生成できることがわかりました（通常の算術演算よりもコストがかかります）。積分除算は合計時間の約70％を要するため、この違いは一般的なケースでは完全に無視できます。

基本的に、Clangはvalue右にシフトして、符号ビットをの幅全体に拡張しますm（つまり0xffffffff、負の0場合など）。これは、の2番目のオペランドをマスクするために使用されmod + mます。

unsigned modulo (int value, unsigned m) {
    int mod = value % (int)m;
    m &= mod >> std::numeric_limits<int>::digits;
    return mod + m;
}
于 2019-09-26T14:19:30.197 に答える
9

2の補数の符号ビット伝播を使用してオプションの加数を取得する昔ながらの方法：

int positive_mod(int i, int m)
{
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1;
    int r = i%m;
    return r+ (r>>shift & m);
}
于 2013-02-22T04:46:52.687 に答える
7

C /C++で正のモジュロを取得する最速の方法

次は速い？-他の人ほど速くはないかもしれませんが、他の人とは異なり、すべての1 に対してシンプルで機能的に正しいです。a,b

int modulo_Euclidean(int a, int b) {
  int m = a % b;
  if (m < 0) {
    // m += (b < 0) ? -b : b; // avoid this form: -b is UB when b == INT_MIN
    m = (b < 0) ? m - b : m + b;
  }
  return m;
}

他のさまざまな回答にはmod(a,b)、特にの場合に弱点がありb < 0ます。

についてのアイデアについては、除法の原理を参照してくださいb < 0

inline int positive_modulo(int i, int n) {
    return (i % n + n) % n;
}

i % n + nオーバーフローすると失敗します（大きいと思いますi, n）-未定義の動作。

return i & (n-1);

n2の累乗として依存します。（答えがこれに言及しているのは公平です。）

int positive_mod(int i, int n)
{
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1;
    int m = i%n;
    return m+ (m>>shift & n);
}

多くの場合、失敗しn < 0ます。e、g、positive_mod(-2,-3) --> -5

int32_t positive_modulo(int32_t number, int32_t modulo) {
    return (number + ((int64_t)modulo << 32)) % modulo;
}

2つの整数幅を使用する必要があります。（答えがこれに言及しているのは公平です。）
で失敗しmodulo < 0ます。 positive_modulo(2, -3)->-1。

inline int positive_modulo(int i, int n) {
    int tmp = i % n;
    return tmp ? i >= 0 ? tmp : tmp + n : 0;
}

多くの場合、失敗しn < 0ます。e、g、positive_modulo(-2,-3) --> -5

1例外：Cでは、またはのようにオーバーフローしたa%b場合は定義されません。a/ba/0INT_MIN/-1

于 2019-08-18T12:14:43.353 に答える
3

より大きな型に昇格する余裕がある場合（そしてより大きな型でモジュロを実行する場合）、このコードは単一のモジュロを実行し、次の場合は実行しません。

int32_t positive_modulo(int32_t number, int32_t modulo) {
    return (number + ((int64_t)modulo << 32)) % modulo;
}
于 2018-10-09T16:49:25.247 に答える
3

すべての条件付きパス（上記で生成された条件付き移動を含む）を回避したい場合（たとえば、このコードをベクトル化する必要がある場合、または一定時間で実行する必要がある場合）、符号ビットをマスクとして使用できます。

unsigned modulo(int value, unsigned m) {
  int shift_width = sizeof(int) * 8 - 1;
  int tweak = (value >> shift_width);
  int mod = ((value - tweak) % (int) m) + tweak;
  mod += (tweak & m);
  return mod;
}

クイックベンチの結果は次のとおりです。gccでは一般的なケースの方が優れていることがわかります。clangの場合、clangは一般的な場合にブランチフリーコードを生成するため、一般的な場合と同じ速度です。コンパイラが特定の最適化を生成するために常に信頼できるとは限らず、ベクトルコードのために手動でロールする必要がある場合があるため、この手法は関係なく役立ちます。

于 2020-04-27T21:53:04.813 に答える
2

array[(i+array_size*N) % array_size]Nは正の引数を保証するのに十分な整数ですが、オーバーフローしないように十分に小さい場合も同様に実行できます。

array_sizeが一定の場合、除算なしでモジュラスを計算する手法があります。2つのアプローチの累乗に加えて、ビットグループの加重和に2 ^ i％nを掛けたものを計算できます。ここで、iは各グループの最下位ビットです。

例：32ビット整数0xaabbccdd％100 = dd + cc * [2] 56 + bb * [655] 36 + aa * [167772] 16、最大範囲は（1 + 56 + 36 + 16）* 255 = 27795 。繰り返しのアプリケーションと異なる細分化により、操作をいくつかの条件付き減算に減らすことができます。

一般的な方法には、2 ^ 32 / nの逆数での除算の近似も含まれます。これは通常、かなり広い範囲の引数を処理できます。

 i - ((i * 655)>>16)*100; // (gives 100*n % 100 == 100 requiring adjusting...)
于 2013-02-21T12:09:12.667 に答える
1

2番目の例は最初の例よりも優れています。乗算はif/else演算よりも複雑な演算なので、次のように使用します。

inline int positive_modulo(int i, int n) {
    int tmp = i % n;
    return tmp ? i >= 0 ? tmp : tmp + n : 0;
}
于 2015-09-16T15:10:12.190 に答える