Division, Operation mit geteilten Dividend - Idee?

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo,

ich habe folgendes Problem.
Ich möchte in Assembler eine Zahl den Nutzer dezimal (ausgeben).
Ich muss also den Wert der Zahl in einzelne Dezimal-Ziffern darstellen.
Das geht ja ganz einfach:
i. Ziffer = ZAHL / 10^(n-i)

Das Problem ist nur, dass meine Zahl 2 Wörter (1 Double Word) groß ist und die arithmetischen Operationen nur 1 Word-Zahlen behandeln können.

Demzufolge muss ich die Operation zerlegen.
Bei der Multiplikation würde ich das so machen:
High Word * FAKTOR -> als Hight Word im Ergebnis speichern
Low Word * FAKTOR -> Low Word als Low Word ins Ergebnis und High Word = übertrag -> wird zum High Word dazu addiert

Aber wie kann man das bei einer Division machen? Wie kann ich die Division machen?

#2

Ich muss also den Wert der Zahl in einzelne Dezimal-Ziffern
darstellen.
Das geht ja ganz einfach:
i. Ziffer = ZAHL / 10^(n-i)

Das Problem ist nur, dass meine Zahl 2 Wörter (1 Double Word)
groß ist und die arithmetischen Operationen nur 1 Word-Zahlen
behandeln können.

Du teils so lange durch 10, bis das Doppelwort leer ist. Den jeweiligen Rest schreibst du von rechts nach links als Ziffern.

Das (grösste mögliche Wort + 1) / 10 ist der Faktor, mit dem du das HiWord multiplizierst, das Ergebnis merkst du dir. Der Rest aus (grösstes mögliche Wort + 1) / 10 wird ebenfalls mit dem HiWord multipliziert und zum LoWort addiert (möglichen Überlauf beachten!). Jetzt kannst du das LoWord dividieren und das Ergebnis zum Merker von vorhin hinzuaddieren. Im Merker hast du jetzt die durch 10 dividierte Zahl, der Rest aus der letzten Division wird als Ziffer plaziert.

Nehmen wir ein Wort als 8-bit und teilen 65535 (Hiword 255, LoWord 255). Das (grösste mögliche Wort + 1) / 10 = (255+1)/10 = 25, Rest 6.

HiWord*25 = 6375 -> Merker
HiWord*Rest + LoWord = 255*6 + 255 = 1785
Merker = Merker + 1785 / 10 = 6553
Erste Ziffer (von rechts) ist der Rest der letzten Division 1785 / 10, also 5

Der Merker enthält jetzt 6553. Hiword 25, LoWord 153
HiWord*25 = 625 -> Merker
HiWord*Rest + LoWord = 25*6 + 153 = 303
Merker = Merker + 303 / 10 = 655
Nächste Ziffer (von rechts) ist der Rest der letzten Division 303 / 10, also 3

Der Merker enthält jetzt 655. Hiword 2, LoWord 143
HiWord*25 = 50 -> Merker
HiWord*Rest + LoWord = 2*6 + 143 = 155
Merker = Merker + 155 / 10 = 65
Nächste Ziffer (von rechts) ist der Rest der letzten Division 155 / 10, also 5

Der Merker enthält jetzt 65. Hiword 0, LoWord 65
HiWord*25 = 0 -> Merker
HiWord*Rest + LoWord = 0*6 + 65 = 65
Merker = Merker + 65 / 10 = 6
Nächste Ziffer (von rechts) ist der Rest der letzten Division 65 / 10, also 5

Der Merker enthält jetzt 6. Hiword 0, LoWord 6
HiWord*25 = 0 -> Merker
HiWord*Rest + LoWord = 0*6 + 6 = 6
Merker = Merker + 6 / 10 = 0
Nächste Ziffer (von rechts) ist der Rest der letzten Division 6 / 10, also 6

Merker = 0 -> Wir haben fertig!

Ist programmtechnisch natürlich etwas schwieriger umzusetzen, weil du rekursiv arbeiten musst, da das Produkt aus HiWord*Rest + LoWord überlaufen kann.

HTH

#3

Wow! Hast dir ja richtig Mühe gegeben.
Riesen Lob von mir!! Danke.

Wie kommt man drauf? Ist das ein spezieller Algorithmus oder nur ein leicht angepasster Divisions-Algorithmus?
Ich kann zwar alles nachvollziehen (also für die Implementierung bin ich jetzt gerüstet), aber was genau dahinter steckt, konnte ich nicht rauslesen.

Ist programmtechnisch natürlich etwas schwieriger umzusetzen,
weil du rekursiv arbeiten musst, da das Produkt aus
HiWord*Rest + LoWord überlaufen kann.

In der Tat :smile: Du meinst jetzt z.B. die Zeile:

Merker = Merker + 1785 / 10 = 6553

#4

Wie kommt man drauf? Ist das ein spezieller Algorithmus oder
nur ein leicht angepasster Divisions-Algorithmus?

Zu Zeiten, als Haupt- und Festplattenspeicher noch in Mark (althochdeutsch für Euro) je Bit gerechnet wurden, wurden Zahlen bei kaufmännischen Aufgabenstellungen trotzdem extrem speicherfressend in BCD, Binary coded Decimals gespeichert. Weil es für die Buchhalter, die mit den Maschinen arbeiten sollten, eine viel zu komplexe Aufgabe gewesen wäre, binär abgelegte Zahlen in ein lesbares Format zu wandeln.

Mit der äusserst unschönen Tatsache, dass Computer mit einem binären Zahlensystem arbeiten, der Mensch seine Ausgaben aber im dezimalen Format vorzieht, wird man aber spätestens dann konfrontiert, wenn man anfängt, auf Primitivprozessoren wie dem ZX80 oder 65xx mathematische Probleme in Assembler anzugehen.

Ist programmtechnisch natürlich etwas schwieriger umzusetzen,
weil du rekursiv arbeiten musst, da das Produkt aus
HiWord*Rest + LoWord überlaufen kann.

In der Tat :smile: Du meinst jetzt z.B. die Zeile:

Merker = Merker + 1785 / 10 = 6553

Nein, dort ist der Überlauf nicht überraschend. Das Ergebnis aus

HiWord*Rest + LoWord = 255*6 + 255 = 1785

musst du zwischenspeichern, und an der Stelle könnte man versucht sein, als Zwischenspeicher ein Singleword zu verwenden. In meinen ersten Gedankenexperimenten habe ich nicht mit 65535, sondern mit wesentlich kleineren Zahlen gerechnet, und da waren die Zwischenergebnisse immer weit von einem Überlauf entfernt.

Aber egal, das Problem ist eigentlich etwas tiefer reichend. Auch wenn es dir zunächst nur darum geht, eine Division über Wortgrenzen hinaus zu realisieren, wirst du doch eine komplette Doppelwort-Arithmetik aufbauen müssen. Um Doppelwörter zu dividieren, musst du vorher zumindest eine Doppelwort-Addition und eine Doppelword-Multiplikation programmieren. Im Grunde bastelst du dir also eine in Software gegossene eigene CPU, und wenn du der noch hinreichend breite Register verpasst, ist das Überlaufproblem (im konkreten Fall) bereits gegessen.

Gruß