Hagen Völzke

Teil 3: Die verwendeten Algorithmen Mit einer eingehenden Besprechung der verwendeten Algorithmen wird in diesem Teil des Artikels mit der Realisierung der Fließkommaroutinen fortgefahren. Dabei kommen Addition, Subtraktion, Multiplikation und Division von Fließkommazahlen zur Sprache, außerdem gibt es das Listing für den Z80.

Nachdem schon im letzten Teil dieser Serie die Programm-Versionen für die Prozessoren 68000 und 8086 (sowie deren kompatible Brüder) abgedruckt wurden, sollen diesmal die dahinter stehenden Algorithmen zur Sprache kommen - natürlich mit Flußdiagramm und allen Erläuterungen, die den Einsatz auch auf anderen Prozessoren möglich machen.

Wir beginnen mit der Addition bzw. Subtraktion zweier Fließkommazahlen (Flußdiagramm in Bild 1).

Die Behandlung der NaNs und Unendlich muß - falls gewünscht - vom Programmierer selbst vor die eigentliche Additions- bzw. Subtraktionsroutine gestellt werden. Sie kann aber auch ersatzlos entfallen, denn die Darstellung der Werte +∞ und -∞ ist in der IEEE-Norm so gewählt, daß sie wahlweise auch als (MAXFLOAT+1) (größte darstellbare Fließkommazahl + 1) bzw. als -(MAXFLOAT+1) interpretiert werden können. Werden sie vor der eigentlichen Berechnungs-Routine nicht abgefangen, so verarbeitet diese die Darstellungen von ±∞ einfach als sehr große Zahlen.
Im Falle einer Subtraktion wird das Vorzeichen des zweiten Operanden umgedreht und dann in die Additionsroutine gesprungen. Die Additionsroutine berücksichtigt später das Vorzeichen der beiden Operanden und führt entweder eine Addition (beide Vorzeichen gleich) oder eine Subtraktion (die Vorzeichen sind verschieden) durch. Als ersten wichtigen Schritt muß man daher in der Additionsroutine die Vorzeichen beider Operanden vergleichen und ein Subtraktionsflag bei ungleichen Vorzeichen setzen. Das Ergebnisvorzeichen ist das Vorzeichen der betragsmäßig größeren Zahl. Im weiteren Verlauf werden die Exponenten abgetrennt (in CPU-Register geladen) und auf Null geprüft. Sind sie nämlich Null, so handelt es sich bei der jeweiligen Zahl um eine denormalisierte Zahl, der eine implizite Null vorangeht. Sind sie ungleich Null, so handelt es sich um eine normalisierte Zahl mit einer führenden Eins. Das vorher implizite Bit wird für die Berechnung explizit vor die Mantisse gestellt. Anschließend bilden wir die Differenz der beiden Exponenten. Ist sie größer als die Zahl der Stellen der Mantisse (also > 24), so sind weitere Berechnungen überflüssig, als Ergebnis wird die betragsmäßig größere Zahl zurückgegeben. Sonst muß nun die kleinere Zahl durch Rechtsschieben der Mantisse an den Exponenten der größeren Zahl angepaßt werden. Die Differenz der Exponenten gibt gerade die Zahl der nötigen Schiebeoperationen an. Der Exponent des Ergebnisses wird vorbesetzt mit dem Wert des Exponenten der größeren Zahl. Durch eventuelle Normalisierungsschritte beim Runden und nach der Berechnung der Summe bzw. Differenz kann er sich noch vergrößern oder verringern.

Die Subtraktionsflag bestimmt nun, ob die beiden Mantissen zusammengezählt oder voneinander abgezogen werden müssen. Nach der Addition kann ein Überlauf eintreten. In diesem Fall wird das Ergebnis wieder normalisiert. Bei der Subtraktion kann es passieren, daß das Ergebnis Null ist. In diesem Fall ist eine Normalisierung überflüssig. Ansonsten muß die Mantisse durch Linksschieben wieder normalisiert werden. Dabei kann der Exponent den Wert Null erreichen, bevor eine führende Eins in der Mantisse auftaucht. Das Ergebnis ist dann denormalisiert, und das Verschieben der Mantisse zur Normalisierung wird abgebrochen.
Im Anschluß an die Normalisierung wird die Rundung durchgeführt. Dazu addieren wir eine Eins zum 25. Bit der Mantisse (Bild 2).

