如何快速执行 (a * b) % c，其中 a、b、c 是 ulong，通常很大

Question

所有值 (a, b, c) 都是 ulong 并且可以变得相当大（它们有时也会上升到 ulong.Max）

如何使 (a * b) % c 执行得更快。我对模乘法做了一大堆研究，但没能找到任何有用的东西。那么什么是（最好是 THE）最快的计算方法呢？我知道我可以使用 BigInteger 但 BigInteger 太慢了，所以我不会使用它。

另一件对我有用的事情是高位和低位 % c（因为我可以使用 Math.BigMul）。但是我还没有找到任何适用于 64 位的东西（最多 63 位）。

Answer 1

这是一个相当快速的实现，它使用 Math.BigMul 方法（.NET 5 及更高版本）和 decimal 数据类型：

/// <summary> Returns (a * b) % modulo </summary>
public static ulong ModuloMultiplication(ulong a, ulong b, ulong modulo)
{
    ulong high = Math.BigMul(a, b, out var low);
    if (high == 0) return low % modulo;
    if (high <= 0xFFFFFFFF) return (ulong)(((decimal)a * b) % modulo);
    decimal remainder = high;
    remainder *= 0x100000000;
    remainder += low >> 32;
    remainder %= modulo;
    remainder *= 0x100000000;
    remainder += low & 0xFFFFFFFF;
    remainder %= modulo;
    Debug.Assert((BigInteger)remainder == ((BigInteger)a * b) % modulo); // Validation
    return (ulong)remainder;
}

此实现分两步执行操作，以克服 decimal 类型的 96 位限制。它几乎比使用 BigInteger 类型快 2 倍，而且它不分配内存。如果两个数的乘积在小数范围内，则一步得出结果。

对于不依赖于 Math.BigMul 方法的类似但稍慢的实现（此答案的source code), you can look at the 4th revision。

更新： 如果您可以使用本机 UInt128 类型，(a * b) % c 操作可能会更快。不幸的是，这种类型 does not exist. If you are feeling adventurous you could use the Dirichlet .NET Number Theory Library by Rick Sladkey (MIT License), that includes this type (along with the Int128). You could just download the UInt128.cs 代码文件，并将其包含在您的项目中。那么你可以这样做：

public static ulong ModuloMultiplication(ulong a, ulong b, ulong modulo)
{
    return (new Dirichlet.Numerics.UInt128(a) * b) % modulo;
}

它比我 PC 中的 BigInteger 快大约 2.5 倍。

此代码文件包含约 2.700 行代码。如果您只对 (a * b) % c 功能感兴趣，您可以将其精简到 150 行左右，如果您认为这样做值得的话。

Answer 2

已找到并改编自

的答案

public static ulong ModMul(ulong a, ulong b, ulong modulus)
{
    ulong result = 0UL;

    if (b >= modulus)
    {
        if (modulus > 0x7FFFFFFFFFFFFFFF)
        {
            b -= modulus;
        }
        else
        {
            b %= modulus;
        }
    }

    while (a != 0UL)
    {
        if ((a & 1UL) != 0UL)
        {
            if (b >= modulus - result)
            {
                result -= modulus;
            }

            result += b;
        }

        a >>= 1;

        ulong temp = b;

        if (b >= modulus - b)
        {
            temp -= modulus;
        }

        b += temp;
    }

    return result;
}

如何快速执行 (a * b) % c，其中 a、b、c 是 ulong，通常很大

How to perform (a * b) % c fast, where a,b,c are ulong, and usually pretty big

c#

math

performance

mod