www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik 80 Bit x 80 Bit auf dem AVR multiplizieren


Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

aus einem kleinen Projekt die Problemstellung: 80 Bit mal 80 Bit = 80 
Bit, auf einem AVR (klar, gehen unter Umständen Bits verloren, weil das 
Ergebnis nur 80 Bit breit ist).

Meine Ansätze wären da gewesen:
- Addierschleife -- Scherz, haha.

- Schieben und Addieren, wäre dann eine konstante Laufzeit, dazu 
bräuchte ich aber mindestens drei 80 Bit breite Register: Eines fürs 
Ergebnis und jeweils eines für die beiden Faktoren, die werden ja nach 
rechts bzw. links verschoben.

- zusammengesetzte Rechnung, also nach Schema (A1 * 265 + A2) * (B1 * 
265 + B2) und dann brav ausmultiplizieren -- ergäbe einen riesigen Code, 
aber machbar.

- Multiplikation nach Booth; bräuchte man wieder drei 2*80-Bit-Register 
und noch eines für das einsame Bit. Wobei man eines davon einsparen 
könnte, denn der AVR kann direkt subtrahieren.

Platz im Programmspeicher und SRAM ist genügend vorhanden, der 
Algorithmus kann gerne 2kB belegen.

Wie würdet ihr sowas realisieren, ungeachtet dessen, ob das nun 
weltfremd ist, oder eher nicht? :-)

Danke und viele Grüße,
Kama

Autor: Helmut Lenzen (helmi1)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schau doch mal in der Codesammlung fuer AVR Arithmetik

http://www.mikrocontroller.net/articles/AVR_Arithm...

Da habe ich mal eine Routine fuer 24 x 24 mit 48 Bit Ergebnis 
reingestellt.
Nach dem gleichen Schema kannst du das ganze dann fuer 80 Bit erweitern.

Autor: Michael U. (amiga)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

warum nicht ganz üblich?

80 Bit sind 11 Speicheradressen im Ram

11 + 11 + 22 (für das Ergebnis) = 44 Byte ram.

Multiplakationsroutine erweitern, X, Y, Z geschickt einsetzen.

32x32 Bit sind bei mir rund 30 Zeilen ASM.
;*********************************************************************
;  32*32 Bit Multiplikation In RX0...3, RY0...4, Out RX0...7
;
;  Scratch-Reg: -
;*********************************************************************
;--------------------------------------------------------------------
;-- RX[64] = RX[32] * RY[32]
;--------------------------------------------------------------------
mul32:
  push  TEMP_0

  clr    RX7
  clr    RX6
  clr    RX5
  sub    RX4,RX4        ; RX4=0, C=0
  ldi    TEMP_0,32+1      ; im ersten Durchlauf wird immer gesprungen

mul32_loop:
  brcc  mul32_noadd

  add    RX4,RY0
  adc    RX5,RY1
  adc    RX6,RY2
  adc    RX7,RY3

mul32_noadd:
  ror    RX7
  ror    RX6
  ror    RX5
  ror    RX4
  ror    RX3
  ror    RX2
  ror    RX1
  ror    RX0

  dec    TEMP_0
  brne  mul32_loop

  pop    TEMP_0

  ret

Gruß aus Berlin
Michael

Autor: spess53 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

AppNote AVR201

http://www.atmel.com/dyn/resources/prod_documents/...

Lässt sich eigentlich beliebig erweitern.

MfG Spess

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Helmut:
Genauso sieht mein dritter Vorschlag aus -- das artet halt insofern 
etwas aus, als dass es dann 100 Multiplikationen sind ;-)

Michael U. schrieb:
> Hallo,
>
> warum nicht ganz üblich?
>
> 80 Bit sind 11 Speicheradressen im Ram
> [...]
Und dann klassisches Schieben und Addieren, oder wie stellst du dir den 
konkreten Algorithmus vor?

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was ist der Sinn, 80Bit x 80bit zu multiplizieren, wenn das Resultat nur 
80 Bit breit ist? Entweder 160Bit für das Resultat benutzen, was dann 
auch stimmt, oder man kann den 80bit im Multiplikator zuvor die 
hintersten 40 Bit wegschneiden, da die sowieso wegfallen.
Zur Multiplikation dann den Hardwaremultiplier und Karatsuba Algorithmus 
benutzen, geht vermutlich am schnellsten.

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
spess53 schrieb:
> Hi
>
> AppNote AVR201
>
> http://www.atmel.com/dyn/resources/prod_documents/...
>
> Lässt sich eigentlich beliebig erweitern.
Hm, den hab ich überlesen -- aber ja, da fällt so langsam ein Groschen 
bei mir :-)

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... 80 Bit sind 11 Speicheradressen im Ram ...

