POLYX

Aus C64-Wiki
Zur Navigation springenZur Suche springen

Anmerkung: Dieser Artikel beschreibt die POLYX-Routine zur Auswertung von Polynomen mit ungeraden Exponenten im BASIC-ROM.

Name: POLYX
Beschreibung: Polynomauswertung mit ungeraden Koeffizienten für Fließkommaregister FAC
Einsprungpunkt: $E043 / 57411
Übergebene Argumente:
Akkumulator: Adresse der Polynomkoeffizienten (Low-Byte)
Y-Register: Adresse der Polynomkoeffizienten (High-Byte)
Rückgabe-Werte:


POLYX[1] — manchmal auch als POLY2[2] bezeichnet — wertet ein Polynom mit ungeraden Exponenten 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. POLYX erwartet an dieser Adresse zunächst die um 1 verminderte Anzahl der Koeffizienten (1 Byte). Da das Polynom nur ungerade Exponenten aufweist, entspricht ein hier gespeicherter Wert von n einem Polynom 2n+1. Grades, ein Nullbyte wird als Polynom 513. Grades interpretiert. Auf dieses einleitende Byte folgen 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 Faktor, die im letzten Schritt der Berechnung mit x1 multipliziert 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 POLYX 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 die Fließkommaregister FAC#3 und FAC#4 an den Adressen 87/$57 bis 96/$60.

POLYX wird von den ROM-Routinen LOG, COS, SIN und ATN aufgerufen.

Algorithmus

POLYX basiert auf der ROM-Routine POLY.

  1. Zunächst überträgt POLYX den Inhalt von FAC in das Fließkommaregister FAC#3, da FAC für einen abschließenden Schritt am Ende der Berechnung gebraucht wird.
  2. Anschließend multipliziert POLYX die in FAC gespeicherte Zahl mit sich selbst und ruft mit dem so erhaltenen Wert von x2 als Argument die ROM-Routine POLY auf. Diese Routine berechnet nun wiederum — basierend auf der Tabelle der Koffizienten
    a2n+1, a2n-1, ..., a3, a1 — den Term a2n+1(x2)n + a2n-1(x2)n-1 + ... a5(x2)2 + a3(x2) + a1 = a2n+1x2n + a2n-1x2n-2 + ... a5x4 + a3x2 + a1.
  3. Im letzten Schritt wird das so berechnete Zwischenergebnis noch mit dem eingangs in FAC#3 übertragenen Wert von x multipliziert, so dass sich als Endergebnis der Wert von
    a2n+1x2n+1 + a2n-1x2n-1 + ... a5x5 + a3x3 + a1x ergibt.

Laufzeitverhalten

Die Laufzeit von POLYX wird im wesentlichen durch die innerhalb der Routine POLY durchgeführten Rechenoperationen bestimmt, ist also ungefähr proportional zum Grad des Polynoms. Hierzu ist dann noch die Rechenzeit für zwei Aufrufe der Multiplikationsroutine FMULT hinzuzurechnen (für das vorbereitende Quadrieren von x und das abschließende Multiplizieren des Resultats von POLY mit x). Da die von POLYX und POLY aufgerufenenen Routinen FMULT und FADD 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

Quellen