Das 25. Bit entspricht dem „Guard-Bit", das die IEEE-Norm fordert. Ist das Guard-Bit Eins, so erfolgt ein Übertrag auf höhere Bits der Mantisse. Es kann dabei sogar ein Überlauf der gesamten Mantisse erfolgen. In diesem Fall muß die Mantisse wieder normalisiert werden (1 Bit nach rechts schieben, Exponent um 1 erhöhen). Nach der Rundung werden die führenden 24 Bit der Mantisse auf Null geprüft (die restlichen 8 Bit werden später nicht abgespeichert). Falls die Mantisse Null ist, so ist das Gesamtergebnis auch Null. Sonst müssen wir den Exponenten-Überlauf behandeln. Durch Rundungsund Normalisierungsschritte während der Berechnung kann es vorkommen, daß der Exponent den Wert MAXEXPO erreicht oder überschreitet. In diesem Fall wird als Ergebnis „unendlich" zurückgeliefert. An dieser Stelle könnte man auch eine Überlauf-Exception oder einen Laufzeitfehler (Sprung zu einer Fehler-Routine) erzeugen. Falls der Exponent nicht übergelaufen ist, so kann er genau Null sein. In diesem Fall ist das Ergebnis denormalisiert, das implizite Bit ist eine Null, der Bias des Exponenten beträgt dann 126 statt 127. Ist der Exponent ungleich Null, so wird die führende Eins aus der Mantisse ausgeschoben, da sie nicht mit abgespeichert wird (implizite Eins). (Den unterschiedlichen Bias bei normalisierter und denormalisierter Darstellung müssen wir nicht weiter behandeln, da durch das Auslassen der Mantissenverschiebung automatisch die nötige Korrektur durchgeführt wird). Zum Abschluß der Additionsroutine müssen nun der Exponent, das Ergebnisvorzeichen und die Mantisse wieder zusammengesetzt werden und in das im letzten Teil der Artikelserie angegebene Format einer Single-Precision-Zahl gebracht werden. Der Bias, mit dem der Exponent einer Fließkommazahl behaftet ist, muß an keiner Stelle explizit zu- oder abgerechnet werden, da der Ergebnisexponent aus dem Exponenten der größeren Zahl gewonnen wird und damit den bereits vorhandenen Bias übernimmt.

An verschiedenen Stellen im Flußdiagramm wurde von der betragsmäßig größeren und betragsmäßig kleineren Zahl gesprochen. Um diese Auswahl zu treffen, müssen wir erst einmal wissen, wie man die Größe der beiden Zahlen vergleicht - ohne die Subtraktion zu benutzten, denn dann wäre unser Problem selbstrekursiv! Bild 3 erläutert diesen Schritt: Durch Rotation werden die beiden Fließkommazahlen zunächst in ein temporäres Format gebracht.

Dieses Format hat auch den Vorteil, daß sich der Exponent verhältnismäßig leicht abtrennen läßt, da er jetzt in einem eigenen Byte steht. Nun subtrahiert man die beiden „Bitstrings" der Fließkommazahlen unter Verwendung einer normalen Integer-Subtraktion voneinander. Beim Bilden der bitweisen Differenz zweier Fließkommazahlen im temporären Format ergibt sich die Differenz „D" nach folgenden Regeln:

	⌈	wenn E1 > E2
D ≥ 0	⟨	wenn El = E2 und F1 > F2
	⌊	wenn E1 = E2 und F1 = F2 und S1≥ S2

