所有值 (a, b, c) 都是ulongs 并且可能會變得非常大（ulong.Max有時也會上升）
我怎樣才能(a * b) % c快速執行。我對模乘法進行了大量研究，但沒有找到任何有用的東西。那么計算這個的（最好是THE）最快的方法是什么？我知道我可以使用BigInteger但BigInteger速度非常慢，所以我不打算使用它。
對我有用的另一件事是 highbits 和 lowbits % c （因為我可以使用Math.BigMul）。但是我找不到任何適用于 64 位的東西（最多 63 位）。
uj5u.com熱心網友回復：
從https://stackoverflow.com/a/18680280/14133865找到并改編的答案
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;
}
uj5u.com熱心網友回復：
如果您的數字decimal很少在范圍內溢位，您可以使用ModuloMultiplication下面的簡單方法：
/// <summary> Returns (a * b) % modulo </summary>
public static ulong ModuloMultiplication(ulong a, ulong b, ulong modulo)
{
ulong high = Math.BigMul(a, b, out ulong low);
return high switch
{
0 => low % modulo,
<= 0xFFFFFFFF => (ulong)((decimal)a * b % modulo),
_ => (ulong)((BigInteger)a * b % modulo),
};
}
此實作使用Math.BigMul方法（.NET 5 及更高版本），以確定操作需要adecimal還是 a BigInteger。
如果您的數字decimal幾乎總是在該范圍內溢位，您可以使用以下演算法實作：
/// <summary> Returns (a * b) % modulo </summary>
public static ulong ModuloMultiplication(ulong a, ulong b, ulong modulo)
{
decimal decimalA = a;
decimal result = decimalA * (b & 0xFFFFFFFF);
result %= modulo;
b >>= 32;
if (b == 0) return (ulong)result;
decimalA *= 0x100000000;
decimalA %= modulo;
result = decimalA * b;
result %= modulo;
return (ulong)result;
}
此實作分兩步執行操作，以克服型別的 96 位限制decimal。它比BigInteger基于 -based 的實作快大約 50% （它在相同的時間內執行 50% 以上的計算），并且它不分配記憶體。
更新：(a * b) % c如果您可以使用本機UInt128型別，操作可能會更快。不幸的是，這種型別不存在。如果你喜歡冒險，你可以使用狄氏.NET數論圖書館由里克Sladkey（MIT許可證），包括該型（有一起Int128）。您可以只下載UInt128.cs代碼檔案，并將其包含在您的專案中。那么你可以這樣做：
public static ulong ModuloMultiplication(ulong a, ulong b, ulong modulo)
{
return (new Dirichlet.Numerics.UInt128(a) * b) % modulo;
}
它比BigInteger我的 PC快 2.5 倍左右，并且不分配記憶體（在釋放模式下）。
此代碼檔案有約 2.700 行代碼。如果您只對(a * b) % c功能感興趣，如果您認為值得付出努力，您可以將其精簡到 200 行左右。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/337038.html
下一篇：沿圓排列圓而不重疊