FIN

Anmerkung: Dieser Artikel beschreibt die numerische FIN-Routine zur Umwandlung von Strings in Fließkommazahlen im BASIC-ROM.

Name:			FIN
Beschreibung:			ASCII-String nach Fließkommazahl im Fließkommaregister FAC wandeln
Einsprungpunkt:			$BCF3 / 48371
Übergebene Argumente:
Akkumulator:			erstes Zeichen des einzulesenden Strings
Carry-Flag:			gelöscht, falls A eine Ziffer (ASCII $30...$39) enthält, gesetzt sonst
Sonstige:			Adresse 122/$7A (Low-Byte) / 123/$7B (High-Byte) = Zeiger auf einzulesenden numerischen String
Rückgabe-Werte:
Sonstige:			FAC = eingelesene Zahl

FIN — manchmal auch als STRFLP oder ASCFLOAT bezeichnet — liest einen numerischen ASCII-String ein und wandelt ihn in eine Fließkommazahl, die dann im Fließkommaregister FAC abgelegt wird. Da der String über die CHRGET-Routine eingelesen wird, muss die Anfangsadresse des Strings im Lesezeiger dieser Routine an den Adressen 122/$7A (Low-Byte) und 123/$7B (High-Byte) übergeben werden. Ferner muss sich das erste Zeichen des Strings bereits im Akkumulator befinden, und das Carry-Flag muss genau dann gesetzt sein, wenn es sich dabei um eine Ziffer handelt — diese Bedingungen lassen sich am einfachsten dadurch erfüllen, dass man unmittelbar vor dem Einsprung in FIN die Routine CHRGOT aufruft.

Der Aufruf von FIN nutzt den Speicherbereich an den Adressen 93/$5D bis 103/$67 als Puffer und bewegt den Lesezeiger der CHRGET-Routine weiter zum ersten Zeichen, das nicht zum numerischen Eingabestring gehört.

Algorithmus

Da FIN die Routine CHRGET für das Einlesen des Strings benutzt, akzeptiert und überliest FIN Leerzeichen an beliebiger Stelle und in beliebiger Anzahl. Ansonsten erwartet FIN nacheinander optional ein Vorzeichen ("+" oder "-"), null oder mehr Ziffern, und danach optional einen Dezimalpunkt gefolgt von null oder mehr Ziffern. Bei einer Zahl in wissenschaftlicher Notation kann sich hieran zuletzt noch ein Exponent anschließen, also das Zeichen 'E', optional gefolgt von einem Vorzeichen ("+" oder "-") und von einer Zahl im Bereich [ -99; 99 ] bestehend aus null oder mehr Ziffern.

1. Im ersten Schritt unterscheidet FIN, ob die einzulesende Zahl mit einem Vorzeichen ("+" oder "-") beginnt, und setzt in bei einem Minuszeichen das Vorzeichenflag an Adresse 103/$67 auf den Wert 255/$FF.
2. Anschließend liest und verarbeitet FIN nacheinander die Ziffern des Strings. Hierfür wird, beginnend mit einem Startwert von FAC = 0, für jedes Zeichen der Inhalt von FAC verzehnfacht und der Wert der neu eingelesenen Ziffer hinzuaddiert. Falls FIN hierbei auf einen Dezimalpunkt trifft, so wird das Dezimalpunkt-Flag in Bit 7 von Adresse 95/$5F geprüft: War dieses Flag bereits gesetzt, so handelt es sich um den zweiten Dezimalpunkt und die Wandlung ist zu Ende, ansonsten wird das Flag gesetzt und an Adresse 93/$5D ab diesem Zeitpunkt die Anzahl der Nachkommastellen mitgezählt.
3. Stößt FIN beim Einlesen auf das Zeichen "E", so enthält der String eine Zahl in wissenschaftlicher Notation. Bei negativem Vorzeichen des Exponenten wird Bit 7 an Adresse 96/$60 gesetzt, anschließend dient Speicherzelle 94/$5E als Zwischenspeicher des Exponenten. Für jede Ziffer wird der hier gespeicherte Wert verzehnfacht und die gerade gelesene Ziffer hinzuaddiert. Hatte der Exponent schon vor dieser Verzehnfachung den Wert 10 erreicht oder überschritten, so wird für positive Exponenten ein ?OVERFLOW ERROR ausgelöst, für negative Exponenten ein Wert von -100 angenommen und damit ein Wert der eingelesenen Zahl von 0 erzwungen.
4. Nun negiert FIN noch den Exponenten, falls er laut Speicherzelle 96/$60 ein ein negatives Vorzeichen hatte. Anschließend wird die Differenz aus Exponent und Anzahl der Nachkommastellen berechnet; sie gibt an, wie oft die Mantisse von FAC nun noch mit 10 multipliziert (bei positiver Differenz) oder durch 10 dividiert (bei negativer Differenz) werden muss, bis FAC den richtigen Betrag hat.
5. Zuletzt wird noch das Vorzeichen-Flag an Adresse 103/$67 geprüft und FAC negiert, falls das Vorzeichen der Zahl negativ war.

