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
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.
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?
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.
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?
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!
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
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.
... 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
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)
Martin schrieb:> ... 80 Bit sind 11 Speicheradressen im Ram ...>> Wie kommst du denn auf dieses putzige Idee?
Na ist klar Ints sind doch nullterminiert ;-)
...
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.
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.
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.
... 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
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
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
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).
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
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.
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
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?
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
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.
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
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.
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.
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 :->
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?
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...
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:
1
; Multiplication
2
; W <-- W * [Y]
3
; Implemented using Booth's algorithm, according to ATMEL
4
; AVR Application Note #200.
5
mul80:
6
push TI
7
push Q0
8
push Q1
9
push Q2
10
push Q3
11
push Q4
12
push Q5
13
push Q6
14
push Q7
15
push Q8
16
push Q9 ; Second factor
17
push S0
18
push S1
19
push S2
20
push S3
21
push S4
22
push S5
23
push S6
24
push S7
25
push S8
26
push S9 ; High result
27
28
ldd Q0, Y+0
29
ldd Q1, Y+1
30
ldd Q2, Y+2
31
ldd Q3, Y+3
32
ldd Q4, Y+4
33
ldd Q5, Y+5
34
ldd Q6, Y+6
35
ldd Q7, Y+7
36
ldd Q8, Y+8 ; Load second factor
37
ldd Q9, Y+9 ; Do not overwrite YH:YL!
38
39
clr S0
40
clr S1
41
clr S2
42
clr S3
43
clr S4
44
clr S5
45
clr S6
46
clr S7
47
clr S8
48
sub S9, S9 ; S9 = 0, carry flag = 0
49
50
ldi TI, 80
51
52
mul80_loop:
53
bst W0, 0
54
brcc mul80_noadd ; Add if second-to-last bit set
55
brts mul80_nosub ; But do nothing if last bit set, too
56
57
add S0, Q0
58
adc S1, Q1
59
adc S2, Q2
60
adc S3, Q3
61
adc S4, Q4
62
adc S5, Q5
63
adc S6, Q6
64
adc S7, Q7
65
adc S8, Q8
66
adc S9, Q9
67
68
mul80_noadd:
69
brtc mul80_nosub ; Subtract if last bit set
70
71
sub S0, Q0
72
sbc S1, Q1
73
sbc S2, Q2
74
sbc S3, Q3
75
sbc S4, Q4
76
sbc S5, Q5
77
sbc S6, Q6
78
sbc S7, Q7
79
sbc S8, Q8
80
sbc S9, Q9
81
82
mul80_nosub:
83
asr S9 ; Sign extension
84
ror S8
85
ror S7
86
ror S6
87
ror S5
88
ror S4
89
ror S3
90
ror S2
91
ror S1
92
ror S0
93
ror W9
94
ror W8
95
ror W7
96
ror W6
97
ror W5
98
ror W4
99
ror W3
100
ror W2
101
ror W1
102
ror W0
103
104
dec TI
105
brne mul80_loop
106
107
108
mov W0, W5
109
mov W1, W6
110
mov W2, W7
111
mov W3, W8
112
mov W4, W9
113
mov W5, S0
114
mov W6, S1
115
mov W7, S2
116
mov W8, S3
117
mov W9, S4 ; Adjust result
118
119
clv
120
cpse S5, TI ; TI = 0 from loop
121
sev
122
cpse S6, TI
123
sev
124
cpse S7, TI
125
sev
126
cpse S8, TI
127
sev
128
cpse S9, TI
129
sev ; Test overflow
130
131
pop S9
132
pop S8
133
pop S7
134
pop S6
135
pop S5
136
pop S4
137
pop S3
138
pop S2
139
pop S1
140
pop S0
141
pop Q9
142
pop Q8
143
pop Q7
144
pop Q6
145
pop Q5
146
pop Q4
147
pop Q3
148
pop Q2
149
pop Q1
150
pop Q0
151
pop TI
152
ret
Bei ersten Tests funktionierte das, ich werde aber noch genauer
hinschauen.
