scala 大数字的动态幂和模
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2847069/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
power and modulo on the fly for big numbers
提问by user unknown
I raise some basis b to the power p and take the modulo m of that.
我将一些基 b 提高到 p 的幂并取其模 m。
Let's assume b=55170 or 55172 and m=3043839241 (which happens to be the square of 55171). The linux-calculator bcgives the results (we need this for control):
让我们假设 b=55170 或 55172 并且 m=3043839241（恰好是 55171 的平方）。linux-calculatorbc给出了结果（我们需要这个来控制）：
echo "p=5606;b=55171;m=b*b;((b-1)^p)%m;((b+1)^p)%m" | bc
2734550616
309288627
Now calculating 55170^5606 gives a somewhat large number, but since I have to do a modulooperation, I can circumvent the usage of BigInt, I thought, because of:
现在计算 55170^5606 给出了一个有点大的数字，但由于我必须进行模运算，我认为可以绕过 BigInt 的使用，因为：
(a*b) % c == ((a%c) * (b%c))%c i.e.
(9*7) % 5 == ((9%5) * (7%5))%5 =>
63 % 5 == (4 * 2) %5 =>
3 == 8 % 5
... and a^d = a^(b+c) = a^b * a^c, therefore I can divide b+c by 2, which gives, for even or odd ds d/2 and d-(d/2), so for 8^5 I can calculate 8^2 * 8^3.
... 并且 a^d = a^(b+c) = a^b * a^c，因此我可以将 b+c 除以 2，对于偶数或奇数 ds d/2 和 d-(d /2)，所以对于 8^5，我可以计算出 8^2 * 8^3。
So my (defective) method, which always cut's off the divisor on the fly looks like that:
所以我的（有缺陷的）方法总是在运行时切断除数，看起来像这样：
def powMod (b: Long, pot: Int, mod: Long) : Long = {
if (pot == 1) b % mod else {
val pot2 = pot/2
val pm1 = powMod (b, pot2, mod)
val pm2 = powMod (b, pot-pot2, mod)
(pm1 * pm2) % mod
}
}
and feeded with some values,
并以一些价值观为食，
powMod (55170, 5606, 3043839241L)
res2: Long = 1885539617
powMod (55172, 5606, 3043839241L)
res4: Long = 309288627
As we can see, the second result is exactly the same as the one above, but the first one looks quiet different. I'm doing a lot of such calculations, and they seem to be accurate as long as they stay in the range of Int, but I can't see any error. Using a BigInt works as well, but is way too slow:
如我们所见，第二个结果与上面的完全相同，但第一个看起来安静不同。我做了很多这样的计算，只要保持在 Int 的范围内，它们似乎都是准确的，但是我看不到任何错误。使用 BigInt 也可以，但速度太慢：
def calc2 (n: Int, pri: Long) = {
val p: BigInt = pri
val p3 = p * p
val p1 = (p-1).pow (n) % (p3)
val p2 = (p+1).pow (n) % (p3)
print ("p1: " + p1 + " p2: " + p2)
}
calc2 (5606, 55171)
p1: 2734550616 p2: 309288627
(same result as with bc) Can somebody see the error in powMod?
（与 bc 的结果相同）有人可以看到错误powMod吗？
采纳答案by Daniel C. Sobral
I think the answer is here:
我想答案在这里：
scala> math.sqrt(Long.MaxValue).toLong < 3043839241L
res9: Boolean = true
That means you can have a long overflow even for numbers which are less than that particular module value. Let's try to catch it:
这意味着即使对于小于该特定模块值的数字，您也可能会出现长时间溢出。让我们试着抓住它：
scala> def powMod (b: Long, pot: Int, mod: Long) : Long = {
| if (pot == 1) b % mod else {
| val pot2 = pot/2
| val pm1 = powMod (b, pot2, mod)
| val pm2 = powMod (b, pot-pot2, mod)
| val partial = ((pm1 % mod) * (pm2 % mod)).ensuring(res =>
| res > pm1 % mod && res > pm2 % mod, "Long overflow multiplying "+pm1+" by "+pm2)
| partial % mod
| }
| }
powMod: (b: Long,pot: Int,mod: Long)Long
scala> powMod (55170, 5606, 3043839241L)
java.lang.AssertionError: assertion failed: Long overflow multiplying 3042625480 by 3042625480
There you have it.
你有它。
回答by Daniel C. Sobral
Not familiar with Scala, but...
不熟悉Scala，但是...
def powMod (b: Long, pot: Int, mod: Long) : Long = {
if (pot == 1) b % mod else {
val pot2 = pot/2
val pm1 = powMod (b, pot, mod)
val pm2 = powMod (b, pot-pot2, mod)
(pm1 * pm2) % mod
}
}
Did you mean
你的意思是
val pm1 = powMod (b, pot2, mod)
Notice the pot2 instead of pot.
注意pot2而不是pot。
Strangely, it seems that this should loop forever/overflow the stack, but who knows what Scala is doing.
奇怪的是，这似乎应该永远循环/溢出堆栈，但谁知道 Scala 在做什么。
回答by user unknown
Ok fellows, it took me some time, and finally destroyed a long but never proven assumption, which was, that if you multiply two 64-bit-positive integral values (aka: Longs, and practically only 63-bit, after all), you could overrun, and get negative values, but not get an overrun to reach positive (but wrong) values again.
好吧，伙计们，我花了一些时间，最终破坏了一个很长但从未被证明的假设，那就是，如果你将两个 64 位正整数值相乘（又名：Longs，毕竟实际上只有 63 位），您可能会超支并获得负值，但不会超支以再次达到正（但错误）的值。
So I had tried to put a guard into my code, to calculate my value with BigInt, it too big, but the guard was insufficient, because I tested for res < 0. res < pm1 && res < pm2isn't sufficient too.
所以我试图在我的代码中加入一个守卫，用 BigInt 来计算我的价值，它太大了，但守卫是不够的，因为我测试了res < 0. res < pm1 && res < pm2也不够。
To increase the speed I used a mutable.HashMap, and now the code looks like this:
为了提高速度，我使用了 mutable.HashMap，现在代码如下所示：
val MVL : Long = Integer.MAX_VALUE
var modPow = new scala.collection.mutable.HashMap [(Long, Int, Long), Long ] ()
def powMod (b: Long, pot: Int, mod: Long) : Long = {
if (pot == 1) b % mod else modPow.getOrElseUpdate ((b, pot, mod), {
val pot2= pot/2
val pm1 = powMod (b, pot2, mod)
val pm2 = powMod (b, pot-pot2, mod)
val res = (pm1 * pm2)
// avoid Long-overrun
if (pm1 < MVL && pm2 < MVL)
res % mod else {
val f1: BigInt = pm1
val f2: BigInt = pm2
val erg = (f1 * f2) % mod
erg.longValue
}
})
}
You might ask yourself, whether the Long-declared MVL is really needed, or whether a
您可能会问自己，是否真的需要长期申报的 MVL，或者是否需要
if (pm1 < Integer.MAX_VALUE && ...
would have worked too. No. It wouldn't. :) Another trap to avoid. :)
也会起作用。不，不会。:) 另一个要避免的陷阱。:)
Finally it is pretty fast and correct and I learned two lessons about overruns and MAX_VALUE - comparision.
最后，它非常快速和正确，我学到了关于超限和 MAX_VALUE 的两个教训 - 比较。