Laufzeitverhalten

Die Laufzeit von FIN wird hauptsächlich bestimmt durch die Anzahl der Ziffern im einzulesenden String und durch die Anzahl der abschließenden Multiplikationen mit 10 oder Divisionen durch 10 (also durch die Differenz aus dem Exponenten der wissenschaftlichen Notation und der Anzahl der Nachkommastellen). Das nachfolgende Schaubild zeigt die Rechenzeit für das Einlesen der Zahlen 1 bis 1000000. Auf der Abszissenachse aufgetragen ist für jede Zahl x der Wert log₁₀(x)+1, entsprechend in etwa der Zahl der Ziffern von x. Deutlich erkennbar ist, dass bei von 0 verschiedenen Zahlen die Rechenzeit pro zusätzliche Ziffer um etwa 1000 Systemtakte ansteigt (führende Nullen benötigen jeweils 639 Takte). Falls im vierten Schritt des Algorithmus noch Multiplikationen mit 10 erforderlich sind, so benötigen diese jeweils rund 400 Systemtakte; Divisionen durch 10 dauern jeweils rund 2500 Takte.

Wenn FIN mit einem Zeiger auf ein ungültiges Zeichen aufgerufen wird, so liefert die Routine bereits nach 154 Systemtakten den Wert 0 zurück. Die am schnellsten einzulesenden, von 0 verschiedenen Zahlen sind mit einer Rechenzeit von 698 Takten die Einzelziffern "8" und "9". Eine Obergrenze für die Laufzeit ergibt sich nur aufgrund des eingeschränkten Wertebereichs für Fließkommazahlen und der auf 255 Zeichen beschränkten Länge von Strings im Commodore-BASIC. Bei ausführlichen Tests hat der String "000...000.000...000160927577777777777777777777777777777777" (mit 125 führenden Nullen, und nach dem Dezimalpunkt 89 Nullen und 39 weitere Ziffern) eine Rekord-Laufzeit von 413029 Takten erzielt.

Ein Systemtakt entspricht auf dem Commodore 64 rund einer Mikrosekunde (μs). Die FIN-Routine benötigt also bereits für das Einlesen gewöhnlicher Dezimalbrüche rund 1 ms pro Ziffer plus 2.5 ms pro Nachkommastelle. Bei zeitkritischen Berechnungen lohnt es sich daher, alle numerischen Konstanten zu Beginn des Programms in Real-Variablen zu übertragen und numerische Operationen anschließend nur mit diesen vorzunehmen.

Bugs

Der Algorithmus, mit dessen Hilfe FIN einen String einliest und in eine Fließkommazahl umwandelt, verwendet an einigen Stellen Zwischenergebnisse, die möglicherweise die Speichermöglichkeiten der ROM-Routine sprengen, auch wenn sich die Zahl selbst problemlos im Fließkommaformat des C64 darstellen ließe. Die dadurch verursachten Fehler hätten sich natürlich durch Erkennung und Behandlung der entsprechenden Sonderfälle vermeiden lassen. Für praktische Anwendungen sind die nachfolgend aufgeführten Bugs allerdings ohne Belang:

• Da FIN zunächst die Mantisse der Zahl ohne Berücksichtigung des Dezimalpunkts einliest und erst anschließend einen eventuellen Exponenten zur Basis 10 (gegeben durch Nachkommastellen oder wissenschaftliche Notation) einfließen lässt, kann es beim Einlesen zu einem ?OVERFLOW ERROR kommen, beispielsweise bei der Zahl 9 mit 38 Nachkommastellen:

?9.00000000000000000000000000000000000000 ?OVERFLOW ERROR

• Die wiederholte Multiplikation und anschließende Division mit der Konstanten 10 führt zu Rundungsfehlern, sobald das auf diese Weise berechnete Zwischenergebnis nicht mehr in der Mantisse des Fließkommaakkus FAC Platz findet, beispielsweise bei der Zahl "9" mit 25 Nachkommastellen:

?9.0000000000000000000000000 9.00000001

• Zuletzt meldet die Beschränkung des Exponenten auf den Wertebereich bis 99 auch dann einen ?OVERFLOW ERROR, wenn der Wert der Mantisse und damit die Zahl selbst gleich 0 ist:

?0E100 ?OVERFLOW ERROR

Weblinks

• Disassembly von FIN/$BCF3 auf All About Your 64
• CodeBase 64: Floating Point Math
• C64 BASIC & KERNAL ROM Disassembly von Michael Steil
• C64OS: Floating Point Math from BASIC