Polynomring
Mathematiker nennen die Menge der Polynome zusammen mit den zwei Verknüpfungen + und * einen Ring. Das bedeutet, dass sich + und * fast genauso verhalten, wie sie es bei Zahlen tun. Das "fast" bezieht sich auf zwei Ausnahmen: Für einen Ring ist es nicht erforderlich, dass x * y = y * x immer gilt. Und für einen Ring muss die Division nicht definiert sein. Für Polynome trifft x * y = y * x sogar zu, aber die Art von Division, die für Polynome definiert ist, geht nicht immer auf.
Polynome können als Datenstruktur dargestellt werden und diese Datenstruktur ist besonders einfach. Sie hat nur eine Komponente - eine Liste mit den Koeffizienten des Polynoms vom höchsten Grad an abwärts. Als Invariante wird festgelegt, dass es mindestens einen Koeffizienten geben muss und alle Koeffizienten Zahlen sind.
(defstruct polynomial (coefficients)
(and coefficients (every? number? coefficients)))
Der Grad eines Polynoms entspricht dem größten Exponent. Beim Polynom 2 x³ - 3 x² + 5 also 3 wegen x³. Da die Liste der Koeffizienten keine Lücken hat (für das Beispiel hat die Liste die Elemente 2, -3, 0 und 5) ergibt sich der Grad aus der um Eins verminderten Länge der Liste.
(defmethod degree ((this polynomial))
t
(- (length (. this coefficients)) 1))
Der führende Koeffizient ist der Multiplikator vor dem x mit dem größten Exponent (im Beispiel also 2). Er steht am Anfang der Liste der Koeffizienten.
(defmethod leading-coefficient ((this polynomial))
t
(first (. this coefficients)))
Ein Polynom entspricht dem neutralen Element der Polynomaddition, wenn alle Koeffizienten Null sind.
(defmethod zero? ((this polynomial))
t
(every? zero? (. this coefficients)))
Zwei Polynome werden addiert, indem ihre Koeffizienten paarweise für gleiche Exponenten addiert werden. Hat ein Polynom weniger Koeffizienten als das andere, werden von der Hilfsmethode expand Nullen ergänzt. Die gegenteilige Hilfsmethode contract entfernt nach der Addition Nullen am Anfang der Koeffizientenliste.
(defmethod add ((this polynomial) (that polynomial))
t
(cond
((< (degree this) (degree that))
(add (expand this) that))
((< (degree that) (degree this))
(add this (expand that)))
(t
(contract
(new polynomial
(zip-with add (. this coefficients) (. that coefficients)))))))
(defmethod expand ((this polynomial))
t
(new polynomial (cons 0 (. this coefficients))))
(defmethod contract ((this polynomial))
t
(cond
((zero? (degree this))
this)
((zero? (leading-coefficient this))
(contract (new polynomial (rest (. this coefficients)))))
(t
this)))
Die Subtraktion erfolgt analog zur Addition, jedoch werden die Koeffizienten paarweise subtrahiert.
(defmethod sub ((this polynomial) (that polynomial))
t
(cond
((< (degree this) (degree that))
(sub (expand this) that))
((< (degree that) (degree this))
(sub this (expand that)))
(t
(contract
(new polynomial
(zip-with sub (. this coefficients) (. that coefficients)))))))
Bei der Multiplikation zweier Polynome wird jeder Summand des einen mit jedem Summanden des anderen multipliziert. Dann werden die Einzelprodukte summiert. Vor den Einzelmultiplikationen werden die beteiligten Polynome in einer anderen Form dargestellt. Das erledigt die Methode to-degree-coefficient-pairs. Sie liefert beispielsweise für das Polynom 2 x³ - 3 x² + 5 eine Liste von Paaren ((3 2) (2 -3) (1 0) (0 5)). Jedes Paar ist aus einem Grad und dem zugehörigen Koeffizient gebildet. Die Kombination "jeder Summand des einen mit jedem Summanden des anderen" wird von der Funktion cartesian-product erledigt. Die Einzelprodukte werden von der anonymen Funktion berechnet, indem die Grade addiert und die Koeffizienten multipliziert werden. Schließlich werden die Einzelprodukte von der Funktion to-polynomial summiert.
(defmethod times ((this polynomial) (that polynomial))
t
(to-polynomial
(map-with
(lambda (pair-of-pairs)
(list
(+ (degree-from-pair (first pair-of-pairs))
(degree-from-pair (second pair-of-pairs)))
(* (coefficient-from-pair (first pair-of-pairs))
(coefficient-from-pair (second pair-of-pairs)))))
(cartesian-product
(to-degree-coefficient-pairs this)
(to-degree-coefficient-pairs that)))
(+ (degree this) (degree that))))
(defmethod to-degree-coefficient-pairs ((this polynomial))
t
(zip-with
list
(reverse (range 0 (+ 1 (degree this))))
(. this coefficients)))
(setq degree-from-pair first)
(setq coefficient-from-pair second)
(defproc to-polynomial (pairs result-degree)
(let
((array (make-array (list (+ 1 result-degree))))
(result nil))
(progn
(dotimes (index (+ 1 result-degree))
(set-array-element array (list index) 0))
(dolist (pair pairs)
(set-array-element
array
(list (degree-from-pair pair))
(+ (coefficient-from-pair pair)
(get-array-element array (list (degree-from-pair pair))))))
(dotimes (index (+ 1 result-degree) (contract (new polynomial result)))
(setq result (cons (get-array-element array (list index)) result))))))
Die Division eines Polynoms durch ein anderes wird nach dem gleichen Verfahren durchgeführt, wie die schriftliche Division. Die Division ist nur möglich, wenn der Dividend keinen kleineren Grad hat, als der Divisior - anderenfalls wird eine Ausnahme ausgelöst.
"Nach dem gleichen Verfahren wie die schriftliche Division" bedeutet, dass man zuerst den führenden Summanden des Dividenden durch den führenden Summanden des Divisiors teilt. Für 2 x³ - 3 x² - 17 x + 30 / (x - 2) bedeutet das 2 x³ / x = 2 x². Dann multipliziert man diesen Quotienten mit dem Divisior, also 2 x² (x - 2) = 2 x³ - 4 x². Das Produkt zieht man vom Dividenden ab, also 2 x³ - 3 x² - 17 x + 30 - 2 x³ + 4 x² = x² - 17 x + 30.
Damit ist der erste Schritt der Division abgeschlossen und man dividiert die erhaltene Differenz durch den Divisior: x² - 17 x + 30 / (x - 2). Der Quotient der führenden Summanden ist x² / x = x. Das Produkt mit dem Divisior ist x (x - 2) = x² - 2 x. Zieht man das Produkt vom Dividenden ab, ergibt sich x² - 17 x + 30 - x² + 2 x = -15 x + 30.
Im dritten Schritt dividiert man -15 x + 30 / (x - 2). Der Quotient der führenden Summanden ist -15 und dessen Produkt mit dem Divisior -15 x + 30. Als Rest ergibt sich in diesem Schritt 0. Die Division geht auf, das ist nicht immer der Fall.
Damit steht das Ergebnis der Polynomdivision fest als 2 x² + x - 15.
(defmethod quotient ((this polynomial) (that polynomial))
(not (zero? that))
(let
((degree-difference (- (degree this) (degree that)))
(leading-quotient (/ (leading-coefficient this) (leading-coefficient that))))
(cond
((zero? this)
this)
((< degree-difference 0)
(throw (quote polynomial-remainder) this))
(t
(let
((partial-result
(to-polynomial
(list (list degree-difference leading-quotient))
degree-difference)))
(+ partial-result
(quotient
(- this (* partial-result that))
that)))))))
Die unten verlinkte Datei enthält die hier vorgestellten Methoden. Außerdem werden an Beispielen die Eigenschaften eines Rings nachgeweisen. Die Datei kann mit dem Programm Calc geöffnet werden.
Polynome können als Datenstruktur dargestellt werden und diese Datenstruktur ist besonders einfach. Sie hat nur eine Komponente - eine Liste mit den Koeffizienten des Polynoms vom höchsten Grad an abwärts. Als Invariante wird festgelegt, dass es mindestens einen Koeffizienten geben muss und alle Koeffizienten Zahlen sind.
(defstruct polynomial (coefficients)
(and coefficients (every? number? coefficients)))
Der Grad eines Polynoms entspricht dem größten Exponent. Beim Polynom 2 x³ - 3 x² + 5 also 3 wegen x³. Da die Liste der Koeffizienten keine Lücken hat (für das Beispiel hat die Liste die Elemente 2, -3, 0 und 5) ergibt sich der Grad aus der um Eins verminderten Länge der Liste.
(defmethod degree ((this polynomial))
t
(- (length (. this coefficients)) 1))
Der führende Koeffizient ist der Multiplikator vor dem x mit dem größten Exponent (im Beispiel also 2). Er steht am Anfang der Liste der Koeffizienten.
(defmethod leading-coefficient ((this polynomial))
t
(first (. this coefficients)))
Ein Polynom entspricht dem neutralen Element der Polynomaddition, wenn alle Koeffizienten Null sind.
(defmethod zero? ((this polynomial))
t
(every? zero? (. this coefficients)))
Zwei Polynome werden addiert, indem ihre Koeffizienten paarweise für gleiche Exponenten addiert werden. Hat ein Polynom weniger Koeffizienten als das andere, werden von der Hilfsmethode expand Nullen ergänzt. Die gegenteilige Hilfsmethode contract entfernt nach der Addition Nullen am Anfang der Koeffizientenliste.
(defmethod add ((this polynomial) (that polynomial))
t
(cond
((< (degree this) (degree that))
(add (expand this) that))
((< (degree that) (degree this))
(add this (expand that)))
(t
(contract
(new polynomial
(zip-with add (. this coefficients) (. that coefficients)))))))
(defmethod expand ((this polynomial))
t
(new polynomial (cons 0 (. this coefficients))))
(defmethod contract ((this polynomial))
t
(cond
((zero? (degree this))
this)
((zero? (leading-coefficient this))
(contract (new polynomial (rest (. this coefficients)))))
(t
this)))
Die Subtraktion erfolgt analog zur Addition, jedoch werden die Koeffizienten paarweise subtrahiert.
(defmethod sub ((this polynomial) (that polynomial))
t
(cond
((< (degree this) (degree that))
(sub (expand this) that))
((< (degree that) (degree this))
(sub this (expand that)))
(t
(contract
(new polynomial
(zip-with sub (. this coefficients) (. that coefficients)))))))
Bei der Multiplikation zweier Polynome wird jeder Summand des einen mit jedem Summanden des anderen multipliziert. Dann werden die Einzelprodukte summiert. Vor den Einzelmultiplikationen werden die beteiligten Polynome in einer anderen Form dargestellt. Das erledigt die Methode to-degree-coefficient-pairs. Sie liefert beispielsweise für das Polynom 2 x³ - 3 x² + 5 eine Liste von Paaren ((3 2) (2 -3) (1 0) (0 5)). Jedes Paar ist aus einem Grad und dem zugehörigen Koeffizient gebildet. Die Kombination "jeder Summand des einen mit jedem Summanden des anderen" wird von der Funktion cartesian-product erledigt. Die Einzelprodukte werden von der anonymen Funktion berechnet, indem die Grade addiert und die Koeffizienten multipliziert werden. Schließlich werden die Einzelprodukte von der Funktion to-polynomial summiert.
(defmethod times ((this polynomial) (that polynomial))
t
(to-polynomial
(map-with
(lambda (pair-of-pairs)
(list
(+ (degree-from-pair (first pair-of-pairs))
(degree-from-pair (second pair-of-pairs)))
(* (coefficient-from-pair (first pair-of-pairs))
(coefficient-from-pair (second pair-of-pairs)))))
(cartesian-product
(to-degree-coefficient-pairs this)
(to-degree-coefficient-pairs that)))
(+ (degree this) (degree that))))
(defmethod to-degree-coefficient-pairs ((this polynomial))
t
(zip-with
list
(reverse (range 0 (+ 1 (degree this))))
(. this coefficients)))
(setq degree-from-pair first)
(setq coefficient-from-pair second)
(defproc to-polynomial (pairs result-degree)
(let
((array (make-array (list (+ 1 result-degree))))
(result nil))
(progn
(dotimes (index (+ 1 result-degree))
(set-array-element array (list index) 0))
(dolist (pair pairs)
(set-array-element
array
(list (degree-from-pair pair))
(+ (coefficient-from-pair pair)
(get-array-element array (list (degree-from-pair pair))))))
(dotimes (index (+ 1 result-degree) (contract (new polynomial result)))
(setq result (cons (get-array-element array (list index)) result))))))
Die Division eines Polynoms durch ein anderes wird nach dem gleichen Verfahren durchgeführt, wie die schriftliche Division. Die Division ist nur möglich, wenn der Dividend keinen kleineren Grad hat, als der Divisior - anderenfalls wird eine Ausnahme ausgelöst.
"Nach dem gleichen Verfahren wie die schriftliche Division" bedeutet, dass man zuerst den führenden Summanden des Dividenden durch den führenden Summanden des Divisiors teilt. Für 2 x³ - 3 x² - 17 x + 30 / (x - 2) bedeutet das 2 x³ / x = 2 x². Dann multipliziert man diesen Quotienten mit dem Divisior, also 2 x² (x - 2) = 2 x³ - 4 x². Das Produkt zieht man vom Dividenden ab, also 2 x³ - 3 x² - 17 x + 30 - 2 x³ + 4 x² = x² - 17 x + 30.
Damit ist der erste Schritt der Division abgeschlossen und man dividiert die erhaltene Differenz durch den Divisior: x² - 17 x + 30 / (x - 2). Der Quotient der führenden Summanden ist x² / x = x. Das Produkt mit dem Divisior ist x (x - 2) = x² - 2 x. Zieht man das Produkt vom Dividenden ab, ergibt sich x² - 17 x + 30 - x² + 2 x = -15 x + 30.
Im dritten Schritt dividiert man -15 x + 30 / (x - 2). Der Quotient der führenden Summanden ist -15 und dessen Produkt mit dem Divisior -15 x + 30. Als Rest ergibt sich in diesem Schritt 0. Die Division geht auf, das ist nicht immer der Fall.
Damit steht das Ergebnis der Polynomdivision fest als 2 x² + x - 15.
(defmethod quotient ((this polynomial) (that polynomial))
(not (zero? that))
(let
((degree-difference (- (degree this) (degree that)))
(leading-quotient (/ (leading-coefficient this) (leading-coefficient that))))
(cond
((zero? this)
this)
((< degree-difference 0)
(throw (quote polynomial-remainder) this))
(t
(let
((partial-result
(to-polynomial
(list (list degree-difference leading-quotient))
degree-difference)))
(+ partial-result
(quotient
(- this (* partial-result that))
that)))))))
Die unten verlinkte Datei enthält die hier vorgestellten Methoden. Außerdem werden an Beispielen die Eigenschaften eines Rings nachgeweisen. Die Datei kann mit dem Programm Calc geöffnet werden.