POLY

Aus C64-Wiki
Zur Navigation springenZur Suche springen

Anmerkung: Dieser Artikel beschreibt die POLY-Routine zur Auswertung von Polynomen im BASIC-ROM.

Name: POLY
Beschreibung: Polynomauswertung für Fließkommaregister FAC
Einsprungpunkt: $E059 / 57433
Übergebene Argumente:
Akkumulator: Adresse der Polynomkoeffizienten (Low-Byte)
Y-Register: Adresse der Polynomkoeffizienten (High-Byte)
Rückgabe-Werte:
Akkumulator: 92/$5C
Y-Register: 0

POLY[1][2] — manchmal auch als POLYNOM[3] bezeichnet — wertet ein Polynom an der Stelle aus, die durch die im Fließkommaregister FAC gespeicherte Zahl gegeben ist. Die Adresse, ab der die Definition des Polynoms gespeichert ist, wird im Akkumulator (Low-Byte) und im Y-Register (High-Byte) übergeben. POLY erwartet an dieser Adresse zunächst den Grad des Polynoms (1 Byte, ein Nullbyte wird als Polynom 256. Grades interpretiert) und danach alle Koeffizienten im kompakten 5 Byte-Format, wie es zum Speichern von REAL-Variablen verwendet wird. Die Reihe der Koeffizienten beginnt mit der Beizahl der höchsten Potenz von FAC und endet mit der Konstanten, die im letzten Schritt der Berechnung zum Wert des Polynoms addiert wird.

Nach dem Aufruf steht in FAC der Wert des Polynoms, während der Inhalt von ARG undefiniert ist.

Neben dem Inhalt der Fließkommaregister FAC und ARG ändert POLY auch den Zähler an Adresse 103/$67, die Hilfszeiger an den Adressen 34/$22 (Low-Byte) und 35/$23 (High-Byte) sowie 113/$71 (Low-Byte) und 114/$72 (High-Byte) und das Fließkommaregister FAC#4 an den Adressen 92/$5C bis 96/$60.

POLY wird von der ROM-Routine EXP aufgerufen. Weil auch die ROM-Routine POLYX auf POLY beruht, ist POLY ferner die Grundlage für die ROM-Routinen LOG, COS, SIN und ATN.

Algorithmus[Bearbeiten | Quelltext bearbeiten]

POLY setzt bei der Berechnung das Horner-Schema ein, berechnet das Polynom n. Grades

anxn + an-1xn-1 + ... + a2x2 + a1 x + a0

also gemäß der Formel:

(((anx + an-1) x + ... + a2) x + a1) x + a0.
  1. Zunächst überträgt POLY den Inhalt von FAC in das Fließkommaregister FAC#4, da FAC während der Berechnung als Speicher für Teilsummen und -produkte benötigt wird. Zudem wird der Grad des Polynoms an die Adresse 103/$67 übertragen, wo er dann als Zähler für die noch zu verarbeitenden Koeffizienten dient.
  2. Im ersten Rechenschritt wird nun durch Aufruf von FMULT zunächst das Produkt anx berechnet und hierzu dann mittels FADD der nächste Koeffizient an-1 addiert.
  3. In jedem weiteren Schritt wird das bisherige Zwischenergebnis mit dem in FAC#4 gespeicherten Wert von x multipliziert und dann der nachfolgende Koeffiziert hinzuaddiert. Dies wird so lange fortgeführt, bis der Zähler an Adresse 103/$67 auf 0 heruntergezählt ist. Während der Berechnung verweist der Hilfszeiger an Adresse 113/$71 (Low-Byte) und 114/$72 (High-Byte) jeweils auf den momentan zu verarbeitenden Koeffizienten.

Laufzeitverhalten[Bearbeiten | Quelltext bearbeiten]

POLY führt für jeden Koeffizienten eine Multiplikation und eine Addition durch. Die Laufzeit von POLY ist dadurch ungefähr proportional zum Grad des Polynoms, wobei der Proportionalitätsfaktor hauptsächlich durch die Laufzeiten der ROM-Routinen FMULT und FADD bestimmt ist. Da diese Routinen vor der eigentlichen Berechnung auf einen Faktor bzw. einen Summanden von 0 prüfen, stellt die Auswertung eines Polynoms an der Stelle FAC=0 einen Sonderfall dar, der sich durch eine besonders kurze Laufzeit — typischerweise nur ein Fünftel bis ein Zehntel der ansonsten benötigten Rechenzeit — auszeichnet.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Quellen[Bearbeiten | Quelltext bearbeiten]