Fast multiplication of very large numbers in perl

Question

I have 50,000 numbers (that could range from 0 to 50,000). And I need (product of these numbers) MOD 1000000007. The following code is so trivial, there should be other ways. Heard about "Divide and conquer" techniques, but have no idea how to implement.

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

Please suggest.

Answer 1

The result of $num % 1000000007 will always be $num for all values less than 1000000007. So if all values in @array are within the range 0 .. 50,000, such a calculation is redundant. You would have to do two steps, and not use the *= operator:

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

Word of caution, though. For any non-prime modulo there's always the risk that your modulo operation results in zero, which will of course cause the entire multiplication to produce zero. I think you've already thought of this, since 1000000007 seems to be a prime number, but I'll just mention it anyway.

ETA: Reusing intermediate products:

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

Note that you do not need to compound the operators here.

Answer 2

Although you do $_ % 1000000007 on every number from your array, your $ans can get very large until you finally do $ans %= 1000000007 after the look.

To correct this i suggest the following:

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