Hallo Foren-Gemeinde,
wenn man eine Multiplikation durchführen möchte, aber durch die
zugrundeliegende Maschine dahingehend eingeschränkt ist, dass die
Maschine nicht den kompletten Wert auf einmal mit einem anderen Wert
verrechnen kann, dann besteht ja der übliche Ansatz darin, dass man den
Wert aufteilt und die Teile einzeln verrechnet.
Üblicherweise sind die Teile "1 Byte"-, "2 Byte"- oder "4 Byte"-groß.
Ein "1 Byte"-großer Wert kann eine Zahl zwischen 0 und 255 sein. Man
könnte daher ein Beispiel dahingehend vereinfachen, dass man einen Teil
als einen Wert zwischen 0 und 9 ansieht und dann eine Dezimalzahl in
seine Dezimalstellen auftrennt.
Beispiele:
1
12 * 34 = 408
entspricht in Einzelschritten (4 Multiplikationen + 3 Additionen):
1
2 * 4 = 8
2
+ 2 * 30 = 60
3
+ 10 * 4 = 40
4
+ 10 * 30 = 300
5
---------------
6
== 408
1
123 * 456 = 56.088
entspricht in Einzelschritten (9 Multiplikationen + 8 Additionen):
1
3 * 6 = 18
2
+ 3 * 50 = 150
3
+ 3 * 400 = 1.200
4
+ 20 * 6 = 120
5
+ 20 * 50 = 1.000
6
+ 20 * 400 = 8.000
7
+ 100 * 6 = 600
8
+ 100 * 50 = 5.000
9
+ 100 * 400 = 40.000
10
--------------------
11
== 56.088
1234 * 5678 führt nach dem selben Schema zu 16 Multiplikationen und 15
Additionen.
Entsprechend ist der Aufwand, um eine Mehrwort-Multiplikation nach
diesem Schema durchzuführen quadratisch von der Anzahl der
Einzelteile/Wörter abhängig.
Nun möchte ich 2 Ganzzahlen miteinander multiplizieren, welche jeweils
aus bis zu 64 Wörtern bestehen (bei der gegebenen Maschine). Es wären
also nach dem bisherigen Schema 4.096 Multiplikationen und 4.095
Additionen notwendig. Ich hoffe, dass nun das Problem definiert wurde.
Kann mir jemand einen Ansatz nennen, wie es möglich ist, dafür zu
sorgen, dass der Aufwand zur Durchführung einer Mehrwort-Multiplikation
reduziert wird?
Vielen Dank!
Gruß,
Joker.
Z=A[n]*B
Label1:
ist LSB von A 1 dann:
Addiere B zu Z
schiebe Z 1bit links
schiebe A 1bit rechts
solange A>0 jump Label1
hole nächstes A
Alle Multiplikatoren geholt?
wenn nein
B:=Z
jump Label1
ende
Mit linearem Aufwand ist das nicht möglich, aber es geht besser als dein
Quadratischer (n^2).
Noch einigermaßen verständlich und so ziemlich der schnellste
Algorithmus (n^1,58...) wäre z.B. der Karazuba-Algorithmus
https://de.wikipedia.org/wiki/Karazuba-Algorithmus
Es gibt noch ein paar etwas schnellere (sind auch im Wiki verlinkt), die
versteht man aber ohne Mathestudium eher nicht...
Joe K. schrieb:> Kann mir jemand einen Ansatz nennen, wie es möglich ist,> dafür zu sorgen, dass der Aufwand zur Durchführung einer> Mehrwort-Multiplikation reduziert wird?
Ja.
Wieder einmal helfen die Russen weiter: Das Zauberwort
heisst "Karazuba-Multiplikation".
Kernidee: Man kann (10*a+b)*(10*c+d) durch Ausmultiplzieren
und geschicktes Zusammenfassen so umformen, dass man mit DREI
(statt vier) Teilmultiplikationen auskommt. Diese Idee kann
man rekursiv auf die Teilprodukte anwenden.
Wikipädie liefert weiterführende Verweise, u.a. auf die
Toom-Cook- und zum Schönhage-Strassen-Algorithmen; die
Erklärung des Karazuba-Verfahrens finde ich dort allerdings
komplett unverständlich.
Ich danke allen für die Antworten. Es braucht aber wohl ein bischen Zeit
bis ich auf eurem Stand bin :-) Ich werde mal nach brauchbaren Quellen
suchen, welche den Algorithmus dokumentiert haben.
Der Wikipedia-Artikel ist Müll, da er haufenweise unnötigen Balast
enthält. Ich kann nicht mal eben ein Master-Studium in Mathematik
nachholen nur um eine Multiplikation programmiertechnisch zu
implementieren.
@Heinz V.: Ist der Pseudo-Code von dir eine Darstellung vom
Karazuba-Algorithmus? Ich verstehe den Anfang nicht. Muss ich "Z" mit
dem Wert "0" initialisieren? Ist "Z=A[n]*B" ein Kommentar über das was
der Pseudocode tut? Oder muss ich "n" mit dem Wert "0" initialisieren
und bei jedem "hole nächstes A" um 1 hochzählen?
Possetitjel schrieb:> dass man mit DREI> (statt vier) Teilmultiplikationen auskommt
Ob das den Aufwand lohnt? Andrerseits gibt es fertige Libraries zum
Rechnen mit beliebig grossen Ganzzahlen, da würde ich eine davon nehmen.
Die sind wahrscheinlich eh schon so weit optimiert wie möglich, da kommt
man mit einer Eigenentwicklung garnicht hin.
Georg
Joe K. schrieb:> @Heinz V.: Ist der Pseudo-Code von dir eine Darstellung vom> Karazuba-Algorithmus?
Ich habe den Wikipedia Artikel nur kurz überflogem aber ich denke ja,
gefunen hatte ih diese Methode in em Buch von Siemens 'Programmierung es
SAB8080', ist aber schon eine Weile her, kann sein das ich mih mit der
Richtung es Schiebens vertan habe.
> Ich verstehe den Anfang nicht. Muss ich "Z" mit> dem Wert "0" initialisieren?
selbsverständlich
> Ist "Z=A[n]*B" ein Kommentar über das was> der Pseudocode tut?
Ja
> Oder muss ich "n" mit dem Wert "0" initialisieren> und bei jedem "hole nächstes A" um 1 hochzählen?
Ja
georg schrieb:> Possetitjel schrieb:>> dass man mit DREI (statt vier) Teilmultiplikationen>> auskommt>> Ob das den Aufwand lohnt?
Nun ja... bei vier Zerlegungsstufen ist Karazuba etwa
drei Mal schneller als das Standardverfahren. Lohnt sich
das?
georg schrieb:> Possetitjel schrieb:>> dass man mit DREI>> (statt vier) Teilmultiplikationen auskommt>> Ob das den Aufwand lohnt? Andrerseits gibt es fertige Libraries zum> Rechnen mit beliebig grossen Ganzzahlen, da würde ich eine davon nehmen.> Die sind wahrscheinlich eh schon so weit optimiert wie möglich, da kommt> man mit einer Eigenentwicklung garnicht hin.>> Georg
In meinem Fall kann ich relativ viel Aufwand investieren, um den Ablauf
zu optimieren, da ich damit beschäftigt bin eine solche Bibliothek zu
schreiben. Es ist davon auszugehen, dass die Funktionen in verschiedenen
Programmen zum Einsatz kommen. Wenn die Multiplikation nur bei einem
einzelnen Programm zum Einsatz käme, hättest du wahrscheinlich recht.
Bei dem Pseudocode von Heinz V kommen außerdem Schiebebefehle zum
Einsatz anstatt Multiplikationen. Dies ist insofern ein Vorteil, weil
dann bei einigen Maschinen (zum Beispiel x86-Architektur) mit größeren
Wörtern gearbeitet werden kann.
@rbx: Danke für den Link.
@Possetitjel: Meiner Erfahrung nach kommen aus Russland so einige
nennenswerte Algorithmen. Auch im Bereich der Datenkompression gibt es
einige begabte Russen.
@Heinz V: Danke für den Verweis auf die Quelle. Ich werde mal im
Internet schauen, ob ich das Dokument finde. Vielleicht gibt es dort
noch weitere ähnliche Tricks =)
Edit: @Heinz V: Dieses Buch? http://ontheserver.de/temp/Buch.jpg
> Bei dem Pseudocode von Heinz V kommen außerdem Schiebebefehle zum> Einsatz anstatt Multiplikationen. Dies ist insofern ein Vorteil, weil> dann bei einigen Maschinen (zum Beispiel x86-Architektur) mit größeren> Wörtern gearbeitet werden kann.
Nicht wirklich. Das ist einfach deine Schulbuchmethode mit Binärzahlen.
Wird häufig auf CPUs ohne Hardwaremultiplier als Softwarelösung
eingesetzt.
Joe K. schrieb:> Edit: @Heinz V: Dieses Buch? http://ontheserver.de/temp/Buch.jpg
Exakt dieses.
foobar schrieb:> Das ist einfach deine Schulbuchmethode mit Binärzahlen.
Ja, Du hast zwar recht, aber mit Binaerzahlen bedeutet die
Multiplikation:
Multiplikator (1Bit) = 1 Multiplikant zum Proukt addieren
Multiplikator (1Bit) = 0 Springen ohne Addition
Bringt zumindest Geschwindigkeitsvorteile.
> Bringt zumindest Geschwindigkeitsvorteile.
Jo, ganz schöne Idioten, diese CPU-Designer: bauen mit viel Aufwand nen
Hardwaremultiplier wo's doch mit Software viel schneller geht ...
... oder hast du evtl einfach nicht weit genug gedacht?
Ok, ich habe mir nun den Karazuba-Algorithmus angeschaut. Dank dem Link
habe ich einigermaßen verstanden, wie er funktioniert. Es stimmt zwar,
dass die Anzahl der Multiplikationen gesenkt wird, dafür wird diese
Ersparnis durch zusätzliche Additionen und Subtraktionen wieder
aufgefressen. Außerdem muss der Übertrag gehandhabt werden, was
kostspielig ist.
Nach meinem Eindruck soweit ist der Algorithmus nur indirekt ein Gewinn,
da eine Multiplikation bei der verwendeten Maschine ein Datenkopieren
benötigt (die Werte müssen in bestimmten Registern sein, während bei
einer Addition und auch bei einer Subtraktion die Werte in beliebigen
Registern sein können).
Und so ein Algorithmus wird zum "Algorithmus der Woche"!? Naja,
vielleicht habe ich bei der Ersparnis noch etwas nicht verstanden.
Der Pseudocode von Heinz V ist keine Implementation vom
Karazuba-Algorithmus.
Edit: Ah, das ist eine Multiplikation auf Bit-Basis anstatt auf
Wort-Basis. Danke für den Hinweis, foobar. Eine Schleife in einer
Schleife. Die innere Schleife scheint durch "n" Bit für Bit vorwärts zu
schreiten. Das Ergebnis scheint erst eine Ewigkeit später berechnet zu
sein. :-/
Gibt es sonst noch Ansätze? Ich meine irgendwo gelesen zu haben, dass es
tatsächlich einen linearen Ansatz gibt. Dies war auch mein Auslöser,
dieses Thema überhaupt zu starten. Leider finde ich nichts hierzu. Es
wäre echt schade, wenn ich dann im Endeffekt tatsächlich das
implementieren muss, was viele kennen (Schulmethode) und nur wenige
übertrifft.
> Ah, das ist eine Multiplikation auf Bit-Basis anstatt auf Wort-Basis.
Bingo! :-)
> Ich meine irgendwo gelesen zu haben, dass es tatsächlich einen linearen> Ansatz gibt.
War wohl die Bild-Zeitung ;-) Man vermutet, dass die untere Grenze O(n *
log n) ist - ne Algorithmus dafür hat man aber noch nicht gefunden.
> Wäre echt schade, wenn ich dann im Endeffekt tatsächlich das> implementieren muss, was jeder kennt (Schulmethode) und niemanden> übertrifft.
Bei deinen kleinen Zahlengrößen kann es gut sein, dass die Qualität der
Implementation wichtiger ist als der Algorithmus an sich. Den Karazuba
könnte man aber trotzdem mal ausprobieren - dann weiß man zumindest, ab
welcher Größe die Implementation schneller wird :-)
Joe K. schrieb:> In meinem Fall kann ich relativ viel Aufwand investieren, um den Ablauf> zu optimieren, da ich damit beschäftigt bin eine solche Bibliothek zu> schreiben. Es ist davon auszugehen, dass die Funktionen in verschiedenen> Programmen zum Einsatz kommen. Wenn die Multiplikation nur bei einem> einzelnen Programm zum Einsatz käme, hättest du wahrscheinlich recht.
Ist das eine akademische Übung? Dann gerne weiter.
Wenn es produktiv sein soll würde ich mich nochmal an die gmp setzen.
Joe K. schrieb:> Und so ein Algorithmus wird zum "Algorithmus der Woche"!? Naja,> vielleicht habe ich bei der Ersparnis noch etwas nicht verstanden.
Die Ersparnis wirkt ein wenig wie beim Quadrieren mit Binomischer
Formel:
z.B. 16*16 -> 160 + 60 + 6*6 bzw, 17*17 -> 170 + 70 + 7*7.. und das
lässt sich ganz gut im Kopf rechnen.
(16*16 geht sowieso sehr schnell)
Es ist sehr zu empfehlen, den Algorithmus von Hand zu machen, bzw. zu
vergleichen und Karazuba auch mit Hexadezimalzahlen probieren (um ein
besseres Gefühl dafür zu bekommen, was bei der Implementierung gut geht,
und was nicht - bzw. es kommt ein wenig auf die Hardware selber an.
(D.h. Beispielimplementation(en) anschauen.)
(Video gucken geht auch, aber es bringt nicht unbedingt viel, besser
selber "antreten":
https://www.youtube.com/watch?v=E58q1dTZa68 )
("fünf Fragen..")
Eine Multiplikation ist nichts anderes als eine Faltung.
Die Signalverarbeiter kennen noch Begriff "Schnelle Faltung".
1.Die erste Zahl in ein Array schreiben.
(Z.B. aus 123 wird x[0,0,0,0,0,1,2,3]
Davon die FFT bilden.
2.Die zweite Zahl wie die erste behandeln.
3. Array von der ersten Zahl mal Array von der zweiten Zahl
multiplizieren. (Faltung im Zeitbereich ist Multiplikation im
Frequenzbereich)
4.Davon InversFFT bilden.
Der Aufwand steigt mit n * ld(n).Habe vor vielen Jahren diesen
Algorithmus mit LabVIEW erfolgreich getestet, aber nur im Wertebereich
von
long * long. Soweit ich mich erinnere, habe ich die Idee aus dem Buch
"Pi".
Ich bin doch recht erstaunt, dass es in der heutigen Zeit noch Maschinen
gibt, die dererlei Verrenkungen nötig machen. Das kenne Ich wirklich nur
von früher und der 8 Bit Zeit. Interessant, welche Lösungen es da gibt.
Bei mir hat immer Herr Binomi zugeschlagen. Die Rechnungen waren
entsprechend umfangreich :-)
An F. schrieb:> Ich bin doch recht erstaunt, dass es in der heutigen Zeit noch Maschinen> gibt, die dererlei Verrenkungen nötig machen. Das kenne Ich wirklich nur> von früher und der 8 Bit Zeit
Es ist doch völlig egal, ob eine CPU mit 4,8,16,32,64 oder noch mehr bit
rechnet, wenn man längere Zahlen hat stösst man immer wieder auf das
genau gleiche Problem.
Die derzeit grösste Primzahl hat 23 Mio Stellen. Ich glaube nicht, dass
es in absehbarer Zeit eine CPU mit dieser Registerlänge gibt. Also doch
weiterhin "verrenken".
Georg
Danke für die Rückmeldungen.
@foobar: Den Vergleich werde ich wohl machen, da ich mir noch nicht
100%ig sicher bin, wie sich die Änderungen vom Karazuba-Algorithmus in
der Praxis auswirken. Der Qualität von der Implementation wird ein
angemessenes Gewicht zugewiesen. Der Ausführungsgeschwindigkeit jedoch
auch. Zum Glück steht für die Bibliothek vergleichsweise viel
Entwicklungszeit zur Verfügung.
@Tippgeber: Danke, die verlinkten Diskussionen bieten viel zum Lesen.
Ich werde sie durchgehen, damit hier keine Wiederholungen notwendig
sind. Ich hoffe allerdings, dass die Diskussionen tatsächlich wertvoll
sind und nicht nur die ersten beiden Ergebnisse von einer automatischen
Suche sind.
@rbx: Ja, einen Blick auf bereits bestehende Mathematik-Bibliotheken zu
werfen, ist wohl ein guter Ansatz. Vielleicht kann ich hier oder dort
von den Bemühungen von Vorgängern profitieren.
@chefdesigner: Es mag sein, dass du dies nun nicht sonderlich gerne
liest. Du hättest gleich im ersten Beitrag lesen können, dass ich mit
Ganzzahlen bestehend aus bis zu 64 Wörtern arbeite. Die Erinnerung an
früher, als noch mit "8 Bit"-Maschinen gearbeitet wurde, obwohl die
vorgegebene Wortbreite hier garkeine Rolle spielt, ist ein Beitrag von
einer Art, welche schnell zur Offtopic-Diskussion führt.
@georg: Danke für die schnelle Erklärung für chefdesigner. Damit hast du
vielleicht eine größere Offtopic-Diskussion abgefangen.
@Alle: Ich danke für die Materialien soweit. Ich bin dann erstmal wieder
für eine Weile beschäftigt. :-)
Joe K. schrieb:> Nun möchte ich 2 Ganzzahlen miteinander multiplizieren, welche jeweils> aus bis zu 64 Wörtern bestehen (bei der gegebenen Maschine). Es wären> also nach dem bisherigen Schema 4.096 Multiplikationen und 4.095> Additionen notwendig. Ich hoffe, dass nun das Problem definiert wurde.>> Kann mir jemand einen Ansatz nennen, wie es möglich ist, dafür zu> sorgen, dass der Aufwand zur Durchführung einer Mehrwort-Multiplikation> reduziert wird?
Nur so am Rande: Wenn du weißt, dass dein Input maximal 64 Wörter hat,
dann ist die Multiplikation IMMER O(1), egal welchen Algorithmus du
verwendest. Wozu also suchen? ;)
> Ich meine irgendwo gelesen zu haben, dass es tatsächlich einen linearen> Ansatz gibt.
War wohl die Bild-Zeitung ;-) Man vermutet, dass die untere Grenze O(n *
log n) ist - ne Algorithmus dafür (
https://www.deviceranking.de/phone/12978/xiaomi-mi-8-se ) hat man aber
noch nicht gefunden.
> Wäre echt schade, wenn ich dann im Endeffekt tatsächlich das> implementieren muss, was jeder kennt (Schulmethode) und niemanden> übertrifft.
Bei deinen kleinen Zahlengrößen kann es gut sein, dass die Qualität der
Implementation wichtiger ist als der Algorithmus an sich. Den Karazuba
könnte man aber trotzdem mal ausprobieren - dann weiß man zumindest, ab
welcher Größe die Implementation schneller wird :-)
