CODEWITHSUNDEEP
perlmathmultiplicationlargenumber
trinity
trinity

Reputation: 10484

Fast multiplication of very large numbers in perl

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.

Upvotes: 4

Views: 824

Answers (3)

Zaid
Zaid

Reputation: 37146

If computational reuse is important/expected (as mentioned in a comment to TLP's answer), then memoizing the function will help speed up by effectively remembering previously calculated results.

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

Upvotes: 1

TLP
TLP

Reputation: 67908

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.

Upvotes: 7

NiklasMM
NiklasMM

Reputation: 2972

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;
}

Upvotes: 1

Related Questions