Mit der Differenz D wird vor jeder Addition oder Subtraktion darüber entschieden, welcher Operand betragsmäßig größer ist. D ist immer positiv, wenn der erste Exponent größer als der zweite Exponent ist (dann ist die erste Zahl betragsmäßig sicher größer als die zweite). Sind die Exponenten gleich, so sind die Mantissen ausschlaggebend. Nur bei gleichen Mantissen und gleichen Exponenten wirken sich die Vorzeichenbits bei der Entscheidung aus: Hier würde im schlimmsten Fall - bei S = 1 und S2 = 0 - eine unnötige Vertauschung der beiden Operanden stattfinden, was aber keinen Fehler im Ergebnis bewirkt: Die Summe zweier gleicher Zahlen mit umgekehrten Vorzeichen ergibt ohnehin Null.

Das Ergebnis liefert gleich zwei Informationen:

—	Die Subtraktionsflag im untersten Bit (gewissermaßen die EXOR-Verknüpfung beider Vorzeichen) und
—	Die Aussage, welche der beiden Zahlen die größere ist.

Da das Vorzeichenflag der beiden Zahlen bei dieser Subtraktion einfach mit Mantisse und Exponent verrechnet wird, muß man sich schon überlegen, ob diese Operation für alle Kombinationen von Eingangsparametern ein korrektes Ergebnis liefert. Mögliche Eingangsparameter sind normalisierte Zahlen, denormalisierte Zahlen, positive und negative Zahlen sowie sämtliche möglichen Kombinationen davon. Daß das Ergebnis korrekt ist, zeigen die weiteren Erläuterungen in Bild 3. Die Software-Version für den Z80 arbeitet allerdings nicht nach diesem Prinzip, da die Schiebeoperationen bei der CPU Z80 zu ineffizient wären: Bei diesem Prozessor wird zunächst das Ergebnisvorzeichen bestimmt, dann werden die beiden Vorzeichenbits gelöscht. Nun können die verbleibenden Bitstrings (bestehend aus Exponent und Mantisse) voneinander subtrahiert werden, um den Größenvergleich durchzuführen.

Betrachten wir dazu das Flußdiagramm (Bild 4).

Da die beiden Algorithmen sehr verwandt sind, wurden sie beide in ein Flußdiagramm eingezeichnet. Zunächst verlaufen beide parallel: Das Ergebnis-Vorzeichen wird bestimmt, die Exponenten werden von der Mantisse abgetrennt und vor die Mantisse wird (je nach Exponent) eine führende Null oder führende Eins gestellt. Bei der Multiplikation werden nun die beiden Exponenten addiert. Da die Exponenten jeweils mit dem Bias behaftet sind, ist der Ergebnisexponent mit dem zweifachen Bias behaftet. Daher muß einmal der Bias subtrahiert werden. Entsprechendes gilt für die Division: Die beiden Exponenten werden voneinander subtrahiert, das Ergebnis ist dann ohne Bias, deshalb muß der einfache Bias wieder addiert werden. Sowohl bei der Multiplikation als auch bei der Division müssen wir berücksichtigen, daß die denormalisierten Zahlen einen Bias von 126 haben, die normalisierten Zahlen einen von 127.

Falls die Summe bzw. Differenz der beiden Exponenten - nach der Bias-Korrektur - kleiner als -24 ist, so haben wir von vornherein den totalen Unterlauf und können die Berechnung abbrechen. Das Ergebnis ist dann Null. Sonst werden bei der Multiplikation jetzt die Mantissen miteinander multipliziert, bei der Division durcheinander dividiert. Wie das funktioniert, zeigt der nächste Abschnitt. Vor der Division müssen wir prüfen, ob der Divisor Null ist. Falls ja, so geben wir als Ergebnis ∞ zurück und brechen ab. Alternativ könnte hier auch ein „Division-durch-Null"-Fehler erzeugt werden. Anschließend wird das Ergebnis wird auf Null geprüft (Null ergibt sich, falls bei der Multiplikation einer der beiden Faktoren Null ist oder falls bei der Division der Dividend Null ist).

