сила и модуль на лету для больших чисел - PullRequest
Новая
       20

сила и модуль на лету для больших чисел

5 голосов
/ 17 мая 2010

Я поднимаю некоторый базис b до степени p и беру по модулю m этого.

Давайте предположим, что b = 55170 или 55172 и m = 3043839241 (что является квадратом 55171). Linux-калькулятор bc дает результаты (нам это нужно для контроля): 

echo "p=5606;b=55171;m=b*b;((b-1)^p)%m;((b+1)^p)%m" | bc
2734550616
309288627

Теперь вычисление 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

... и 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 
      } 
}

и подается с некоторыми значениями 

powMod (55170, 5606, 3043839241L) 
res2: Long = 1885539617
powMod (55172, 5606, 3043839241L) 
res4: Long = 309288627

Как мы видим, второй результат точно такой же, как приведенный выше, но первый выглядит совершенно иначе. Я делаю много таких вычислений, и они кажутся точными, пока они находятся в диапазоне 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

(тот же результат, что и для bc) Может кто-нибудь увидеть ошибку в powMod?

Ответы [ 3 ]

4 голосов
/ 17 мая 2010

Я думаю, что ответ здесь: 

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

Вот, пожалуйста.

2 голосов
/ 17 мая 2010

Не знаком со 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)

Обратите внимание на горшок 2 вместо банка.

Странно, но кажется, что это должно постоянно зацикливаться / переполнять стек, но кто знает, что делает Scala.

1 голос
/ 18 мая 2010

Хорошо, ребята, это заняло у меня некоторое время и, наконец, уничтожило длинное, но никогда не доказанное предположение, а именно: если вы умножите два 64-битных положительных целых значения (иначе говоря, Longs и практически только 63-битные все), вы можете переполнить и получить отрицательные значения, но не получить переполнение для достижения положительных (но неправильных) значений снова.

Итак, я попытался установить защиту в свой код, чтобы вычислить мое значение с помощью BigInt, оно слишком большое, но защиты было недостаточно, потому что я проверял на res < 0. res < pm1 && res < pm2 тоже недостаточно.

Для увеличения скорости я использовал 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 - сравнении.

...