Wie kommst du denn auf dieses putzige Idee?

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Aber noch eine Überlegung, die mir gerade in den Sinn kommt:
Wenn es sich bei den 80 Bit um Festkommazahlen handelt, muss ja 
anschließend noch zurückgeschoben (geteilt) werden, wobei einige 
Nachkommastellen flöten gehen.

Sehe ich das dann richtig, dass etwa der kleinste Term im Produkt (quasi 
LSB * LSB, B=Byte) sich nur noch über das Carry-Flag aufs Ergebnis 
auswirken kann?

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael U. schrieb:
> 32x32 Bit sind bei mir rund 30 Zeilen ASM.
> [...]
Statt den Faktor zu schieben, lieber das Ergebnis rotieren. Das werde 
ich mir näher ansehen, danke!

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sven P. schrieb:
> Michael U. schrieb:
>> Hallo,
>>
>> warum nicht ganz üblich?
>>
>> 80 Bit sind 11 Speicheradressen im Ram
>> [...]
> Und dann klassisches Schieben und Addieren, oder wie stellst du dir den
> konkreten Algorithmus vor?

80/8 sind immer noch 10 ;-)

Man rechnet ganz einfach Ziffernweise. Wenn ein HW-Multiplikator 
verfügbar ist, etwa 8*8=16, dann ist die sinnigste Zifferngröße 1 Byte.

Für 10*10 Bytes ist jedes mit jedem zu multiplizieren, das sind 55 
Multiplikationen a[i]*b[j], die ab c[i+j] aufzuaddieren sind mit
i=0..9
j=0..9
i+j <= 9

Hier kann Arbeit bei der Addition gespart werden, indem man 
Teilsummenden bildet: bei
a[0]*b[0]*B^0 + a[0]*b[2]*B^2 + a[0]*b[4]*B^4 +...
mit der Basis B (hier 256) gibt es keine Überläufe von einer 
Doppelziffer (B^2) zur nächsten. Dito für
a[1]*b[0]*B^1 + a[1]*b[2]*B^3 + a[1]*b[4]*B^5 +...
etc.

...und das alles natürlich in einer Schleife, nicht explizit austexten 
:-)

Falls kein Multiplikationsbefehl vorhanden ist, geht es wohl am 
komfortabelsten mit B=2, d.h. Schulmultiplpikation und -addition auf 
Binärebene.

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... Für 10*10 Bytes ist jedes mit jedem zu multiplizieren, das sind 55
Multiplikationen ...

Hier ein Beipsiel mit 3 'Bytes' x 3 'Bytes'. Das sind 9 
Multiplikationen.

10 Bytes x 10 Bytes sind 100 Multiplikationen.


   123 * 456
  -----------
        12
        8
       4
         15
        10
        5
          18
         12
         6
  --------------
       56088

Autor: magnetus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Martin schrieb:
> ... Für 10*10 Bytes ist jedes mit jedem zu multiplizieren, das sind 55
> Multiplikationen ...

Martin schrieb:
> 10 Bytes x 10 Bytes sind 100 Multiplikationen.

Wat denn nu?  ;o)

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
magnetus schrieb:

> Wat denn nu?  ;o)

Braucht man im Ergebnis nur 10 Bytes -> 55
Braucht man im Ergebnis alle 20 Bytes -> 100

