perlで非常に大きな数値を高速に乗算する

Question

私は50,000の数字（0〜50,000の範囲）を持っています。そして、私は（これらの数字の積）MOD 1000000007が必要です。次のコードはそれほど簡単ではありません。 「分割して克服する」テクニックについて聞いたことがありますが、どのように実装するかはわかりません。

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

お勧めします。

Answer 1

アレイのすべての番号で$_ % 1000000007を実行しますが、最後に$ans %= 1000000007を実行するまで、$ansは非常に大きくなる可能性があります。

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

Answer 2

@array内のすべての値が範囲0内にある場合$num % 1000000007の結果は常に少ない1000000007.よりだから、すべての値について$numになります... 50,000、こうした：私は次のことを提案し、これを修正するには

計算は冗長です。あなたは、2つのステップを行う必要はなく、*=演算子使用します。しかし、注意の

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

Wordを。非プライムモジュロの場合、常にモジュロ演算の結果がゼロになるというリスクがありますが、乗算全体がゼロになることはもちろんです。私は1000000007が素数であるように思われるので、あなたはすでにこれを考えていたと思いますが、とにかく言及します。

ETA：中間製品の再利用：あなたがここに演算子を配合する必要はありません

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

注意。

Answer 3

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

はChapter 3: Caching and Memoization in Higher-Order Perl