mikrocontroller.net

Forum: PC-Programmierung Mehrwort-Multiplikation mit linearem Aufwand möglich?


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
Autor: Joe K. (joker123)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
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:
12 * 34 = 408
entspricht in Einzelschritten (4 Multiplikationen + 3 Additionen):
   2 *  4 =   8
+  2 * 30 =  60
+ 10 *  4 =  40
+ 10 * 30 = 300
---------------
         == 408
123 * 456 = 56.088
entspricht in Einzelschritten (9 Multiplikationen + 8 Additionen):
    3 *   6 =     18
+   3 *  50 =    150
+   3 * 400 =  1.200
+  20 *   6 =    120
+  20 *  50 =  1.000
+  20 * 400 =  8.000
+ 100 *   6 =    600
+ 100 *  50 =  5.000
+ 100 * 400 = 40.000
--------------------
           == 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.

: Bearbeitet durch User
Autor: Heinz V. (heinz_v)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: ich (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
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...

Autor: Possetitjel (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
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.

Autor: Heinz V. (heinz_v)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
Und als erstes prüfen ob einer der Faktoren 0 ist ;-)

Autor: Joe K. (joker123)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
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?

: Bearbeitet durch User
Autor: georg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Heinz V. (heinz_v)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Possetitjel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: rbx (Gast)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
Der Karazuba Algo wird von den Autoren Arno Eigenwillig und Kurt 
Mehlhorn vom Max-Planck-Institut für Informatik, Saarbrücken auf der 
Internetseite "Algorithmus der Woche" recht gut erklärt:

https://www-i1.informatik.rwth-aachen.de/~algorithmus/algo16.php

Autor: Joe K. (joker123)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

: Bearbeitet durch User
Autor: foobar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Heinz V. (heinz_v)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: foobar (Gast)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
> 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?

Autor: Joe K. (joker123)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

: Bearbeitet durch User
Autor: foobar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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 :-)

Autor: Karl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Tippgeber (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert

Autor: rbx (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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":
Youtube-Video "Monty Python Ritter der Kokosnuss Drei Fragen" )
("fünf Fragen..")

Autor: max123 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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".

Autor: Andreas F. (chefdesigner)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 :-)

Autor: georg (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
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

Autor: Joe K. (joker123)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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. :-)

Autor: tictactoe (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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? ;)

Autor: bestican (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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 :-)

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.