Multiplikation sehr langer Ganzzahlen

Question

Gibt es einen Algorithmus für die genaue Multiplikation zweier beliebig langer Ganzzahlen? Die Sprache, mit der ich arbeite, ist auf eine vorzeichenlose Integer-Länge von 64 Bit beschränkt (maximale Integer-Größe von 18446744073709551615). Realistischerweise würde ich das gerne tun, indem ich jede Zahl zerlege, sie irgendwie mit den unsignierten 64-Bit-Ganzzahlen verarbeite und sie dann wieder zu einer Zeichenkette zusammenfügen könnte (was das Problem des multiplizierten Ergebnisses lösen würde) Lager).

Irgendwelche Ideen?

Answer 1

Die meisten Sprachen haben Funktionen oder Bibliotheken, die dies tun, in der Regel eine Bignum Bibliothek mit dem Namen (GMP ist ein guter.)

Wenn Sie es selbst tun wollen, würde ich es auf die gleiche Weise tun, dass die Menschen lange tun Multiplikation auf Papier. Um dies zu tun, könnten Sie entweder mit Strings arbeiten, die die Zahl enthalten, oder mit binären Operationen binär arbeiten.

Beispiel:

45 
x67 
--- 
315 
+270 
---- 
585 

Oder in binär:

101 
    x101 
    ---- 
    101 
    000 
+101 
------ 
11001 

Edit: Nachdem es in binären tut mir klar, dass es viel einfacher (und schneller natürlich) wäre Code bitweise Operationen anstelle von Strings, die die Basis-10-Nummern enthalten. Ich habe mein binäres Multiplikationsbeispiel bearbeitet, um ein Muster zu zeigen: Für jedes 1-Bit in der unteren Zahl addiere die obere Zahl, bitverschobene linke die Position des 1-Bit mal zu einer Variablen. Am Ende enthält diese Variable das Produkt.

Um das Produkt zu speichern, müssen Sie zwei 64-Bit-Nummern haben und sich vorstellen, dass eine davon die ersten 64 Bits und die andere die zweiten 64 Bits des Produkts sind. Sie müssen Code schreiben, der die Addition von Bit 63 der zweiten Nummer zu Bit 0 der ersten Nummer enthält.

Answer 2

Ja, Sie tun es mit einem Datentyp, der effektiv eine Folge von Ziffern ist (genau wie eine normale 'Zeichenfolge' ist eine Zeichenfolge). Wie Sie dies tun, ist stark sprachabhängig. Zum Beispiel verwendet Java BigDecimal. Welche Sprache verwendest du?

Answer 3

Dies wird oft als Hausaufgabe gegeben. Der Algorithmus, den Sie in der Grundschule gelernt haben, wird funktionieren. Verwenden Sie eine Bibliothek (mehrere sind in anderen Posts erwähnt), wenn Sie dies für eine echte Anwendung benötigen.

Answer 4

Der einfachste Weg wäre, den Schulbuchmechanismus zu verwenden, indem Sie Ihre willkürlich großen Zahlen in 32-Bit-Stücke aufteilen.

Gegeben A B C D * E F G H (jedes Chunk 32 Bit, für insgesamt 128 Bit)
Sie benötigen ein Ausgabearray 9 dwords wide. Setzen Sie [0..8] auf 0

Sie würden damit beginnen: H * D + out [8] => 64-Bit-Ergebnis.
Speichern Sie die niedrigen 32-Bits in out [8] und nehmen Sie die hohen 32-Bits als tragen
Weiter: (H * C) + out [7] + carry
Noch einmal speichern Low 32-Bit in out 7], benutze die hohen 32-Bit als carry
nachdem du H * A + out [4] + carry gemacht hast, musst du weiterschleifen bis du keinen carry hast.

Dann wiederholen mit G, F, E.
Für G würden Sie bei [7] statt bei [8] beginnen und so fort.

Schließlich gehen durch und wandeln die große ganze Zahl in Ziffern (die Routine ein „durch ein einziges Wort teilen große Zahl“ erfordert)

Answer 5

Wenn Sie nicht über eine vorhandene bignum Bibliothek wie GMP verwenden können, überprüfen Wikipedia's article on binary multiplication with computers. Dafür gibt es eine Reihe guter, effizienter Algorithmen.

Answer 6

hier ist mein Code Stück in C. Die gute alte mehrfach Verfahren

char *multiply(char s1[], char s2[]) { 
    int l1 = strlen(s1); 
    int l2 = strlen(s2); 
    int i, j, k = 0, c = 0; 
    char *r = (char *) malloc (l1+l2+1); // add one byte for the zero terminating string 
    int temp; 

    strrev(s1); 
    strrev(s2); 
    for (i = 0;i <l1+l2; i++) { 
     r[i] = 0 + '0'; 
    } 

    for (i = 0; i <l1; i ++) { 
     c = 0; k = i; 
     for (j = 0; j < l2; j++) { 
      temp = get_int(s1[i]) * get_int(s2[j]); 
      temp = temp + c + get_int(r[k]); 
      c = temp /10; 
      r[k] = temp%10 + '0'; 

      k++; 
     } 
     if (c!=0) { 
      r[k] = c + '0'; 
      k++; 
     } 
    } 

    r[k] = '\0'; 
    strrev(r); 
    return r; 
}