питание и по модулю на лету для больших чисел
Я повышаю некоторое основание b до питания p и беру модуль m этого.
Давайте примем b=55170 или 55172 и m=3043839241 (который, оказывается, квадрат 55 171). Калькулятор Linux bc дает результаты (нам нужно это для управления):
echo "p=5606;b=55171;m=b*b;((b-1)^p)%m;((b+1)^p)%m" | bc
2734550616
309288627
Теперь вычисление 55170^5606 дает несколько большое количество, но так как я должен сделать modulooperation, я могу обойти использование 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
... и a^d = a^ (b+c) = a^b * a^c, поэтому я могу разделить b+c на 2, который дает, для даже или нечетный ds d/2 и d-(d/2), таким образом, для 8^5 я могу вычислить 8^2 * 8^3.
Так мой (дефектный) метод, который всегда сокращение от делителя на лету похоже на это:
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
}
}
и feeded с некоторыми значениями,
powMod (55170, 5606, 3043839241L)
res2: Long = 1885539617
powMod (55172, 5606, 3043839241L)
res4: Long = 309288627
Как мы видим, вторым результатом является точно то же как то выше, но первые взгляды, тихие отличающийся. Я делаю много таких вычислений, и они, кажется, точны, пока они остаются в диапазоне Интервала, но я не вижу ошибки. Используя 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
(тот же результат как с до н.э), Может кто-то видеть ошибку в powMod?
3 ответа
Я думаю, что ответ здесь:
scala> math.sqrt(Long.MaxValue).toLong < 3043839241L
res9: Boolean = true
Это означает, что у вас может быть долгое переполнение даже для чисел, которые меньше, чем это конкретное значение модуля. Попробуем его поймать:
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
Вот и все.
Не знаком со 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
}
}
Вы имели в виду
val pm1 = powMod (b, pot2, mod)
Обратите внимание на pot2 вместо pot.
Как ни странно, кажется, что это должно постоянно зацикливаться / переполнять стек, но кто знает, что делает Scala.
Ладно, ребята, мне потребовалось некоторое время, и я наконец разрушил длинное, но так и не доказанное предположение, которое заключалось в том, что если вы умножите два 64-битных положительных целочисленных значения (также известные как Longs и в конце концов, практически только 63-битный), вы могли бы переполниться и получить отрицательные значения, но не получить переполнение, чтобы снова достичь положительных (но неправильных) значений.
Итак, я попытался поставить защиту в свой код, чтобы вычислить мое значение с помощью BigInt, оно слишком велико, но защиты оказалось недостаточно, потому что я тестировал на res <0 . res
Чтобы увеличить скорость, я использовал 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
}
})
}
Вы можете спросить себя, действительно ли нужен давно объявленный MVL или
if (pm1 < Integer.MAX_VALUE && ...
тоже сработал бы . Нет, не будет. :) Еще одна ловушка, которую следует избегать. :)
Наконец, это довольно быстро и правильно, и я извлек два урока о переполнении и MAX_VALUE - сравнении.