Große Zahlen multiplizieren

Wissenschaft Physik
1

Hallo,

mein Problem ist, dass ich zwei große Zahlen x und y mit jeweils z.B. 20 Stellen miteinander multiplizieren programmatisch muss, und dass der Interpreter das nicht mehr auf die Reihe bekommt.

Meine Frage ist nun, ob es irgendeine Möglichkeit gibt, diese Multiplikation zu umschiffen, so dass nicht mit so großen Zahlen multipliziwert werden muss, z.B. dadurch das Teilergebnisse addiert werden. (Wir nehmen an, Addieren von kleinen Zahlen zu großen geht!)

Nun kann ich z.B. 1000*2000 rechnen, indem ich 1000 mal 2000 addiere. Dabei werd ich aber bestimmt verblöden (oder zumindest mein Programm…)
In diesem Fall wäre 10 mal 10*2000 zu rechnen eine Lösung - aber dazu müsst ich die Zahlen vorher ja kennen… :frowning:

hat jemand vielleicht ne Idee? Hab auch schon an andere Zahlensystem gedacht (z.B. ist eine Binäre Zahl ja durch eine einfach Verschiebung um eine Stelle nach links blitzschnell mit 2 multipliziert. Oder eine Hex-Zahl mal 16, etc…)
Oder mit irgendeiner Lösung mit boolschen Operationen?

Danke für alle Antworten,
Gruss
Datz

2

Hallo,

mein Problem ist, dass ich zwei große Zahlen x und y mit
jeweils z.B. 20 Stellen miteinander multiplizieren
programmatisch muss, und dass der Interpreter das nicht mehr
auf die Reihe bekommt.

Mit welcher Programmiersprache machst du das denn? long ints müßten 20 Stellen schon noch schaffen.

Ansonsten gibt es Bibliotheken für sowas, manche Programmiersprachen können das auch so schon (z.B. perl mit use bigint; Scheme kann das ohne weiteren Aufwand).

Beschreib mal genauer was du machen willst, ev. gibt es für deinen Spezialfall auch einfacherer Lösungen.

Grüße,
Moritz

3

Hallo zurück,

das hatte ich vor vielen Jahren mal an der Uni als Übungsaufgabe. Gelöst habe ich es damals so:

Zahlen als String abspeichern, dann die Multiplikation auf diesem Datentyp selbst programmieren. Der Algorithmus ist einfaches Kaufmannsrechnen, also die aus der Schule bekannte schriftliche Multiplikation. Dafür musst Du allerdings vorher die Addition programmieren. Sicherlich nicht die effizienteste Lösung, aber funktioniert …

Gruß & Spaß

Ted

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

4

Hallo,

ich sehe da zwei Möglichkeiten:

  1. Möglichkeit. Hier ist das Ergebnis möglicherweise nicht 100 % exakt, aber doch ziemlich genau und somit vielleicht brauchbar. Diese Möglichkeit eröffnet sich, wenn dein Rechner Logarithmen zu einer bestimmten Basis x (z.B. x=10 oder x=e=Eulersche Zahl) berechnen und auch potenzieren kann.

Dann gilt nämlich logx(a*b) = logxa + logxb

und somit a*b = x hoch logx(a*b) = x hoch (logxa + logxb)

Nach diesem Prinzip arbeitet übrigens ein althergebrachter Rechenschieber. Ich was gar nicht, ob das Ding heute noch bekannt ist.

  1. Möglichkeit. Wenn dein Rechner das Definieren von Feldern zuläßt, schreibst du dir zunächst ein Teilprogramm, das die beiden zu multiplizierenden Zahlen in eine Folge von Ziffern zerlegt, z.B. 12345 in 1 2 3 4 5. Indem du den Logarithmus zur Basis 10 von der umzuwandelnden Zahl ermittelst und von dieser Zahl die Nachkommastellen abschneidest, erhältst du die Zahl der Stellen = n. Dann dividierst du die Zahl durch 10 hoch n und schneidest den Rest ab = 1. Stelle, dann von der Zahl 1. Stelle * 10 hoch n abziehen und durch 10 hoch (n-1) dividieren usw.

