使用移位和加法对 64 位整数取模 7（32 位有效，但 64 位无效）

Question

我有一个工作实现来计算 32 位无符号整数的 modulo 7，但我在 64 位实现上遇到了问题。 32 位实现来自 this blog post（修复了一些错误）。我能够获得适用于 modulo 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;
}

我做了一个看起来很明显的扩展，它适用于 modulo 3、5 和 15，但对于 mod7，结果到处都是，没有明显的模式（除了结果都在 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. 我一直在尝试一些变体，但我没有得到任何明显更好的东西，我不确定如何完成系统地。

我已经进行了基准测试并表明，在我的环境中使用 shift 和 add 计算 modulo 比梅森数的内置 modulus 运算符更快，这是运行在热路径中的紧密循环中（静态大小循环缓冲区的索引）。这些较低值的除数也比较大的缓冲区大小更常见。

Answer 1

这背后的数学原理实际上非常简单。

（注意数学部分，我使用 a^b 表示 "a to the power b" 不是 "a xor b"。这些数学部分不应该是 C# 代码）

关键技巧是将 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

我们多次应用这个技巧

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

考虑到这一点，您的 "working" Mersene7 似乎不起作用。

我认为：

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;
}

请注意最终比较中值的变化，以及最终总和行的删除。

通过这些更改，我认为 unit 和 ulong 版本都应该产生正确的结果。（虽然还没有测试）

我复制了第二次收缩 - 我不确定是否真的需要它。（这是为了处理溢出 - 但可能不会发生你需要尝试一些值来检查）

在 ulong 情况下，您将需要 a=(a>>48) + a & 0xFFFFFFFFFFFFL 行，就像您已经实现的那样。

使用移位和加法对 64 位整数取模 7（32 位有效，但 64 位无效）

Modulo 7 on 64 bit integer using shift and add (32 bit works but 64 doesn't)

c#

math

optimization

bit-manipulation

modulo