Ich habe folgende Routine geschrieben um zwei 32bit Zahlen zu
multiplizieren (mit 32bit Ergebnis!)
(ML = r0, MH = r1)
1
//Q1 * Q2
2
//abcd * ABCD
3
//Output = Q0
4
5
//d * ABCD
6
mul Q10, Q20 //d*D
7
movw Q01:Q00, MH:ML
8
mul Q10, Q22 //d*B
9
movw Q03:Q02, MH:ML
10
mul Q10, Q23 //d*A
11
mov temp, ML
12
mul Q10, Q21 //d*C
13
add Q01, ML
14
adc Q02, MH
15
adc Q03, temp
16
//c * BCD
17
mul Q11, Q21 //c*C
18
add Q02, ML
19
adc Q03, MH
20
mul Q11, Q22 //c*B
21
mov temp, ML
22
mul Q11, Q20 //c*D
23
add Q01, ML
24
adc Q02, MH
25
adc Q03, temp
26
//b * CD
27
mul Q12, Q21 //b*C
28
add Q03, ML
29
mul Q12, Q20 //b*D
30
add Q02, ML
31
add Q03, MH
32
//a * D
33
mul Q13, Q20 //a*D
34
add Q03, ML
35
//10x mult + 12x add + 4x sonst = 36clk
Konnte bis jezt auch keinen Fehler entdecken, scheint zu funktionieren
:)
Jezt möchte ich aber auch das Quadrat einer Zahl, also Q1*Q1 berechnen
und frage mich, ob (aus der Tatsache das Q1 = Q2) sich etwas ergibt
womit man das ganze beschleunigen könnte?
Oder ist das so eh shcon die schnellste Möglichkeit.
Hab jezt schon etwas rumgerechnet aber mir fällt nix ein. Vieleicht
kennt ja jemand nen Trick?
Ich hab sowas vor Jahren auch mal selbst geschrieben, aber ich hab
16x16=>32
bzw 16/16 => 16 R16.
Aber ich hab nen anderen Alghorithmus dahinter und keine Multiplikation
verwendet.
Kannst dir ja mal angucken.
Aber Trick bei Quadrieren wüsste ich jetzt auf die Schnelle auch keinen.
Michael G. wrote:
> Läubi Mail@laeubi.de wrote:>> Ich habe folgende Routine geschrieben um zwei 32bit Zahlen zu>> multiplizieren (mit 32bit Ergebnis!)>> Sehr sinnvoll.
Was sollte daran nicht "sinnvoll" sein? Ich glaube in nahezu jeder
Programmiersprache ist das Ergebnis einer Integer (32bit) Multiplikation
wieder ein Integer(32bit).
Und wozu sollte ich 64bit draus machen wenn ich weiß das das Ergebnis
der Multiplikation meinen 32bit Datentyp nicht überschreitet?
@Matthias Lipinsky:
Jupp danke, ich benutz hier allerdings den Hardwaremultiplizierer was
das ganze etwas beschleunigen kann :)
Assembler verstehe ich nicht besonders gut, konnte Deinen Algorithmus
jetzt nicht analysieren, aber trotzdem noch ein bisschen
hintergründiges:
Die Multiplikation hat im Allgemeinen eine quadratische Komplexität
[O(n²)]. Es geht zwar in der Theorie etwas schneller, Auswirkungen hat
das in der Praxis aber nur für astronomisch große Zahlen.
Um die Multiplikation in der Praxis dennoch zu beschleunigen, kann man
oft verwendete cachen (zwischenspeichern). Ich würde mir also wirklich
überlegen, ob es sinnvoll ist, den letzten Takt aus dem
Multiplikationsalgorithmus rauszuholen, oder nicht besser einen Cache
auf einer höheren Ebene (z.B. der gesamten zu berechnenden Formel)
einzusetzen.
Wenn du wirklich nur an einem 32bit-Ergebnis interessiert bist, reicht
es ja das Quadrieren auf 16x16 zu beschränken - das spart schonmal
einiges.
Ansonsten:
1
x = 256 * a + b
2
x² = 65536 * a² + b² + 2 * a * b
macht drei Multiplikationen und eine etwas aufwändigere Addition.
Hattest du dir sowas in der Art vorgestellt?
Du hast A1:A0 = 16 Bit
A1:A0 * A1:A0
in Schoolboy rechnen wir
R3:R2 = A1*A1
R2:R1 = A1*A0
R2:R1 = A1*A0
R1:R0 = A0*A0
R3:R2:R1:R0 = 32 Bit Resulat
Den Schritt R2:R1 = A1*A0 machen wir nur einmal, und addieren das
Resultat R2:R1 einfach mit sich selber = *2.
Verbleibt
R3:R2 = A1*A1
R1:R0 = A0*A0
R2:R1 = A1*A0 * 2
3x 8 Bit MUL, + 5x ADD/ADC
@Hans:
>Der Schnellste von allen, aber auch nur von theoretischer Bedeutung:>http://de.wikipedia.org/wiki/Toom-Cook-Algorithmus
Asympthotisch die schnellste Multipliaktion ist nach
A.Schönhage+Solvey+Strassen die modulare Fermat Fast Fourier
Transformation. Die ist wie die meisten anderen FFT Algoerithmen
schneller als die Karatsuba und Toom-Cook-Variante. Toom-Cook ist ja nur
eine logische Weiterentwicklung der Karatusuba Variante. Und diese
Verfahren haben sehr wohl auch praktische Bedeutung.
Gruß Hagen
Sechs Einzelmultiplikationen reichen:
b0 * b0
b0 * b1
b0 * b2
b0 * b3
b1 * b1
b1 * b2
b0 bis b3 sind dabei die einzelnen Bytes der zu quadrierenden Zahl der
Wertigkeit nach.
Alle anderen 10 möglichen Produkte ergeben sich aus den genennten
durch Vertauschen der Operanden oder haben auf die unteren 32 Bits des
Ergebnisses keinen Einfluss.
mul Q12, Q20 //b*D
add Q02, ML
add Q03, MH
sollte der 2. add nicht ein adc sein?
32 x 32 --> 32 Bit macht dann Sinn, wenn ein Faktor klein und der andere
groß ist.
z.B. 0x00000012 x 0x00345678
er möchte ein 32Bit Resultat, 2^32^0.5 = 2^16, ergo bei einem Resulat
von 32Bit ist das Quadrieren von Zahlen größer 2^16-1 ziemlich sinnfrei.
Man benötigt also eine 16x16 Bit Mul und bei der Quadrierung dessen kann
man 1 MUL sparen, macht 3x MUL.
Man kann bei größeren Multiplikationen einige MULs sparen geht aber zu
Lasten von mehr Additionen und Registerumkopierereien. Auf einem AVR mit
seiner 2 Zyklen MUL muß man bei solchen Tricks schon sehr genau auf das
Aufwand Nutzen Verhältnis achten.
Gruß Hagen
>mul Q12, Q20 //b*D> add Q02, ML> add Q03, MH>sollte der 2. add nicht ein adc sein?
ADD+ADC+ADC müsste es sein
R3:R2 = MUL A1,A1
R1:R0 = MUL A0,A0
+ 00:T2:T1 = MUL A1,A0
+ 00:T2:T1
-------------
= R3:R2:R1:R0
Das + 00:T2:T1 setzt sich aus 1 ADD und 2 ADC zusammen.
Gruß Hagen
Fuer's Multiplizieren gibt es nen Divide-And-Conquer-Algorithmus. Wenn
ich jetzt nich zu faul waere wuer dich ma nachgucken ;) Ausm Stegreif
bekomm ich den jedenfalls nich hin. Ach ja, das Ergebnis zweier
Multiplikationen mit 32-Bit-Zahlen ist natuerlich bis zu 64 Bits lang.
Hier einzuschraenken ist Unfug weil das Ergebnis dann nur in einem
Restklassenring mod 2^32 korrekt ist. Ich denke das ist nicht, was man
sich hier erwartet. Sonst kannst max. zwei 16-Bit-Zahlen miteinander
multiplizieren.
Ach ja: Der Titel heisst ja "Quadrieren". Das geht natuerlich sehr
schnell. Sprich: Fuer's Potenzieren gibt es sehr effiziente Algorithmen.
Zwei Zahlen miteinander zu multiplizieren hat allerdings mit Quadieren
wenig gemein, es sei denn, die Zahlen sind identisch, was natuerlich nur
ein Sonderfall ist.
Michael
eProfi wrote:
> mul Q12, Q20 //b*D> add Q02, ML> add Q03, MH>>> sollte der 2. add nicht ein adc sein?
ja, danke hab ich übersehen.
Hagen Re wrote:
> er möchte ein 32Bit Resultat, 2^32^0.5 = 2^16, ergo bei einem Resulat> von 32Bit ist das Quadrieren von Zahlen größer 2^16-1 ziemlich sinnfrei.> Man benötigt also eine 16x16 Bit Mul und bei der Quadrierung dessen kann> man 1 MUL sparen, macht 3x MUL.
Danke Hagen, da hast du recht, das habe ich nicht bedacht!
muls16x16=32 braucht "nur" 19 Takte.
Michael G. wrote:
> Ach ja: Der Titel heisst ja "Quadrieren". Das geht natuerlich sehr> schnell. Sprich: Fuer's Potenzieren gibt es sehr effiziente Algorithmen.> Zwei Zahlen miteinander zu multiplizieren hat allerdings mit Quadieren> wenig gemein, es sei denn, die Zahlen sind identisch, was natuerlich nur> ein Sonderfall ist.
Ja darum ging es mir ja ob man den allgemeinen Fall wenn man weiß das
dieser Sonderfall vorliegt vereinfachen kann.
@all:
Also einmal brauch ich die Routine um zwei (allgemeine) 32bit Zahlen zu
multiplizieren, das das Ergebnis NICHT korrekt ist wenn das Ergebnis
eine höhere Wertigkeit als 32bit hat ist mir klar, aber wie schon
angedeutet wurde, wenn man eine kleine mit einer großen Zahl
multipliziert macht das schon Sinn.
Was das Quadrieren angeht wurde ja schon bemerkt das das maximale
ergebnis was noch in 32bit passt das einer 16x16 Multiplikation ist. Das
spart dann in meinem Fall immerhin 17 Takte was mich schonmal
weiterbringt!
Danke schonmal an alle die sich bis hierher Gedanken gemacht haben :)
Läubi Mail@laeubi.de wrote:
> Michael G. wrote:>> Ach ja: Der Titel heisst ja "Quadrieren". Das geht natuerlich sehr>> schnell. Sprich: Fuer's Potenzieren gibt es sehr effiziente Algorithmen.>> Zwei Zahlen miteinander zu multiplizieren hat allerdings mit Quadieren>> wenig gemein, es sei denn, die Zahlen sind identisch, was natuerlich nur>> ein Sonderfall ist.> Ja darum ging es mir ja ob man den allgemeinen Fall wenn man weiß das> dieser Sonderfall vorliegt vereinfachen kann.
Du koenntest modulares Potenzieren verwenden. Allerding bei nem
Exponenten von 2 bringt Dir das reichlich wenig, eher im Gegenteil. Bei
groesseren Exponenten bringt es Dir allerdings sehr viel.
Hagen Re schrieb:
> bei einem Resulat von 32Bit ist das Quadrieren von Zahlen größer> 2^16-1 ziemlich sinnfrei.
Ziemlich und meistens, aber nicht immer. Manchmal nimmt man bei
Rechenoperationen Überläufe bewusst in Kauf, weil einen nur die
untersten n Bits des Ergebnisses interessieren. Bei Additionen sieht
man das recht häufig, bei Multiplikationen und beim Quadrieren
zugegebenermaßen seltener, bspw. in Pseudozufallszahlengeneratoren.
Als ich oben schrieb, man bräuchte sechs Einzelmultiplikationen, bin
davon ausgegangen, dass 32-Bit-Werte modulo 2**32 quadriert werden
sollen (deswegen auch die Erwähnung der unteren 32 Bits des
Ergebnisses).
Für "gewöhnliche" Berechnungen hast du natürlich völlig recht, da sind
beim Quadrieren Argumente mit mehr als der halben Bitzahl des
Ergebnisses unsinnig, und es genügen 3 Einzelmultiplikationen.
linuxgeek schrieb:
> Fuer's Multiplizieren gibt es nen Divide-And-Conquer-Algorithmus.> Wenn ich jetzt nich zu faul waere wuer dich ma nachgucken
Zum Glück haben das schon andere Poster in diesem Thread für dich
getan (s. Beiträge von Hans und Hagen Re) ;-)
Läubi schrieb:
> muls16x16=32 braucht "nur" 19 Takte.
Damit ich doch noch etwas in diesem Thread beitragen kann: Quadrieren
von 16-Bit-Zahlen mit 32-Bit-Ergebnis geht sogar in 15 Zyklen:
1
clr temp
2
mul Q10, Q10
3
movw Q01:Q00, MH:ML
4
mul Q11, Q11
5
movw Q03:Q02, MH:ML
6
mul Q10, Q11
7
add Q01, ML
8
adc Q02, MH
9
adc Q03, temp
10
add Q01, ML
11
adc Q02, MH
12
adc Q03, temp
(ungetestet)
Wenn du sowieso schon ein Register mit dem Inhalt 0 herumliegen hast,
kannst du dir den clr-Befehl am Anfang sparen, so dass nur noch 14
Zyklen benötigt werden.
>Fuer's Multiplizieren gibt es nen Divide-And-Conquer-Algorithmus. Wenn>ich jetzt nich zu faul waere wuer dich ma nachgucken ;) Ausm Stegreif
Bringt auf dem AVR recht wenig. Da die MUL nur 2 Takte benötigt im
Vergleich zu ADD mit 1 Takt, bingen Tricks wie Divide&Conquer keinen
Vorteil. Bei diesen Verfahren wird immer die Multiplikation durch
zusätzliche Additionen/Subtraktionen substituiert. Konkret spart man
eine Multiplikation mit drei Additionen ein. Ergo auf dem AVR mit seiner
schnellen Multiplikation untauglich. Was was bringen würde, bei großen
Zahlen ist der Tower Trick auch unter Comba-Trick bekannt. Der spart im
Vergleich zur Schoolboy Methode keinerlei Multiplikationen ein sondern
führt eine Reorganisation der einzelnen Multiplikationen durch um
Additionen zu sparen. Das habe ich oben schon mit der Quadrierung
gezeigt. Im gleichen Schemata kann man fortfahren wenn man größere
Zahlen multiplizieren möchte. Allerdings ist es denoch eine
Gatwanderung. Der AVR ist mit seiner RISC Architektur und den geringen
Unterschieden zwischen MUL, ADD, ADC, MOV und MOVW in der Taktanzahl ein
schlechter Kandidat für algorithmische Optimierungen. Die meisten
Verfahren setzen voraus das die Multiplikation im Vergleich zu
Additionen wesentlich ineffizienter sind.
>Zwei Zahlen miteinander zu multiplizieren hat allerdings mit Quadieren>wenig gemein, es sei denn, die Zahlen sind identisch, was natuerlich nur>ein Sonderfall ist.
Naja die Quadrierung einer Zahl ist eine Multiplikation von zwei Zahlen
die identisch sind. Somit ist dein angesprochener Sonderfall ja
eingetreten ;) Ein Quadrat ist ja auch nur ein Rechteck.
Gruß Hagen
>Als ich oben schrieb, man bräuchte sechs Einzelmultiplikationen, bin>davon ausgegangen, dass 32-Bit-Werte modulo 2**32 quadriert werden>sollen (deswegen auch die Erwähnung der unteren 32 Bits des>Ergebnisses).
Man kann auf diese Weise (A*B) mod 2^(8x) und (A*B) div 2^(8x) sehr
effizient rechnen, also nicht nur modulo um die untersen LSB su
berechnen sondern auch wenn man nur die obersten MSBs haben möchte. Im
Grunde läuft es darauf hinaus das man die notwendigen MULs für die
LSB/MSB einfach weglässt.
Gruß Hagen