[Nosferatu]

Hallo,

ich habe als Aufgabe ein Assembler Programm zu schreiben, das zwei 32 Bit Wörter mit Vorzeichen multipliziert. Als Befehlssatz habe ich zur Verfügung: ADD, SUB, AND, OR, NOT, SL, SR. Desweiteren stehen mir dafür 10 Register zur Verfügung.

Als triviale Methode fällt mir ein einfach für jede 1 im Multiplikator den Multiplikant in ein Register aufzuaddieren. Das ist allerdings sehr langsam.

Kennt da jemand einen guten Algorithmus der auch noch einfach zu implementieren ist? Wenns was fertig gibt wäre das auch optimal.

Gruß

[highpinger]

sind deine zahlen denn inder betrag vorzeichen darstellung?




Beispiel für die (schriftliche) Multiplikation von zwei positiven 4Bit Zahlen:

1011 * 1100 ( = 11*12)
-----------
....1011...
+....1011..
+.....0000.
+......0000
----111----- (Übertrag)
=  10000100 = 128 + 4 = 132 = 11*12  check :)

Ein Beispiel für eine Multiplikation von 1011 mit einer 4Bit Zahl X=abcd:

1011 * abcd
-----------
....1011... * a
+....1011.. * b
+.....1011. * c
+......1011 * d
-----------
ist gleich
-----------  (Nullen auffüllen)
....1011000 * a
+....101100 * b
+.....10110 * c
+......1011 * d
-----------
ist gleich
-----------
 1011 * a * 2^3
+ 1011 * b * 2^2
+ 1011 * c * 2^1
+ 1011 * d * 2^0

Wir haben schonmal Summen und Multiplizieren mit 2 entspricht einem ShiftLeft, 2^3 also 3*Shiftleft.
Es müssen also noch die Ausdrücke 1011 * x auswertet werden.
Es muss vergliechen werden:
-> x = 0, dann ist der Ausdruck Null,
-> x = 1, dann ist der Ausdruck 1011.


Ein Algorithmus für A*B könnte also so lauten:
1. Vergleiche die Vorzeichen Bits:
wenn => +
sonst -
2. , wenn springe zu 7.
3. wenn Bit , dann springe zu 6.
4. shifte Betrag(A) um i Stellen nach links.
5. Addiere das Teilergebnis zu deinem Gesamtergebnis
6. i++, springe zu 2.
7. fertig

Dies enthält jetzt die Multiplikation! Du hast allerdings eine Wortlänge von 32 bit und das Endergebnis hat 64 Bit!
Du musst also noch aufteilen, dass die Rechnungen alle in 32 Bit Register passen.

viel spaß damit^^




**edit**

für das mit dem high und low register:
das was zu zum high hinzuaddieren must ist der Betrag von A um (31-i)Bit nach rechts
und das zu low um i Bit nach links geshiftet