Forum: Mikrocontroller und Digitale Elektronik Schnelle(re)s Quadrieren??


von Läubi .. (laeubi) Benutzerseite


Lesenswert?

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?

von Matthias L. (Gast)


Angehängte Dateien:

Lesenswert?

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.

von Michael G. (linuxgeek) Benutzerseite


Lesenswert?

Läubi Mail@laeubi.de wrote:
> Ich habe folgende Routine geschrieben um zwei 32bit Zahlen zu
> multiplizieren (mit 32bit Ergebnis!)

Sehr sinnvoll.

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

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 :)

von Hans (Gast)


Lesenswert?

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.

von Hans (Gast)


Lesenswert?

Wer noch etwas über die (Integer) Multiplikation nachlesen möchte, hier 
ein paar Wikipedia-Links:

Computeralgrbra-Allgemein:
http://de.wikipedia.org/wiki/Computeralgebra

Schneller, aber für Feld-Wald-Wiesen-Anwendungen zu ineffiziente 
Implementierung:
http://de.wikipedia.org/wiki/Karatsuba-Algorithmus

Der Schnellste von allen, aber auch nur von theoretischer Bedeutung:
http://de.wikipedia.org/wiki/Toom-Cook-Algorithmus

von Kai G. (runtimeterror)


Lesenswert?

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?

von Hagen R. (hagen)


Lesenswert?

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

von yalu (Gast)


Lesenswert?

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.

von eProfi (Gast)


Lesenswert?

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

von Hagen R. (hagen)


Lesenswert?

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

von Hagen R. (hagen)


Lesenswert?

>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

von Michael G. (linuxgeek) Benutzerseite


Lesenswert?

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

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

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 :)

von Michael G. (linuxgeek) Benutzerseite


Lesenswert?

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.

von yalu (Gast)


Lesenswert?

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.

von Hagen R. (hagen)


Lesenswert?

>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

von Hagen R. (hagen)


Lesenswert?

>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

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.