perl - perl中非常大的数字的快速乘法

Question

我有 50,000 个数字（范围从 0 到 50,000）。我需要（这些数字的乘积）MOD 1000000007。下面的代码太简单了，应该还有其他方法。听说过“分而治之”技术，但不知道如何实施。

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

请建议。

score 7 · Accepted Answer

的结果$num % 1000000007将始终$num适用于小于 1000000007 的所有值。因此，如果其中的所有值@array都在 0 .. 50,000 范围内，则这样的计算是多余的。您必须执行两个步骤，而不是使用*=运算符：

$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

尽管您$_ % 1000000007对阵列中的每个数字都进行了处理，但您$ans可能会变得非常大，直到您最终$ans %= 1000000007在查看之后才这样做。

为了纠正这个问题，我建议如下：

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

score 1 · Accepted Answer

如果计算重用很重要/预期（如对 TLP 答案的评论中所述），那么记忆该函数将有助于通过有效地记住先前计算的结果来加快速度。

3 回答 3