Autor: Nobody (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@  Sven P.
Mal ne Frage: Welche von den 160 Ergebnisbits brauchst Du denn?

Autor: Crest (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Martin schrieb:
> ... 80 Bit sind 11 Speicheradressen im Ram ...
>
> Wie kommst du denn auf dieses putzige Idee?

Na ist klar Ints sind doch nullterminiert ;-)

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
...
Für 10*10 Bytes ist jedes mit jedem zu multiplizieren, das sind 55
Multiplikationen a[i]*b[j], die ab c[i+j] aufzuaddieren sind mit
i=0..9
j=0..9
...

Du schreibst zwar von 55 Multiplikationen, dein 'Algorithmus' umfasst 
jedoch 100 Multiplikationen, da i und j von 0 bis 9 laufen und die 
Multiplikation a[i]*b[j] ausgeführt wird.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Martin schrieb:
> ...
> Für 10*10 Bytes ist jedes mit jedem zu multiplizieren, das sind 55
> Multiplikationen a[i]*b[j], die ab c[i+j] aufzuaddieren sind mit
> i=0..9
> j=0..9
> ...
>
> Du schreibst zwar von 55 Multiplikationen, dein 'Algorithmus' umfasst
> jedoch 100 Multiplikationen, da i und j von 0 bis 9 laufen und die
> Multiplikation a[i]*b[j] ausgeführt wird.

Da steht dann noch ein "i+j <= 9". Wenn schon zitieren, dann nicht das 
wegsnippen, was dann angemäkelt wird ;-)

...und es ist kein Algorithmus, sondern lediglich eine Skizze dessen.

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Prinzipiell kann man die Multiplikationen nur sparen, wenn man 
ausschließlich die 'unteren' 80 Bits berechnet, so wie das bei einer 16 
Bit Integer Multiplikation gemacht wird: die 4 Bytes der Multiplikation 
ab x cd erfordern zwar für ein 32 Bit Ergebnis 4 Teilmultiplikationen, 
da die Teilmultiplikation a x c immer ein Ergebnis größer 16 Bit hat, 
lässt man sie weg und kommt mit 3 Multiplikationen aus.

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... und es ist kein Algorithmus, sondern lediglich eine Skizze dessen 
...

... Da steht dann noch ein "i+j <= 9". Wenn schon zitieren, dann nicht 
das
wegsnippen, was dann angemäkelt wird ...


Johann - bist du tatsächlich so boniert?

EOT

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kommt drauf an, ob der AVR ein ATtiny oder ATmega ist.

Beim ATtiny geht der Klassiker: Schieben und addieren.
Du brauchst 31 Register, also überhaupt kein Problem.

Man kann dann noch optimieren. Wenn das Ergebnis nur 80 Bit sein darf, 
muß ein Faktor kleiner 40 Bit sein. D.h. Du brauchst nur ne 40*80=80Bit 
Multiplikation. Davor testen und gegebenenfalls die Faktoren 
vertauschen.

Bei den ATmega kann man auch den Multiplikationsbefehl benutzen. Der 
Code wird schneller, aber auch größer.


Peter

Autor: magnetus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Peter Dannegger schrieb:
> Man kann dann noch optimieren. Wenn das Ergebnis nur 80 Bit sein darf,
> muß ein Faktor kleiner 40 Bit sein. D.h. Du brauchst nur ne 40*80=80Bit
> Multiplikation.

Das verstehe ich jetzt nicht...

Beispiel: FFFFFFFFFF * 0002 = 1FFFFFFFFFE
            80 Bit     16 Bit    81 Bit

Gruß,
Magnetus

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
magnetus schrieb:
> Peter Dannegger schrieb:
>> Man kann dann noch optimieren. Wenn das Ergebnis nur 80 Bit sein darf,
>> muß ein Faktor kleiner 40 Bit sein. D.h. Du brauchst nur ne 40*80=80Bit
>> Multiplikation.
>
> Das verstehe ich jetzt nicht...
>
> Beispiel: FFFFFFFFFF * 0002 = 1FFFFFFFFFE
>             80 Bit     16 Bit    81 Bit

Peter sagt, daß wenn man weiß, daß kein Überlauf auftreten wird, 
mindestens einer der Faktoren höchstens 40 Bit haben kann.

In deinem Fall ist aber ein Überlauf aufgetreten (Falls "F" für 10 Bits 
steht).

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
magnetus schrieb:
> Das verstehe ich jetzt nicht...

Ganz einfach, wenn beide 41bit groß sind, gibts einen Überlauf und das 
Ergebnis ist ungültig.
Also lohnt es sich nicht, 41*41Bit zu rechnen, es kann nie in 80 Bit 
passen.


Peter

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Verzeihung für die späte Antwort.

Nun, für einen ganz konkreten Fall:
- Prozessor hat Multiplikationsbefehl (ATmega)
- Zahlen liegen als 80-Bit-Festkommazahlen vor und das Ergebnis soll 
auch derart herauskommen, dabei S40.40, also vorzeichenbehaftet und 
jeweils 40 Bits vor- und nach dem Komma.