Falls das Ergebnis ungleich Null ist, so wird die Mantisse normalisiert und gerundet. Jetzt prüfen wir auf Überlauf. Überlauf erkennen wir daran, daß der Exponent MAXEXPO erreicht hat. Falls Überlauf eintritt, wird als Ergebnis ∞ erzeugt. Sonst müssen wir auf Unterlauf prüfen. Unterlauf tritt ein, wenn der Exponent kleiner als Null geworden ist (wir rechnen immer mit einem Bias-behafteten Exponenten!). Falls der Exponent kleiner oder gleich -24 ist, so erhalten wir totalen Unterlauf und können als Ergebnis Null zurückgeben. Sonst ist das Ergebnis denormalisiert und wir verschieben die Mantisse so oft nach rechts, bis der Exponent wieder Null wird. (Bei jeder Verschiebung nach rechts wird zum Ausgleich der Exponent erhöht). Diesen Vorgang nennt man denormalisieren. Tritt kein Unterlauf ein, müssen wir prüfen, ob der Exponent genau Null ist. Dann ist das Ergebnis ebenfalls denormalisiert. Sonst verfahren wir wie bei der Addition: die führende Eins der Mantisse wird rausgeschoben und zum Schluß der Routine müssen nun der Exponent, das Ergebnisvorzeichen und die Mantisse wieder zusammengesetzt werden und in das Format Single-Precision-Zahl gebracht werden. Bei der Realisierung der Fließkommaroutinen weichen wir von diesem Flußdiagramm aus Effizienzgründen leicht ab:

—	Bei der Multiplikation wird die Mantisse nur soweit normalisiert, daß der Exponent nicht negativ wird (sonst müssen wir später wieder denormalisieren).
—	Bei der Division wird nicht einfach naiv dividiert, sondern die Division wird solange berechnet, bis entweder ein bereits normalisiertes Ergebnis vorliegt, oder wegen Exponentenunterlaufs abgebrochen werden muß.

Je nach Leistung des verwendeten Mikroprozessors stellt uns die Aufgabe, die beiden Mantissen miteinander zu multiplizieren, vor verschieden große Probleme. Tabelle 1 zeigt exemplarisch den Rechenvorgang bei der Multiplikation zweier Dezimalzahlen und dessen Pendant im Binärsystem.

Die schriftliche Multiplikation arbeitet nach einem einfachen Verfahren: die erste Zahl wird nacheinander mit jeder einzelnen Ziffer der zweiten Zahl multipliziert. Entsprechend der Stelligkeit der gerade verwendeten einzelnen Ziffer werden die entstehenden Produkte untereinander aufgeschrieben und anschließend aufsummiert. Im Binärsystem gibt es bekanntlich nur die Ziffern 0 und 1. Das bedeutet, daß die Berechnung der einzelnen Zwischenprodukte trivial ist, da nur mit 0 oder 1 multipliziert werden muß. Wir können mit diesem Wissen nun einen Algorithmus formulieren, der zwei Binärzahlen miteinander multipliziert. Ein paar Rahmenbedingungen müssen wir allerdings noch betrachten. Die Mantissen unserer beiden Faktoren sind jeweils 24 Bit lang. Bei der Multiplikation entsteht ein bis zu 48 Bit langes Ergebnis. Sind beide Faktoren normalisiert, so werden wir nur wenig mehr als die Hälfte der berechneten Bits benötigen, denn in Single-Precision werden nur 24 Bit für die Mantisse reserviert, zwei Bit werden noch für eine eventuell nötige Normalisierung und für die Rundung benötigt. Man könnte also auf die Idee kommen, nur die ersten 32 Bit des Produktes zu berechnen und die übrigen 16 Bit zu vernachlässigen. Der dabei entstehende Rechenfehler ist so gering, daß diese Beschränkung durchaus zulässig wäre. Allerdings wollen wir auch denormalisierte Zahlen miteinander multiplizieren. Für diesen Fall werden meistens auch die restlichen 16 Bit benötigt. Wir berechnen daher immer die gesamten 48 Bit des Produktes. Eine kommentierte Formulierung zum Verständnis des Multiplikationsalgorithmus finden Sie ebenfalls in Tabelle 1. Die Mikroprozessoren 68000 und 8086 bieten nun bereits Multiplikationsbefehle, die in der Lage sind, zwei 16-Bit Zahlen miteinander zu multiplizieren und ein 32-Bit Ergebnis zu erzeugen. Statt das oben beschriebene Verfahren zu benutzen, liegt der Wunsch nahe, diese doch schnelleren CPU-Befehle einzusetzen. Das ist verhältnismäßig einfach möglich. Wir erweitern dazu unsere Mantissen auf 32 Bit durch Voranstellen von führenden Nullen (siehe Tabelle 1). Wir benutzen nun die Multiplikationsbefehle, um die Hälften der Mantissen paarweise miteinander zu multiplizieren. Die Ergebnisse werden anschließend entsprechend ihrer Wertigkeit aufaddiert. Mit nur vier CPU-Multiplikations-Befehlen wird zunächst ein 64-Bit-Produkt berechnet, von dem allerdings nur die niederen 48 Bit signifikant sind. Beim Prozessor Z80 müssen wir allerdings das erste Verfahren verwenden, da diese CPU keine Multiplikationsbefehle kennt (Bild 5).

