快速计算 (a*b) mod c for c=2^N +-1
在 32 位整数数学中，加法和乘法的基本数学运算是隐式计算 mod 2^32 的，这意味着您的结果将是加法或乘法的最低位。
如果您想使用不同的模数计算结果，您当然可以使用不同语言中任意数量的 BigInt 类。 对于值 a,b,c < 2^32 你可以计算 64 位长整数的中间值，并使用内置的 % 运算符来减少到正确的答案
但我被告知，当 C 是时，有一些特殊的技巧可以有效地计算 a*b mod C形式 (2^N)-1 或 (2^N)+1，不使用 64 位数学或 BigInt 库，并且非常高效，比任意模数评估更高效，并且还可以正确计算通常情况下的情况如果包含中间乘法，则会溢出 32 位 int。
不幸的是，尽管听说这种特殊情况有一个快速评估方法，但我实际上还没有找到该方法的描述。 “这不是高德纳的作品吗？” “这不是维基百科上的某个地方吗？” 是我听到的咕哝。
这显然是随机数生成器中的一种常见技术，随机数生成器执行 a*b mod 2147483647 的乘法，因为 2147483647 是等于 2^31 -1 的质数。
那我就请教一下专家吧。 我找不到任何讨论的这种巧妙的特殊情况乘以 mod 方法是什么？
In 32 bit integer math, basic math operations of add and multiply are computed implicitly mod 2^32, meaning your results will be the lowest order bits of the add or multiply.
If you want to compute the result with a different modulus, you certainly could use any number of BigInt classes in different languages. And for values a,b,c < 2^32 you could compute the intermediate values in 64 bit long ints and use built in % operators to reduce to the right answe
But I've been told that there are special tricks for efficiently computing a*b mod C when C is of the form (2^N)-1 or (2^N)+1, that don't use 64 bit math or a BigInt library and are quite efficient, more so than an arbitrary modulus evaluation, and also properly compute cases which would normally overflow a 32 bit int if you were including the intermediate multiplication.
Unfortunately, despite hearing that such special cases have a fast evaluation method, I haven't actually found a description of the method. "Isn't that in Knuth?" "Isn't that somewhere on Wikipedia?" are the mumblings I've heard.
It apparently is a common technique in random number generators which are doing multiplies of a*b mod 2147483647, since 2147483647 is a prime number equal to 2^31 -1.
So I'll ask the experts. What's this clever special case multiply-with-mod method that I can't find any discussion of?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我认为技巧如下（我将以 10 为基数进行计算，因为这样更容易，但原理应该成立）
假设您要乘以
a*b mod 10000-1，现在
a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32自
x * 10000 ≡ x (mod 10000-1)> [1]，第一项和最后一项变为648+1088。 第二项和第三项是“技巧”出现的地方。请注意：这本质上是一个循环移位。 给出结果 648 + 3618 + 8403 + 1088。还要注意，在所有情况下，相乘的数字都 < 10000（因为 a < 100 且 b < 100），因此如果您只能将多个 2 位数字组合在一起并将它们相加，那么这是可以计算的。
在二进制中，也会有类似的结果。
从a和b开始，都是32位。 假设您想将它们相乘 mod 2^31 - 1，但您只有 16 位乘法器（给出 32 位）。 该算法将是这样的：
已经晚了，所以累加器部分可能无法工作。 我认为原则上这是对的。 有人可以随意编辑此内容以使其正确。
展开后，这也相当快，我猜这就是 PRNG 使用的方法。
I think the trick is the following (I'm going to do it in base 10, because it's easier, but the principle should hold)
Suppose you are multiplying
a*b mod 10000-1, andnow
a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32Since
x * 10000 ≡ x (mod 10000-1)[1], the first and last terms become 648+1088. The second and third terms are where the 'trick' come in. Note that:This is essentially a circular shift. Giving the results of 648 + 3618 + 8403 + 1088. And also note that in all cases, the multiplied numbers are < 10000 (since a < 100 and b < 100), so this is calculable if you only could multiple 2 digit numbers together, and add them.
In binary, it's going to work out similarly.
Start with a and b, both are 32 bits. Suppose you want to multiply them mod 2^31 - 1, but you only have a 16 bit multiplier (giving 32 bits). The algorithm would be something like this:
It's late, so the accumulator part of that probably won't work. I think in principle it's right though. Someone feel free to edit this to make it right.
Unrolled, this is pretty fast, as well, which is what the PRNG use, I'm guessing.
假设您可以将 a*b 计算为
p*2^N+q。 这可能需要 64 位计算，或者您可以将 a 和 b 分成 16 位部分并在 32 位上计算。然后
a*b mod 2^N-1 = p+q mod 2^N-1因为2^N mod 2^N-1 = 1。并且
a*b mod 2^N+1 = -p+q mod 2^N+1因为2^N mod 2^N+1 = -1。在这两种情况下，都不会被
2^N-1或2^N+1除。Suppose you can compute a*b as
p*2^N+q. This can require 64-bit computations, or you can split a and b into 16-bit parts and compute on 32-bits.Then
a*b mod 2^N-1 = p+q mod 2^N-1since2^N mod 2^N-1 = 1.And
a*b mod 2^N+1 = -p+q mod 2^N+1since2^N mod 2^N+1 = -1.In both cases, there is no division by
2^N-1or2^N+1.快速搜索发现了这个： http://home.pipeline.com/ ~hbaker1/AB-mod-N.pdf。 不幸的是，对我来说已经太晚了，无法充分理解这一点，只能写下简化的公式，但它可能在那篇论文的某个地方。
A quick search turned up this: http://home.pipeline.com/~hbaker1/AB-mod-N.pdf. Unfortunately, it's too late for me to make enough sense of that to just write in the simplified formula, but it's probably in that paper somewhere.
您可以使用蒙哥马利缩减（还有其他描述）以减少模乘计算的成本。 不过，这仍然没有使用 N 是正/负 2 的幂的属性。
Rather than doing modular reduction at each step, you can use Montgomery reduction (there are other descriptions) to reduce the cost of modular multiplication calculation. This still doesn't use the properties of N being plus/minus a power of two, though.
您要查找的恒等式为
x mod N = (x mod 2^q)- c*floor(x/2^q)，假设N = 2^q + c且 c 是任意整数（但通常为 ±1）。您可能想阅读 Richard Crandall 和 Carl Pomerance 所著的《素数：计算视角》中的第 9.2.3 节：“特殊形式的模”。 除了理论之外，它还包含实现上述关系的算法的伪代码。
The identity you're looking for is
x mod N = (x mod 2^q)- c*floor(x/2^q), given thatN = 2^q + cand c is any integer (but typically ±1).You may want to read section 9.2.3: "Moduli of special form" in "Prime Numbers: A Computational Perspective" by Richard Crandall and Carl Pomerance. Besides theory, it contains pseudocode for an algorithm implementing the above relation.
我找到了关于这个主题的相当广泛的页面，不仅仅是讨论算法甚至是问题和解决方案的具体历史以及人们使用该解决方案的方式。
I have found a rather extensive page on this very topic, discussing not just the algorithm but even the specific history of the problem and solution and the ways people have used the solution.