Das mit dem Vorzeichen dürfte kein Problem sein, zumindest klappt meine 
Negieren-Funktion hervorragend :->

Meine Vermutung wäre dann: Wenigstens der kleinste Term, also das 
Produkt der beiden LSB (B=Bytes), kann sich nur noch über das Carry aufs 
Endergebnis auswirken, da die beiden Ergebnisbytes selbst ohnehin im 
Anschluss an die Multiplikation weggeschoben werden.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sven P. schrieb:
> - Zahlen liegen als 80-Bit-Festkommazahlen vor und das Ergebnis soll
> auch derart herauskommen, dabei S40.40, also vorzeichenbehaftet und
> jeweils 40 Bits vor- und nach dem Komma.

Dann müssen beide Faktoren aber immer als S60.20 vorliegen.
Ich würde die Zahlen der Einfachheit halber erstmal als Ganzzahl ansehen 
und erst zum Schluß die Skalierung vornehmen.


Peter

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Peter Dannegger schrieb:
> Sven P. schrieb:
>> - Zahlen liegen als 80-Bit-Festkommazahlen vor und das Ergebnis soll
>> auch derart herauskommen, dabei S40.40, also vorzeichenbehaftet und
>> jeweils 40 Bits vor- und nach dem Komma.
>
> Dann müssen beide Faktoren aber immer als S60.20 vorliegen.
So?

Meine Auffassung davon war bisher: 40.40 x 40.40 ergibt 80.80, das muss 
ich dann nach rechts schieben, sodass 40 Nachkommastellen flöten gehen. 
Einen Überlauf produziert es, wenn die oberen 40 Bits vor dem Komma 
nicht allesamt Null sind.

Oder missverstehe ich das?

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sven P. schrieb:
> Meine Auffassung davon war bisher: 40.40 x 40.40 ergibt 80.80, das muss
> ich dann nach rechts schieben, sodass 40 Nachkommastellen flöten gehen.

Hängt eben davon ab, wo Du abschneidest.
Dann muß man aber immer beachten, daß man nicht auch unten zuviel 
abschneidet.

Ich finds einfacher, immer nur oben abzuschneiden und einzuschätzen, daß 
man keinen Überlauf macht.
Jedesmal Überlauf und Unterlauf beachten zu müssen, ist mir zu 
aufwendig.


Peter

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja, was will ich machen?

Das Dingen werkelt in einer Art 'Taschenrechner', soll also einen 
möglichst breiten, aber wenigstens definierten Zahlenbereich erschlagen.

Setz ich da S40.40, dann ist das von der Auflösung ausreichend genau 
(daher ists kein großer Verlust, wenn das Ergebnis der Multiplikation 
auf von .80 auf .40 gerundet wird), und von der Magnitute sind 40 Bit 
vor dem Komma ebenfalls ausreichend.

Vorallem aber rechnets immer gleichbleibend (=absehbar) genau.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sven P. schrieb:
> Das Dingen werkelt in einer Art 'Taschenrechner'

Dann ist ja die Eingabezeit des Menschen der einzig limitierende Faktor.
D.h. Du könntest auch 800*800=1600Bit rechnen, ohne das es auffällt.


Peter

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Peter Dannegger schrieb:
> Sven P. schrieb:
>> Das Dingen werkelt in einer Art 'Taschenrechner'
>
> Dann ist ja die Eingabezeit des Menschen der einzig limitierende Faktor.
> D.h. Du könntest auch 800*800=1600Bit rechnen, ohne das es auffällt.
Ja natürlich, aber dafür müsste ich mir erstmal vollkommen klar werden, 
wie ich das bewerkstellige :-D

Sollte dann mal CORDIC o.ä. dazukommen, sieht das wieder anders aus, 
wenn man Resultate in endlicher Zeit erwarten möchte.
Ist halt mal eine Konzeptstudie.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Am naheliegendsten ist doch, die Multiplikation als 40.40*40.40 = 40.80 
auszuführen und die Nachkommastellen, die nicht in .40 reinpassen, 
wegzuwerfen (evtl. nach Rundung). Was am MSB überläuft wird weggeworfen 
bzw. zur Überlauferkennung verwendet.