Zum Dividieren der Mantissen muß man auch bei der CPU 68000 oder 8086 „zu Fuß" rechnen. Die eingebauten Divisionsbefehle liefern nämlich nur ein 16-Bit-Ergebnis und lassen sich nicht so einfach wie die Multiplikationsbefehle zum Rechnen mit höherer Genauigkeit bewegen.
Analog zur schriftlichen Multiplikation verwenden wir nun die schriftliche Division, Tabelle 2 soll das zugrunde liegende Prinzip erläutern.

Aus Gründen der Vereinfachung des Algorithmus gehen wir davon aus, daß uns zwei normalisierte Mantissen vorliegen. Das ist schließlich der Normalfall. Werden denormalisierte Mantissen durcheinander dividiert, so muß der Algorithmus das durch eine Sonderbehandlung berücksichtigen. Für die Division im Dezimalsystem sind zwei Beispiele gegeben: im ersten ist der Dividend größer als der Divisor, so daß der Quotient (das Ergebnis) bereits normalisiert ist. Im zweiten Beispiel sind die Größenverhältnisse umgekehrt, das Ergebnis ist dann denormalisiert und kann durch eine Kommaverschiebung um eine Stelle wieder normalisiert werden. Im Dezimalsystem zerlegt die schriftliche Division die gesamte Berechnung in einfache Divisionen von kleinen Zahlen, die der Mensch im Kopf berechnen kann.

Im Binärsystem sind diese einfachen Divisionen wieder trivial: Entweder kann einmal dividiert werden oder keinmal (1 oder 0). Ob dividiert werden kann, bestimmt ein Vergleich: Ist der Dividend größer als der Divisor (oder gleich), kann dividiert werden, ist er kleiner, kann nicht dividiert werden. Falls dividiert werden kann, notieren wir für das Ergebnis eine 1 (sonst eine 0) und subtrahieren den Divisor vom Dividenden. Anschließend wird der Dividend um eine Stelle nach links geschoben und das nächste Ergebnisbit bestimmt. Eine Schleife läuft solange durch diesen Algorithmus, bis 25 signifikante Bits berechnet sind. Im Assemblerprogramm wird statt des Vergleiches sofort die Subtraktion durchgeführt. Liefert sie einen Übertrag (Carry), so kann nicht dividiert werden und die Subtraktion wird durch Rückkopieren des alten Dividenden wieder aufgehoben. Dadurch gewinnt der Algorithmus beim Z80 und 8086 etwas an Geschwindigkeit. Das letzte Beispiel in Tabelle 2 zeigt den Ablauf der Division von 26/7 im Binärsystem. Dargestellt sind jeweils die normalisierten Mantissen der beiden Zahlen. Die Exponenten sind getrennt angegeben. Vor der Division werden die beiden Mantissen um ein Bit nach rechts verschoben, so daß sie mit einer führenden Null beginnen. Dadurch läßt sich die Division durch einen Divisor, der größer ist als der Dividend, leichter handhaben (das Ergebnis ist dann kleiner als 1, nach der Berechnung wird ein Normalisierungsschritt notwendig).
Wie schon erwähnt durchlaufen wir die Divisionsschleife, bis 25 signifikante Bits berechnet sind. Das 25. Bit benötigen wir wieder zum Runden. Die Divisionsschleife kann aber auch vorzeitig abgebrochen werden. Dazu wird bei jedem Schleifendurchlauf der Ergebnisexponent geprüft. Droht ein Unterlauf, so wird die Divisionsschleife abgebrochen, das Ergebnis ist dann denormalisiert. Auch für die schriftliche Division ist ein informeller Algorithmus angegeben.

