Hacker's Delight を読むことをお勧めします。定数除数の非常に高速な剰余アルゴリズムについて説明します。彼らはほぼ確実に一般的なアルゴリズムを打ち負かします.
更新:ここにいくつかのサンプル コードがあります...おそらく、一時的な long long を回避するために作り直すことができます。
unsigned mod25(unsigned n)
{
unsigned reciprocal = 1374389535; // 2^35 / 25
unsigned div25 = ((unsigned long long)n * reciprocal) >> 35;
return n - div25 * 25;
}
これが私が思いついた別の解決策です:
int mod25(int x){
/* 25 * (all powers of 2 <= INT_MAX), descending */
if (x >= 1677721600) x -= 1677721600;
if (x >= 838860800) x -= 838860800;
if (x >= 419430400) x -= 419430400;
if (x >= 209715200) x -= 209715200;
if (x >= 104857600) x -= 104857600;
if (x >= 52428800) x -= 52428800;
if (x >= 26214400) x -= 26214400;
if (x >= 13107200) x -= 13107200;
if (x >= 6553600) x -= 6553600;
if (x >= 3276800) x -= 3276800;
if (x >= 1638400) x -= 1638400;
if (x >= 819200) x -= 819200;
if (x >= 409600) x -= 409600;
if (x >= 204800) x -= 204800;
if (x >= 102400) x -= 102400;
if (x >= 51200) x -= 51200;
if (x >= 25600) x -= 25600;
if (x >= 12800) x -= 12800;
if (x >= 6400) x -= 6400;
if (x >= 3200) x -= 3200;
if (x >= 1600) x -= 1600;
if (x >= 800) x -= 800;
if (x >= 400) x -= 400;
if (x >= 200) x -= 200;
if (x >= 100) x -= 100;
if (x >= 50) x -= 50;
if (x >= 25) x -= 25;
return x;
}
これは除算や乗算を使用せず、27 回の比較と最大 27 回の減算のみを使用します。
これが機能することを自分で納得させるのは少し難しいですが、機能します (少なくとも x の負でない値の場合)。
上記のコードは実際にはこれを展開したバージョンです:
int mod25(int x){
int divisor;
for(int divisor = 1677721600; divisor >= 25; divisor >>= 1) {
if (x >= divisor) x -= divisor;
}
return x;
}
それをアンロールすることで、ループの比較と、より大きなコードを犠牲にしてシフトを行うことを回避します。必要に応じて、ダフのデバイスを使用して部分的に展開することもできますが、合計で 27 回の反復しかなく、反復ごとに非常に小さなコードしかないため、完全に展開することをお勧めします。
これがどのように機能するかです:すべての負でない整数 x は (n * 25) + k として表すことができます。ここで、n は負でない整数であり、k は 0 から 24 までの整数です。k はたまたま、必要な結果でもあります。したがって、x - (n * 25) を計算できれば、答えが得られます。ただし、前もって n を知らなくても、これを実行できるようにしたいと考えています。
n を 2 進数で考えてみましょう。 1 の各ビットをオフにすることができれば、0 になります。これを行う 1 つの方法は、2 の大きなべき乗から開始し、2 の各べき乗を減算することです。これは、n の現在の値がよりも大きい場合にのみ行われます。またはその 2 の累乗に等しい。
(n * 25) を扱っているので、実際には 2 かける 25 の降べき乗が必要です。k は厳密に 25 未満であり、考慮した最小の除数は 25 であるため、(n * 25) + k.
したがって、それぞれの比較と減算は、n の 1 ビットをゼロにすることであり、最後に残りの k が残ります。
Pax の回答に触発されて、より汎用的なアルゴリズムを作成しました。
int mod(int a, int b) {
int s = b;
while (s <= a) {
s <<= 1;
}
int r = a;
while (r >= b) {
s >>= 1;
if (s <= r) {
r -= s;
}
}
return r;
}
b の 2 乗の倍数を減算します。 a から 結果が見つかるまで。
編集:if を追加 正常に動作させるための条件
例として、これが 100 % 7 を実行している場合、最初に 7 * 2 * 2 * 2 * 2 =112 となります。次に、112 を割ります (s ) を 2 倍し、100 からそれを減算します (r ) (s <= rの場合 ) モジュロが見つかるまでこれを繰り返します。したがって、
s = 112 / 2 = 56, r = 100 - 56 = 44
s = 56 / 2 = 28, r = 44 - 28 = 16
s = 28 / 2 = 14, r = 16 - 14 = 2
したがって、100 % 7 =2