シフトと加算を使用する64ビット整数のモジュロ7

Question

32ビットの符号なし整数の7のモジュロを計算するための実装がありますが、64ビットの実装に問題があります。 32ビットの実装はthis blog post（いくつかのバグ修正があります）でした。私はモジュロ3、5、15、6では動作しますが、7では動作しない64ビット版を手に入れることができました。数学は私の頭を少し上回っています。

参考として、here is a gist with the full codeです。

はここで働いて32ビットです：

static public uint Mersenne7(uint a) 
{ 
    a = (a >> 24) + (a & 0xFFFFFF); // sum base 2**24 digits 
    a = (a >> 12) + (a & 0xFFF); // sum base 2**12 digits 
    a = (a >> 6) + (a & 0x3F);  // sum base 2**6 digits 
    a = (a >> 3) + (a & 0x7);  // sum base 2**2 digits 
    a = (a >> 2) + (a & 0x7);  // sum base 2**2 digits 
    if (a > 5) a = a - 6; 
    return a; 
} 

私は明白なモジュロ3、5のために働い拡張、および15のように思えたものを作ったが、MOD 7のために結果がまったくないと場所を超えています

static public ulong Mersenne7(ulong a) 
{ 
    a = (a >> 48) + (a & 0xFFFFFFFFFFFF); // sum base 2**48 digits 
    a = (a >> 24) + (a & 0xFFFFFF); // sum base 2**24 digits 
    a = (a >> 12) + (a & 0xFFF); // sum base 2**12 digits 
    a = (a >> 6) + (a & 0x3F);  // sum base 2**6 digits 
    a = (a >> 3) + (a & 0x7);  // sum base 2**2 digits 
    a = (a >> 2) + (a & 0x7);  // sum base 2**2 digits 
    if (a > 5) a = a - 6; 
    return a; 
} 

64ビットのために同じ技術が明らかにMOD 7.私はいくつかのバリエーションをしようとしてきたために動作しませんが、私は著しく、より良いものを得ることはありません：明白なパターン（結果以外のすべての7の下にあります）私はそれを体系的にどのように処理するのか分かりません。

私がシフトを使用して剰余を計算し、メルセンヌ番号を追加する（私の環境での弾性率がオペレータに建てられ、これは熱いパスにタイトなループ内で実行されているインデックスよりも高速であることをベンチマークと示されています静的なサイズの循環バッファへ）。これらのより小さい値の除数は、より大きなバッファサイズよりも一般的です。

Answer 1

この背後にある数学は実際にはかなり簡単です。

（私はこれらの数学の部分はC＃のコードであるために仮定されていない。ない 「のxor B」「電源bに」を意味するa^bを使用している数学の一部に注意してください）

キーのトリックあなたが二つにaを分割することであるので、

a = b * 2^3 + c 

どこb = a/2^3 = a >> 3とその後c = a mod 2^3 = a & 0x7

a mod 7 = ((b mod 7) * (2^3 mod 7) + c) mod 7 

しかし2^3 mod 7 = 1はそう

a mod 7 = (b mod 7 + c) mod 7 = (b + c) mod 7 

私たちは、それはあなたの "作業" Mersene7が動作しないように見えるこのことを念頭に

1 = 2^3 mod 7 = 2^6 mod 7 = 2^12 mod 7 = 2^24 mod 7 = 2^48 mod 7 

を使用して、このトリックを数回適用します。

私はこれだと思う：

static public uint Mersenne7(uint a) 
{ 
    a = (a >> 24) + (a & 0xFFFFFF); // sum base 2**24 digits 
    a = (a >> 12) + (a & 0xFFF); // sum base 2**12 digits 
    a = (a >> 6) + (a & 0x3F);  // sum base 2**6 digits 
    a = (a >> 3) + (a & 0x7);  // sum base 2**2 digits 
    a = (a >> 2) + (a & 0x7);  // sum base 2**2 digits 
    if (a > 5) a = a - 6; 
    return a; 
} 

が

static public uint Mersenne7(uint a) 
{ 
    a = (a >> 24) + (a & 0xFFFFFF); // sum base 2**24 digits 
    a = (a >> 12) + (a & 0xFFF); // sum base 2**12 digits 
    a = (a >> 6) + (a & 0x3F);  // sum base 2**6 digits 
    a = (a >> 3) + (a & 0x7);  // sum base 2**3 digits 
    a = (a >> 3) + (a & 0x7);  // sum base 2**3 digits 
    if (a >= 7) a = a - 7; 
    return a; 
} 

最終比較して値が変化し、最終合計行の除去に注意する必要があります。

これらの変更により、ユニットとulongの両方のバージョンで正しい結果が得られるはずです。 （しかし、テストしていない）

私は2番目の収縮を複製しました - 私はそれが実際に必要かどうかはわかりません。 （オーバーフローを処理することですが、チェックするために値を試してみる必要はありません）

ulongの場合は、既に実装したようにa=(a>>48) + a & 0xFFFFFFFFFFFFL行が必要です。