Wenn Sie die Assemblerlistings studieren, so fällt als erstes der große Längenunterschied zwischen den Listings auf. Die CPU 68000 liefert den kompaktesten Code und - bei äquivalentem Datendurchsatz - die höchste Rechengeschwindigkeit. Das liegt zum einen daran, daß diese CPU über viele universelle Register verfügt und problemlos mit 32-Bit-Zahlen umgehen kann. Der 8086 verfügt nur über wenige Register, die oft für spezielle Befehle reserviert werden müssen. Außerdem kann er nur mit 16-Bit-Zahlen umgehen. Besonders bei Schiebeoperationen hat der 68000 hier Vorteile, da Register-Shifts gleich um mehrere Bits auf einmal vorgenommen werden können. Der 8086 hingegen hat den Vorteil, daß jedes Register auch byteweise angesprochen werden kann. Trotzdem beansprucht der Code für die CPU 8086 schon wesentlich mehr Platz als der für den Prozessor 68000. Wegen der geringen Zahl der Register ist beim 8086 eine Parameterübergabe über den Stack unumgänglich, beim 68000 kann man ruhigen Gewissens zwei der acht Datenregister für Parameterübergaben verwenden. Die CPU Z80 schließlich bietet deutlich Nachteile bei der Parameterübergabe - vor allem dadurch, daß auf den Stackpointer der CPU nicht vernünftig zugegriffen werden kann: Das ist nur durch das Auslagern in eine absolute Speicherzelle möglich. Dadurch ist der Z80-Code auch nicht reentrant. Da der Z80 nur mit Bytes umgehen kann und keine Multiplikationsbefehle besitzt, werden schon aus einfachen Schiebeoperationen größere Programmsequenzen. Die Geschwindigkeit der Fließkommaoperationen beim Prozessor Z80 liegt deutlich unter der beim 8086 und 68000. Benchmarks der Routinen haben ergeben, daß sie mit den erhältlichen Bibliotheken für die jeweiligen Prozessoren voll konkurrenzfähig sind, zumal die wenigsten Bibliotheken das Rechnen mit denormalisierten Zahlen unterstützen.

An den Routinen sind trotz ihrer guten Geschwindigkeit noch einige Optimierungen möglich. Schiebeoperationen um mehr als acht Bits können z.B. in einen byteweisen Transfer, gefolgt von einer Schiebeoperation um die restlichen Bits, realisiert werden. Bei Normalisierungs- und Anpassungsvorgängen bringt dies noch einiges an Geschwindigkeit. Sicherlich kann auch die Verwendung der CPU-Register beim 8086 und Z80 verbessert werden. Allerdings sollten die Programmlistings nicht unnötig verlängert und verkompliziert werden. Multiplikationen (und Divisionen) mit Zweierpotenzen können wesentlich beschleunigt werden, wenn man dafür spezielle Routinen zur Verfügung stellt. Im nächsten Heft wird eine solche Funktion vorgestellt.

Im letzten Teil dieser Serie in mc 11/88 ist uns auf der Seite 80 leider ein kleiner Fehler unterlaufen. Rechts oben beim Beispiel für eine Multiplikation ist das Ergebnis von 4,0 × 10² × 2,0 × 10³ natürlich 8,0 × 10⁵.

Im nächsten Teil des Artikels werden die Konvertierungsroutinen sowie die Multiplikation mit Zweierpotenzen besprochen. Konvertiert wird

—	von Integer nach Float
—	von Float nach Integer
—	von ASCII nach Float
—	von Float nach ASCII.

Außerdem werden kurze Beispielprogramme den Aufruf der Fließkommafunktionen erläutern.

mc Heft 1 gibt es ab 27. Dezember an Ihrem Kiosk.