perl - perl での非常に大きな数の高速乗算

Question

50,000 個の数字があります (0 から 50,000 の範囲)。そして、(これらの数値の積) MOD 1000000007 が必要です。次のコードは非常に簡単なので、他の方法があるはずです。「分割統治」手法について聞いたことがありますが、実装方法がわかりません。

$ans *= ( $_ % 1000000007 ) foreach @array;
$ans %= 1000000007;

提案してください。

score 7 · Accepted Answer

の結果は、$num % 1000000007常に$num1000000007未満のすべての値になります。したがって、のすべての値@arrayが0 .. 50,000の範囲内にある場合、そのような計算は冗長になります。*=2つの手順を実行する必要があり、演算子は使用しないでください。

$ans = ($ans % 1000000007) * $_ for @array;

ただし、注意が必要です。非素数のモジュロの場合、モジュロ演算の結果がゼロになるリスクが常にあります。これにより、もちろん、乗算全体がゼロになります。1000000007は素数のようですので、もうお気づきだと思いますが、とにかくお話しします。

ETA：中間製品の再利用：

for (@array) {
    $ans *= $_;
    print "Before mod: $ans\n";
    $ans %= 1000000007;
    print "After mod : $ans\n";
}

ここで演算子を合成する必要はないことに注意してください。

score 1 · Accepted Answer

計算の再利用が重要/期待される場合 (TLP の回答へのコメントに記載されているように)、関数のメモ化は、以前に計算された結果を効果的に記憶することでスピードアップに役立ちます。

score 1 · Accepted Answer

$_ % 1000000007配列のすべての数値に対して実行しますが、$ans最終的に見てから実行するまで、非常に大きくなる可能性が$ans %= 1000000007あります。

これを修正するには、次のことをお勧めします。

foreach my $number (@array)
{
  $ans *= ($number % 1000000007);
  $ans %= 1000000007;
}

3 に答える 3