强大的运算能力和模数 [英] power and modulo on the fly for big numbers
问题描述
我将幂b的基数b提高,并将其取模m.
I raise some basis b to the power p and take the modulo m of that.
让我们假设b = 55170或55172,而m = 3043839241(恰好是55171的平方). linux-calculator bc
给出结果(我们需要此来进行控制):
Let's assume b=55170 or 55172 and m=3043839241 (which happens to be the square of 55171). The linux-calculator bc
gives the results (we need this for control):
echo "p=5606;b=55171;m=b*b;((b-1)^p)%m;((b+1)^p)%m" | bc
2734550616
309288627
现在计算55170 ^ 5606会得到一个较大的数字,但是由于我必须进行模运算,因此我可以避免使用BigInt,原因是:
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:
(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
...并且a ^ d = a ^(b + c)= a ^ b * a ^ c,因此我可以将b + c除以2,得出ds d/2和d为偶数或奇数-(d/2),因此对于8 ^ 5,我可以计算8 ^ 2 * 8 ^ 3.
... 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.
因此,我的(有缺陷的)方法总是会随时切断除数,它看起来像这样:
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
}
}
并输入了一些值
powMod (55170, 5606, 3043839241L)
res2: Long = 1885539617
powMod (55172, 5606, 3043839241L)
res4: Long = 309288627
我们可以看到,第二个结果与上面的结果完全相同,但是第一个看起来很安静.我正在做很多这样的计算,只要它们保持在Int的范围内,它们似乎是准确的,但是我看不到任何错误.使用BigInt也可以,但是太慢了:
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:
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
(与bc相同的结果)有人可以看到powMod
中的错误吗?
(same result as with bc) Can somebody see the error in powMod
?
推荐答案
我认为答案在这里:
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
那里有.
这篇关于强大的运算能力和模数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!