Dann schreibst du dir ein weiteres Teilprogramm, das genau so eine Multiplikation der einzelnen Stellen der beiden zerlegten Zahlen ausführt, wie du die beiden Zahlen mit Papier und Bleistift multiplizieren würdest. Zum Schluß wandelst du die erhaltene Ziffernfolge mit einem weiteren Teilprogramm wieder in eine numerische Zahl um (durch sukzessive Multiplikation von der höchsten bis zur niedrigsten Zehnerpotenz). Wenn der Computer von dem letzten Schritt überfordert ist (wegen zu geringer Stellenanzahl), kannst du auch die Ziffernfolge als Ergebnis ausdrucken und dann manuell weiterverarbeiten.

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

5

off topic
Hallo,

Nach diesem Prinzip arbeitet übrigens ein althergebrachter
Rechenschieber. Ich was gar nicht, ob das Ding heute noch
bekannt ist.

Klar, manche Parkscheiben haben auf der Rückseite einen Rechenschieber, naja eher Rechendreher, der den Benzinverbrauch berechnet, der benutz genau das Prinzip (nur weiss das kaum noch jemand).

Gruß Volker

6

Hallo,

mein Problem ist, dass ich zwei große Zahlen x und y mit
jeweils z.B. 20 Stellen miteinander multiplizieren
programmatisch muss, und dass der Interpreter das nicht mehr
auf die Reihe bekommt.

Meine Frage ist nun, ob es irgendeine Möglichkeit gibt, diese
Multiplikation zu umschiffen, so dass nicht mit so großen
Zahlen multipliziwert werden muss, z.B. dadurch das
Teilergebnisse addiert werden. (Wir nehmen an, Addieren von
kleinen Zahlen zu großen geht!)

Hallo,

was noch gehen muss, ist das Verschieben um ganze Stellen bzw. die Multiplikation mit 10er-Potenzen - bei der üblichen schriftlichen Rechentechnik einfach durch die Schreibweise *10 = 1 Stelle weiter links. Dann kann man die Multiplikation aufteilen, z.B. statt 4stellig nur 2stellig:

 1234 \* 2345
 (12\*100 + 34) \* (23\*100 + 45)
 12\*23\*10000 + 12\*45\*100 + 34\*23\*100 + 34\*45
 
 0276
 0540
 0782
 1530
 ========
 02893730

Das lässt sich natürlich für beliebige Schiebefaktoren und Stellenzahlen erweitern, so wie im Beispiel ist es zwar einsichtig, aber wegen des Dezimalsystems für den Rechner weniger geeignet.

Gruss Reinhard

7
  1. Möglichkeit. Wenn dein Rechner das Definieren von Feldern
    zuläßt, schreibst du dir zunächst ein Teilprogramm, das die
    beiden zu multiplizierenden Zahlen in eine Folge von Ziffern
    zerlegt, z.B. 12345 in 1 2 3 4 5. Indem du den Logarithmus zur
    Basis 10 von der umzuwandelnden Zahl ermittelst und von dieser
    Zahl die Nachkommastellen abschneidest,

(… und noch 1 addieren ! - aber da wärest du bestimmt auch drauf gekommen)

erhältst du die Zahl
der Stellen = n. Dann dividierst du die Zahl durch 10 hoch n
und schneidest den Rest ab = 1. Stelle, dann von der Zahl 1.
Stelle * 10 hoch n abziehen und durch 10 hoch (n-1) dividieren
usw.

8

schöne Idee. Sehr einfach umzusetzen, zwar etwas langsam aber funktioniert garantiert mit (fast) jeder beliebig langen Zahl.
Und Probleme mit Additionen von zu großen Zahlen können auch auf keinen Fall auftreten…

Danke
Dirk

9

Danke an alle, die sich Gedanken gemacht haben. Waren recht nette Ideen dabei und ich konnte das Problem jetzt lösen!

Gruss
Datz