Schnelle Multiplikation sehr großer Zahlen in Perl

Question

Ich habe 50.000 Zahlen (die von 0 bis 50.000 reichen könnten). Und ich brauche (das Produkt dieser Zahlen) MOD 1000000007. Der folgende Code ist so trivial, es sollte andere Wege geben. Habe von "Teile und herrsche"-Techniken gehört, aber keine Ahnung, wie man das umsetzt.

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

Bitte um Vorschläge.

Answer 1

Das Ergebnis von $num % 1000000007 wird für alle Werte kleiner als 1000000007 immer $num sein. Wenn also alle Werte in @array im Bereich von 0 bis 50.000 liegen, ist eine solche Berechnung redundant. Sie müssten zwei Schritte durchführen und den *=-Operator nicht verwenden:

$ans = ($ans % 1000000007) * $_ für @array;

Ein Wort der Vorsicht jedoch. Bei einem nicht primen Modulowert besteht immer die Gefahr, dass Ihre Moduloberechnung null ergibt, was natürlich zur Folge hat, dass die gesamte Multiplikation null produziert. Ich denke, Sie haben bereits daran gedacht, da 1000000007 eine Primzahl zu sein scheint, aber ich möchte es trotzdem erwähnen.

ETA: Wiederverwendung von Zwischenprodukten:

für (@array) {
    $ans *= $_;
    print "Vor Modulo: $ans\n";
    $ans %= 1000000007;
    print "Nach Modulo: $ans\n";
}

Beachten Sie, dass Sie die Operatoren hier nicht zusammensetzen müssen.

Answer 2

Auch wenn Sie $_ % 1000000007 auf jede Zahl aus Ihrem Array anwenden, kann Ihr $ans sehr groß werden, bis Sie schließlich $ans %= 1000000007 am Ende der Schleife machen.

Um dies zu korrigieren, schlage ich Folgendes vor:

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

Answer 3

Wenn die Wiederverwendung von Berechnungen wichtig/erwartet wird (wie in einem Kommentar zu TLP's Antwort erwähnt), dann wird die Speicherung der Funktion dazu beitragen, die Geschwindigkeit zu erhöhen, indem zuvor berechnete Ergebnisse effektiv gespeichert werden.

Siehe Kapitel 3: Caching und Memoization in Higher-Order Perl