5

ある基底 b を p 乗し、そのモジュロ m をとります。

b=55170 または 55172 で、m=3043839241 (たまたま 55171 の 2 乗) とします。linux-calculatorbcは結果を返します (制御のためにこれが必要です):

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

ご覧のとおり、2 番目の結果は上記の結果とまったく同じですが、最初の結果は静かに異なって見えます。私はそのような計算をたくさん行っており、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?

4

3 に答える 3

4

答えはここにあると思います：

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

そこにあります。

于 2010-05-17T15:27:15.610 に答える
2

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)

pot の代わりに pot2 に注意してください。

奇妙なことに、これは永遠にループする/スタックをオーバーフローするように思われますが、Scala が何をしているのかは誰にもわかりません。

于 2010-05-17T06:39:44.740 に答える
1

OK フェロー、それには少し時間がかかり、最終的に長いが証明されたことのない仮定を破壊しました。オーバーランして負の値を取得することはできますが、オーバーランして正の (ただし間違った) 値に再び達することはありません。

そこで、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 && ...

も働いたでしょう。いいえ、そうではありません。:) 回避すべきもう 1 つのトラップ。:)

最後に、それは非常に高速で正確であり、オーバーランと MAX_VALUE - 比較に関する 2 つの教訓を学びました。

于 2010-05-18T02:52:34.557 に答える