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

Question

私の内側のループでは、配列のサイズを100にしてコードが要素-2を要求するように、「ラップアラウンド」の方法で配列をインデックスする必要があります。 Pythonのような多くの高水準言語では、my_array[index % array_size]で単純にこれを行うことができますが、何らかの理由でCの整数演算（通常）が常に丸められるのではなくゼロに向かって丸められ、結果的にモジュロ演算子が返します負の第1引数が与えられた場合は負の結果になります。

多くの場合、私は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)) 
} 

として分岐せずにそれを行うには、いくつかの「賢い」方法がありますが、私は私のシステム上で最速であるかを調べるためにこれらのプロファイルを作成することができますが、私はすることができます私がより良いものを見逃しているかもしれないことを心配するのを助けるか、または私のマシンで速いものが別のマシンでは遅くなるかもしれないことを助けてください。

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

また、これはおそらく希望の考えですが、自動ベクタライズできるこれを行う方法があれば、それは素晴らしいことでしょう。

Answer 1

モジュロ2のパワー、以下の作品（と仮定すると2の補数表現を補完する）：

return i & (n-1); 

Answer 2

私が学んだ標準的な方法は、この機能は、基本的にabsなしで、あなたの最初の変種である

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

です（実際には、間違った結果を返す）。最適化コンパイラがこのパターンを認識し、それを "符号なしモジュロ"を計算するマシンコードにコンパイルすると、私は驚くことはありません。

編集：

があなたの第二の変形に移る：まず第一に、それはあまりにも、バグが含まれています - n < 0はi < 0する必要があります。

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

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

Answer 3

array[(i+array_size*N) % array_size]でも可能です（Nは正の引数を保証するのに十分な大きさですが、オーバーフローしないように十分小さい）。

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

（1 + 56 + 36 + 16）* 255 = 27795の最大範囲を有する32ビット整数0xaabbccdd％100 = dd + cc * [2] 56 + bb * 36 + aa *反復適用および異なる細分化により、動作をいくつかの条件付き減算に減らすことができる。

一般的なプラクティスには、2^32/nの逆数を持つ除算の近似も含まれます。これは、通常、合理的に大きな範囲の引数を処理できます。

i - ((i * 655)>>16)*100; // (gives 100*n % 100 == 100 requiring adjusting...) 

Answer 4

2の補数の符号ビットの伝播を使用して、オプションの加数を取得するための古い学校の道：

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

Answer 5

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

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