Sooo zeitkritisch ist das alles ja nicht, und wenn sich später 
rausstellt, daß es zu zäh ist weil es durch darauf aufbauende Funktionen 
wie log, sin, ... sehr oft aufgerufen wird, lässt sich immer noch 
Optimierungspotential ausnutzen.

Zuerst geht's also um eine einfache Implementierung der 
Schul-Multiplikation.

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Johann L. schrieb:
> Am naheliegendsten ist doch, die Multiplikation als 40.40*40.40 = 40.80
> auszuführen und die Nachkommastellen, die nicht in .40 reinpassen,
> wegzuwerfen (evtl. nach Rundung). Was am MSB überläuft wird weggeworfen
> bzw. zur Überlauferkennung verwendet.
Ganz genau das habe ich vor.

> Zuerst geht's also um eine einfache Implementierung der
> Schul-Multiplikation.
Ich hab einfach mal die Lösung von Michael U. (amiga) implementiert, das 
funktioniert soweit.
Das 10-Byte-Register für den ersten Faktor habe ich mit weiteren 10 
Bytes aufgeblasen (gesichert auf dem Stack), so ists zugleich das 
temporäre Ergebnisregister. Den zweiten Faktor lade ich bei jedem der 80 
Durchläufe direkt aus dem SRAM.
Im Anschluss an die Schleife schiebe ich das temporäre Ergebnis um 5 
Bytes nach rechts, so gehen die kleinen Nachkommastellen flöten. Zuletzt 
wird geprüft, ob eines der oberen fünf Bytes ungleich Null ist, was dann 
durch das Carry-Flag als Überlauf angezeigt wird.

Laut Simulator macht das nun 276,4 Mikrosekunden pro Multiplikation, 
also locker 3,5kOp/s.
Mal sehen, ob ich noch einen der intelligenteren Vorschläge hier 
umgesetzt bekomme :->

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Soderle, der Multiplizierer funktioniert scheinbar jetzt.
Ich habe Eure Vorschläge allesamt mal ausprobiert und bin dann beim 
Booth-Algorithmus hängen geblieben. Der liefert mit 80x80 Bit nun in 
rund 200 Mikrosekunden (16 MHz), also in etwa 3200 Takten.

Wenn ich das Dingen etwas aufgeräumt habe, stell ichs in die 
Codesammlung.

Die Appnote von Atmel (AVR200) enthält noch eine Bemerkung: Der 
Booth-Algorithmus soll versagen, wenn der erster Faktor ('multiplicand') 
der betragsmäßig größten negativen Zahl entspricht.
Woher diese Beschränkung? In meinen Büchern habe ich solch eine Warnung 
nämlich nicht gefunden --

