C コンパイラが除算命令のない CPU をターゲットにしている場合は、次のようにコードを変更できます。
mod(a, b) {
int s = b + b + b + b;
int r = a;
while(r >= s) {
r -= s;
}
while(r >= b) {
r -= b;
}
return r;
}
これは、値を 1 ではなく 4 のチャンクで減算することによって機能し、最後の値までは、1 のチャンクの減算に切り替わります。
これにより、コードが約 4 倍速く実行されるはずです (4*b整数の範囲外ではないことを前提としています)。さらに高速化するために、ループ8*bの前に複数のループ (1 つなど) を挿入することもできます。4*b
それ以外には、アセンブラーのハンドコーディングが役立つかもしれませんが、それがなくても上記のコードからかなりのブーストが得られると思います。
mod 呼び出しの使用方法について詳しく知っている場合は、特定のケースに合わせて最適化できます。たとえば、16 ビット整数のモジュロ 25 だけを知りたい場合、次のコードは変数分母を使用した単純なループよりもはるかに高速です。
int mod25 (int a) { // a has maximum value of 2^15-1 = 32767
while (a >= 15625) a-= 15625; // at most 2 times.
while (a >= 625) a-= 625; // at most 24 times.
while (a >= 25) a-= 25; // at most 24 times.
return a;
}
%テストを実行すると、モジュロ コードと演算子の使用 (2 秒対 0 秒)の間に顕著な違いが現れるまでに、1000 万回の反復を実行する必要があることがわかりました。その時点までは両方とも 0 秒でしたが、これは高速なマシン (より優れているmod25) と命令div(オペレーターにとってより優れている) で実行された%ため、独自のハードウェアでベンチマークする必要があります。
これは、コードを読めなくすることなく得られる可能性が高い速度とほぼ同じです (ただし、それがどのように機能するかを説明するコメントをたくさん追加したい場合は、それでも停止することはありません)。
分母のより一般的な解決策は、最初に分母を可能な限り 2 倍にし (速度のためにビット シフトを使用)、その後の減算が最小になるようにすることです。次に、分子が増加した分母を下回ったら、分母を半分にして続行します (分母が最初に戻るまで)。
int mod (int n, int d) {
/* dx is the adjusted denom, don't let it overflow though. */
int dx = d;
while (((dx << 1) >>1) == dx)
dx <<= 1;
/* This loop processes the dx values until they get too small. */
while (dx >= d) {
/* This loop subtracts the large dx value. */
while (n >= dx)
n -= dx;
dx >>= 1;
}
return n;
}
mod25これは、より一般的なソリューションを提供しながら、実際には上記の最適化されたバージョンと同等のパフォーマンスを発揮します。