Man stelle sich eine Assemblersprache vor, die Addieren/Subtrahieren und
Bit shiften kann, aber sonst keine mathematischen Operationen.
(Bedingte Sprünge, Zuweisungen, Unterprogramme natürlich schon)
Um zu multiplizieren, muss man Bits shiften und addieren,
z.B. Faktor 10
1
reg1*1010b->reg2:
2
3
reg2=0
4
reg1<<=1
5
reg2+=reg1
6
reg1<<=2
7
reg2+=reg1
Bei vielen Bits im Multiplikator könnte man es mit einem Trick
wesentlich schneller machen.
Normaler Algo:
1
reg1*0xf->reg2:
2
3
reg2=0
4
reg2+=reg1
5
reg1<<=1
6
reg2+=reg1
7
reg1<<=1
8
reg2+=reg1
9
reg1<<=1
10
reg2+=reg1
Trick mit Subtraktion:
1
reg1*0xf->reg2:
2
3
reg2=0
4
reg3=reg1
5
reg3<<=4// mit 16 multiplizieren
6
reg2+=reg3
7
reg2-=reg1// wieder 1 abziehen
Gibt es einen bekannten Algorithmus,
der dies bei beliebigien Faktoren feststellt,
wo man mit größeren Zahlen (z.B. nächstgrößere 2-er Potenz)
multiplizert,
und dann wieder abziehen muss?
Du triffst hier aber eine Annahme. Nämlich die, das reg3 auch frei ist.
Ist es das nicht, dann kommt da noch dazu
1
reg1*0xf->reg2:
2
3
pushreg3
4
reg2=0
5
reg3=reg1
6
reg3<<=4// mit 16 multiplizieren
7
reg2+=reg3
8
reg2-=reg1// wieder 1 abziehen
9
popreg3
Ob das dann immer noch schneller ist, hängt unter anderem auch davon ab,
welche Operation wieviele Taktzyklen benötigt.
Und genau da liegt auch die Antwort auf deine Frage:
>> Gibt es einen bekannten Algorithmus,
Beide Varianten vom Compiler ausformulieren lassen, Takte abzählen und
die schnellere nehmen.
Wobei das heutzutage mit den ganzen Caches und überlappenden Operationen
alles andere als simpel ist.
Johannes schrieb:> Gibt es einen bekannten Algorithmus,
Mir ist jedenfalls keiner bekannt, obwohl sich die Aufgabe ziemlich
interessant anhört.
Es geht also darum, eine variable Zahl möglichst effizient mit einem
vorgegebenen, konstanten Faktor zu multiplizieren, wobei nur Additionen,
Subtraktionen, Shift-Operationen und Zuweisungen zur Verfügung stehen.
Mathematisch könnte man das Problem folgendermaßen formulieren:
Gesucht ist die Darstellung einer gegebenen Zahl (nämlich des konstanten
Faktors) als Summe möglichst weniger Zweierpotenzen mit jeweils
positivem oder negativen Vorzeichen.
Dafür gibt es sicher einen recht einfachen Lösungsalgorithmus, auch wenn
mir spontan keiner einfallen will ;-)
Allerdings ist die Laufzeit eines optimalen Programms nur näherungsweise
eine monotone Funktion der Anzahl der benötigten Zweierpotenzen. Um die
Laufzeit perfekt zu optimieren, müssen weitere Aspekte berücksichtigt
werden:
- Sonderbehandlung der Zweierpotenz 2⁰
- Laufzeit der einzelnen Operationen, insbesondere die mögliche
Abhängigkeit der Shift-Operation vom zweiten Operanden
- Anzahl der verfügbaren Register zur Speicherung und späteren
Wiederverwendung von Zwischenergebnissen
Das macht den Algorithmus gleich sehr viel komplizierter. Wahrscheinlich
wird er auf eine Backtracking-Suche hinauslaufen.
Karl Heinz schrieb:> Du triffst hier aber eine Annahme.
Eigentlich hast du 2 Annahmen getroffen.
Die Sache mit dem Register UND die Annahme, dass du um beliebig viele
Bits in einem Rutsch schieben kannst. Manche Prozessoren können das,
andere wieder nicht.
Mal angenommen, die CPU kann das nicht.
Ist
Beobachtung bzw. Annahme
Der Trick lohnt sich nur, wenn es eine Folge von 1 Bits der Länge n gibt
(deren rechtestest das LSB ist, wobei ich aus dem Stegreif raus noch
nicht sagen kann, ob das eine echt Einschränkung ist, oder ob man die
los wird.)
Dann geht es doch darum, die Multiplikation mit einer derartigen Folge
von n Stück 1 Bist derart abzuwägen, ob
1
reg2 = reg1
2
3
wiederhole n-1 mal {
4
reg1 <<= 1
5
reg2 += reg1
6
}
weniger Instruktionen benötigt, als
1
reg2 = reg1
2
reg2 <<= n
3
reg2 -= reg1
(unter der Annahme, dass alle Instruktionen gleich lang dauern bzw. die
sonstigen Umstände ... bla, bla, bla))
Hmm. auf den ersten Blick scheint das bei 2 nebeeinander liegenden 1
Bits bereits zielführend zu sein.
Jetzt erhebt sich 'nur noch' die Frage, wie verallgemeinert das, wenn
die Folge von 1 Bits nicht beim LSB endet.
>Mathematisch könnte man das Problem folgendermaßen formulieren:>>Gesucht ist die Darstellung einer gegebenen Zahl (nämlich des konstanten>Faktors) als Summe möglichst weniger Zweierpotenzen mit jeweils>positivem oder negativen Vorzeichen
Ja. Ich würde zwar schreiben "Summe oder Differenz" statt "pos. oder
neg. Vorzeichen", aber der Sinn bleibt gleich.
Sicherlich bieten Zahlen, wo in der Binärdarstellung viele 1-er
aufeinandertreffen, große Vorteile.
Bei 3 oder mehr könnte der Trick Vorteile bringen.
Hat die Zahl mehrere solcher 1-er Kolonnen, kann der Algo schwieriger
werden.
>Eigentlich hast du 2 Annahmen getroffen.>Die Sache mit dem Register UND die Annahme, dass du um beliebig viele>Bits in einem Rutsch schieben kannst.
1. Es sind viele Register frei (reg4 ... reg10)
2. man kann bis zu 31 Bits schieben. (Die register haben jeweils 32
Bits)
Solche Algorithmen gibt es, aber das eigentliche Problem ist (mal
wieder) NP-vollständig...
http://www.spiral.net/hardware/multless.html
"For a given constant c, the problem is to find a multiplier block with
the least number of adds/subtracts. This problem and two extensions are
visualized on the right. We have developed algorithms and online
generators for each of the problems.
Finding an optimal solution for the these problems is NP complete [1].
Thus our algorithms find only a close-to-optimal solution."
Benutzen Compiler (zb der avr-gcc) sowas eigentlich zur Optimierung von
Multiplikationen mit konstanten Werten?
Das ersetzen von Multiplikationen mit 2er-Potenzen gehört ja zum
Standard. Hier muss natürlich auch erücksichtigt werden, ob der
Prozessor einen Barrelshifter hat, oder nicht. Das war iirc ja mal ein
Problem beim avr-gcc, dass er multiplikation zu shift "optimiert" hat,
auch wenn der AVR hardwaremäßig multiplizieren konnte..
Bei einem Faktor von 1011 1111 1001b funktioniert dieser Trick auch ganz
schön:
(reg1 soll mit 0xbf9 multipliziert werden, der Einfachheit halber sei
reg1=1)
Johannes schrieb:> Gibt es einen bekannten Algorithmus,
Jupp, schau z.B. in die GCC-Quellen.
Der macht das nämlich so; irgendwo in der Gegend von expmed.c.
