Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


36. Arithmetik



Arithmetik für Polynome

Nehmen wir an, daß wir ein Programm erstellen wollen, das zwei Polynome addiert; wir möchten, daß es Berechnungen der Art

(1 + 2x - 3x3) + (2 - x) = 3 + x - 3x3

ausführt. Allgemein gesagt, nehmen wir an, daß unser Programm in der Lage sein soll, r(x) = p(x) + q(x) zu berechnen, wobei p und q Polynome mit N Koeffizienten seien. Bei einer Darstellung mit Hilfe eines Feldes läßt sich das sehr leicht realisieren. Wir stellen das Polynom p(x) = p0 + p1x + ... + pN-1xN-1 durch das Feld p[0...N - 1] dar, mit p[j] == pj usw. Die Addition ist dann weiter nichts als das einzeilige Programm

    for i:=0 to N-1 do r[i]:=p[i]+q[i];

Wie gewöhnlich in Pascal (siehe Kapitel 3) müssen wir im voraus entscheiden, wie groß N werden kann, da die Größen der Felder p, q und r auf den vermuteten maximalen Wert gesetzt werden müssen.

Das obige Programm zeigt, daß die Addition sehr einfach ist, nachdem für Polynome die Feld-Darstellung gewählt worden ist; andere Rechenarten lassen sich ebenfalls leicht programmieren. Zum Beispiel ist der folgende Programmabschnitt eine sehr einfache Implementation der Multiplikation von Polynomen:

    for i:=0 to 2*(N-1) do r[i]:=0;
    for i:=0 to N-1 do
      for j:=0 to N-1 do
        r[i+j]:=r[i+j]+p[i]*q[j];

Bei der Deklaration von r müssen doppelt so viele Koeffizienten für das Produkt berücksichtigt werden. Jeder der N Koeffizienten von p wird mit jedem der N Koeffizienten von q multipliziert, so daß die Laufzeit dieses Algorithmus natürlich quadratisch bezüglich der Anzahl der Koeffizienten ist.

Wie wir in Kapitel 3 gesehen haben, besteht ein Vorteil der Darstellung eines Polynoms durch ein Feld, welches seine Koeffizienten enthält, darin, daß es einfach ist, auf jeden Koeffizienten direkt Bezug zu nehmen; ein Nachteil ist, daß möglicherweise für mehr Zahlen als nötig Platz reserviert werden muß. Zum Beispiel könnte das obige Programm nicht sinnvoll angewandt werden, um die Multiplikation

(1 + x10000)(1 + 2x10000) = 1 + 3x10000 + 2x20000

auszuführen, obwohl die Eingabedaten nur vier Koeffizienten und die Ausgabedaten sogar nur drei umfassen.

Eine andere Möglichkeit wäre, Polynome unter Verwendung verketteter Listen darzustellen und sie wie folgt zu addieren:

    function add(p,q: link): link;
      var t: link;
      begin
      t:=z;
      repeat
        new(t^.next); t:=t^.next;
        t^.c:=p^.c+q^.c;
        p:=p^.next; q:=q^.next
      until (p=z) and (q=z);
      t^.next:=z; add:=z^.next
      end;

Die Eingabe-Polynome werden mit Hilfe verketteter Listen mit einem Listenelement pro Koeffizient dargestellt; das Ausgabe-Polynom wird mittels der Funktion add erzeugt. Die Operationen mit Verkettungen weisen große Ähnlichkeiten mit Programmen auf, die wir in den Kapiteln 3, 8, 14, 29 und an anderen Stellen in diesem Buch betrachtet haben.

In der angegebenen Form ist das obige Programm keine echte Verbesserung gegenüber der Feld-Darstellung, abgesehen davon, daß es den Mangel an dynamischen Feldern in Pascal geschickt ausgleicht (der Preis dafür ist der Platz für eine Verkettung pro Koeffizient). Wie jedoch das obige Beispiel vermuten läßt, können wir die Tatsache ausnutzen, daß möglicherweise viele der Koeffizienten null sind. Wir können erreichen, daß Listenknoten nur die von null verschiedenen Glieder des Polynoms darstellen, indem wir den Grad des dargestellten Gliedes mit in den Listenknoten aufnehmen, so daß jeder Listenknoten die Werte von c und j enthält, um cxj darzustellen. Es ist dann zweckmäßig, die Funktion der Erzeugung eines Knotens und seiner Hinzufügung zu einer Liste herauszulösen:

    type link = ^node;
         node = record c: real; j: integer; next: link end;
    function listadd(t: link; c: real; j: integer): link;
      begin
      new(t^.next); t:=t^.next;
      t^.c:=c; t^.j:=j;
      listadd:=t;
      end;

Die Funktion listadd erzeugt einen neuen Knoten, weist ihm die angegebenen Felder zu und verkettet ihn nach dem Knoten t mit einer Liste. Um eine systematische Verarbeitung der Polynome zu ermöglichen, können die Listenknoten entsprechend der wachsenden Reihenfolge des Grades des dargestellten Gliedes angeordnet werden.

Nunmehr wird die Funktion add interessanter, da sie eine Addition nur für Glieder auszuführen hat, deren Grade übereinstimmen, und danach gewährleisten muß, daß kein Glied mit einem Koeffizienten 0 ausgegeben wird:

    function add(p,q: link): link;
      begin
      t:=z; z^.j:=N+1;
      repeat
        if (p^.j=q^.j) and (p^.c+q^.c<>0.0) then
          begin
          t:=listadd(t,p^.c+q^.c,p^.j);
          p:=p^.next; q:=q^.next
          end
        else if p^.j<q^.j then
          begin t:=listadd(t,p^.c,p^.j); p:=p^.next end
        else if q^.j<p^.j then
          begin t:=listadd(t,q^.c,q^.j); q:=q^.next end;
      until (p=z) and (q=z);
      t^.next:=z; add:=z^.next
      end;

Diese Verbesserungen sind für die Verarbeitung von »lichten« Polynomen, bei denen viele Koeffizienten den Wert null haben, lohnenswert, da sie bedeuten, daß der Platz und die Zeit, die für die Verarbeitung der Polynome benötigt werden, proportional zur Anzahl der Koeffizienten und nicht zum Grad des Polynoms sind. Ähnliche Einsparungen sind bei anderen Operationen mit Polynomen möglich, zum Beispiel bei der Multiplikation, doch es ist Vorsicht geboten, da die Polynome möglicherweise wesentlich weniger licht sind, nachdem eine Reihe derartiger Operationen ausgeführt worden ist. Die Darstellung mittels Feld ist besser geeignet, wenn nur wenige Glieder vorhanden sind, deren Koeffizienten den Wert null haben, oder wenn der Grad nicht hoch ist. Zur Vereinfachung nehmen wir bei der nachfolgenden Beschreibung weiterer Algorithmen für Polynome an, daß diese Darstellung benutzt wird.

Ein Polynom kann nicht nur eine, sondern mehrere Variablen enthalten. Zum Beispiel könnte es erforderlich sein, Polynome der Art

1 + wx2 + y6z + w25x50y99z38 + x1000z1000

zu verarbeiten. In solchen Fällen ist die Darstellung mittels verketteter Listen auf jeden Fall vorzuziehen; die Alternative (mehrdimensionale Felder) würde zu viel Platz beanspruchen. Es ist nicht schwierig, das obige Programm listadd (zum Beispiel) so zu erweitern, daß solche Polynome verarbeitet werden können.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]