Ich kann mir das bisher nur so erklären:
Der Booth-Algorithmus arbeitet ja nur mit Additionen, entsprechend 
verlangt er nach einer Zweierkomplement-Darstellung ('die zweite 
Zeile'), um zu subtrahieren. Nur das geht natürlich schief, da die 
betragsmäßig größte negative Zahl im Zweierkomplement bei fester 
Stellenzahl nicht negiert werden kann, da sie sonst überläuft.
Das Problem dürfte ich dann umgehen können, indem ich nicht das 
Zweierkomplement bilde und addiere, sondern den Subtrahier-Befehl 
verwende, ja?

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sven P. schrieb:
> Das Problem dürfte ich dann umgehen können, indem ich nicht das
> Zweierkomplement bilde und addiere, sondern den Subtrahier-Befehl
> verwende, ja?

Zweierkomplement addieren oder originalen Wert abziehen bringt das 
gleiche Ergebnis, auch für 0x80...

Eher ist das Problem, das 0x80=-0x80 (bei 8 Bit, für mehr Bits analog). 
Demnach ist x+0x80 = x-0x80.

Btw: So wie ich Booth verstehe, arbeitet der auf der Binärdarstellung 
durch Zusammenfassen von Gruppen gleicher Bits. Intuitiv würd ich sagen, 
daß ne normale Schul-Multiplikation schneller ist, wenn man die 
MUL-Befehle von AVR verwendet. Und der Implementierung wird wohl auch 
übersichtlicher...offenbar tippst du in Assembler...

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Johann L. schrieb:
> Sven P. schrieb:
>> Das Problem dürfte ich dann umgehen können, indem ich nicht das
>> Zweierkomplement bilde und addiere, sondern den Subtrahier-Befehl
>> verwende, ja?
>
> Zweierkomplement addieren oder originalen Wert abziehen bringt das
> gleiche Ergebnis, auch für 0x80...
Muss ich nochmal überdenken.

> Btw: So wie ich Booth verstehe, arbeitet der auf der Binärdarstellung
> durch Zusammenfassen von Gruppen gleicher Bits. Intuitiv würd ich sagen,
> daß ne normale Schul-Multiplikation schneller ist, wenn man die
> MUL-Befehle von AVR verwendet. Und der Implementierung wird wohl auch
> übersichtlicher...offenbar tippst du in Assembler...
Naja, dann programmier mal eine Schulmultiplikation mit 10x10 Bytes :-/

Aktueller Zustand, spaßeshalber mal in voller Schönheit im Text und 
nicht im Anhang:
; Multiplication
; W <-- W * [Y]
; Implemented using Booth's algorithm, according to ATMEL
; AVR Application Note #200.
mul80:
  push  TI
  push  Q0
  push  Q1
  push  Q2
  push  Q3
  push  Q4
  push  Q5
  push  Q6
  push  Q7
  push  Q8
  push  Q9    ; Second factor
  push  S0
  push  S1
  push  S2
  push  S3
  push  S4
  push  S5
  push  S6
  push  S7
  push  S8
  push  S9    ; High result

  ldd  Q0, Y+0
  ldd  Q1, Y+1
  ldd  Q2, Y+2
  ldd  Q3, Y+3
  ldd  Q4, Y+4
  ldd  Q5, Y+5
  ldd  Q6, Y+6
  ldd  Q7, Y+7
  ldd  Q8, Y+8    ; Load second factor
  ldd  Q9, Y+9    ; Do not overwrite YH:YL!

  clr  S0
  clr  S1
  clr  S2
  clr  S3
  clr  S4
  clr  S5
  clr  S6
  clr  S7
  clr  S8
  sub  S9, S9    ; S9 = 0, carry flag = 0
  
  ldi  TI, 80

mul80_loop:
  bst  W0, 0
  brcc  mul80_noadd  ; Add if second-to-last bit set
  brts  mul80_nosub  ; But do nothing if last bit set, too

  add  S0, Q0
  adc  S1, Q1
  adc  S2, Q2
  adc  S3, Q3
  adc  S4, Q4
  adc  S5, Q5
  adc  S6, Q6
  adc  S7, Q7
  adc  S8, Q8
  adc  S9, Q9

mul80_noadd:
  brtc  mul80_nosub  ; Subtract if last bit set

  sub  S0, Q0
  sbc  S1, Q1
  sbc  S2, Q2
  sbc  S3, Q3
  sbc  S4, Q4
  sbc  S5, Q5
  sbc  S6, Q6
  sbc  S7, Q7
  sbc  S8, Q8
  sbc  S9, Q9

mul80_nosub:
  asr  S9    ; Sign extension
  ror  S8
  ror  S7
  ror  S6
  ror  S5
  ror  S4
  ror  S3
  ror  S2
  ror  S1
  ror  S0
  ror  W9
  ror  W8
  ror  W7
  ror  W6
  ror  W5
  ror  W4
  ror  W3
  ror  W2
  ror  W1
  ror  W0

  dec  TI
  brne  mul80_loop


  mov  W0, W5
  mov  W1, W6
  mov  W2, W7
  mov  W3, W8
  mov  W4, W9
  mov  W5, S0
  mov  W6, S1
  mov  W7, S2
  mov  W8, S3
  mov  W9, S4    ; Adjust result

  clv
  cpse  S5, TI    ; TI = 0 from loop
  sev
  cpse  S6, TI
  sev
  cpse  S7, TI
  sev
  cpse  S8, TI
  sev
  cpse  S9, TI
  sev      ; Test overflow

  pop  S9
  pop  S8
  pop  S7
  pop  S6
  pop  S5
  pop  S4
  pop  S3
  pop  S2
  pop  S1
  pop  S0
  pop  Q9
  pop  Q8
  pop  Q7
  pop  Q6
  pop  Q5
  pop  Q4
  pop  Q3
  pop  Q2
  pop  Q1
  pop  Q0
  pop  TI
  ret

Bei ersten Tests funktionierte das, ich werde aber noch genauer 
hinschauen.

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.