Fast multiplication of very large numbers in perl

Question

I have 50,000 numbers (it can vary from 0 to 50,000). And I need (the product of these numbers) MOD 1000000007. The following code is so trivial, there must be other ways. I heard about the “Divide and Win” methods, but I have no idea how to implement it.

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

Please offer.

Answer 1

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

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

A word of caution. For any non-standard module, there is always a risk that your modulo operation will lead to zero, which, of course, will cause complete multiplication by zero. I think you’ve already thought about it, since 1000000007 seems to be a prime number, but I mentioned it anyway.

ETA: Recycling Intermediates:

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

Please note that here you do not need to combine operators.

Answer 2

Although you make $_ % 1000000007 for each number from your array, your $ans can become very large until you finally make $ans %= 1000000007 after looking.

To fix this, I suggest the following:

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

Answer 3

If the reuse of the calculations is important / expected (as indicated in the comment to the TLP answer), then the memoizing function will help speed up, effectively remembering previously calculated results.

See Chapter 3: Higher Order Caching and Substitution in Perl