Robert Sedgewick: Algorithmen

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


36. Arithmetik



Multiplikation von Polynomen

Unser erster komplizierter arithmetischer Algorithmus ist für das Problem der Multiplikation von Polynomen bestimmt: Gegeben seien zwei Polynome p(x) und q(x), zu berechnen ist ihr Produkt p(x)q(x). Wie wir zu Beginn dieses Kapitels angemerkt haben, können Polynome vom Grad N - 1 aus N Summanden bestehen (einschließlich der Konstanten), und ihr Produkt ist vom Grad 2N - 2 und besteht aus 2N - 1 Summanden. Zum Beispiel ist

(1 + x + 3x2 - 4x3)(1 + 2x - 5x2 - 3x3) = (1 + 3x - 6x3 - 26x4 + 11x5 + 12x6).

Der primitive Algorithmus für dieses Problem, der am Anfang dieses Kapitels angegeben wurde, erfordert N2 Multiplikationen für Polynome vom Grad -1: Jeder der N Summanden von p(x) wird mit jedem der N Summanden von q(x) multipliziert.

Um diesen einfachen Algorithmus zu verbessern, wenden wir das Prinzip «Teile und Herrsche« an. Ein Weg, um ein Polynom in zwei zu zerlegen, besteht darin, die Menge der Koeffizienten in zwei Hälften zu teilen; wenn ein Polynom vom Grad N - 1 (mit N Koeffizienten) gegeben ist, können wir es in zwei Polynome mit N/2 Koeffizienten aufspalten (wir setzen N als gerade voraus): Wir verwenden die N/2 Koeffizienten niedrigerer Ordnung für ein Polynom und die N/2 Koeffizienten höherer Ordnung für das andere. Für p(x) = p0 + p1x + ... + pN-1xN-1 definieren wir

pl(x) = p0 + p1x + ... + pN/2-1xN/2-1,
ph(x) = pN/2 + pN/2+1x + ... + pN-1xN/2-1.

Dann gilt, wenn wir q(x) in der gleichen Weise aufspalten:

p(x) = pl(x) + xN/2ph(x),
q(x) = ql(x) + xN/2qh(x).

Ausgedrückt über die kleineren Polynome ist das Produkt nunmehr gegeben durch:

p(x)q(x) = pl(x)ql(x) + (pl(x)qh(x) + ql(x)ph(x))xN/2 + ph(x)qh(x)xN.

(Die gleiche Aufspaltung verwendeten wir in Kapitel 35, um einen Überlauf zu vermeiden.)

Die entscheidende Tatsache bei dieser Vorgehensweise ist nun, daß nur drei Multiplikationen erforderlich sind, um diese Produkte zu berechnen (nicht vier, wie es aufgrund obiger Formel den Anschein hat), denn wenn wir rl(x) = pl(x)ql(x), rh(x) = ph(x)qh(x) und rm(x) = (pl(x) + ph(x))(ql(x) + qh(x)) berechnen, können wir das Produkt p(x)q(x) erhalten, indem wir

p(x)q(x) = rl(x) + (rm(x) - rl(x) - rh(x))xN/2 + rh(x)xN

berechnen. Die erzielbaren Einsparungen werden durch dieses kleine Beispiel vielleicht noch nicht deutlich. Das Verfahren beruht auf der Tatsache, daß die Addition von Polynomen einen linearen Algorithmus erfordert, die einfache Multiplikation von Polynomen dagegen quadratisch ist, so daß es sich lohnt, ein paar (einfache) Additionen auszuführen, um eine (schwierige) Multiplikation einzusparen. Weiter unten betrachten wir die mit dieser Methode erzielbaren Einsparungen ausführlicher.

Für das oben angegebene Beispiel mit p(x) = 1 + x + 3x2 - 4x3 und q(x) = 1 + 2x - 5x2 - 3x3 erhalten wir

rl(x) = (1 + x)(1 + 2x) = 1 + 3x + 2x2,
rh(x) = (3 - 4x)(-5 - 3x) = -15 + 11x + 12x2,
rm(x) = (4 - 3x)(-4 - x) = -16 + 8x + 3x2.

Somit ist rm(x) - rl(x) - rh(x) = -2 - 6x - 11x2, und das Produkt wird gemäß der obigen Formel als die Summe von drei Gliedern berechnet:

p(x)q(x) = (1 + 3x + 2x2) + (-2 - 6x - 11x2)x2 + (-15 + 11x + 12x2)x4
= 1 + 3x - 6x3 - 26x4 + 11x5 + 12x6.

Durch diese Herangehensweise nach der Methode »Teile und Herrsche« wird ein Problem der Multiplikation von Polynomen der Größe N durch das Lösen von drei Teilproblemen der Größe N/2 gelöst, wobei einige Additionen von Polynomen angewandt werden, um die Teilprobleme zu formulieren und ihre Lösungen zu kombinieren. (Falls N = 1 gilt, ist das Produkt einfach gleich dem Skalarprodukt der beiden konstanten Koeffizienten.) Somit läßt sich diese Prozedur leicht in Form eines rekursiven Programms beschreiben:

    function mult(p,q: array[0..N-1] of real;
                         N: integer) : array [0..2*N-2] of real;
    var pl,ql,ph,qh,t1,t2: array [0..(N  div 2)-1] of real;
        rl,rm,rh: array[0..N-1] of real;
        i,N2: integer;
    begin
    if N=1 then mult[0]:=p[0]*q[0]
    else
      begin
      N2:=N div 2;
      for i:=0 to N2-1 do
        begin pl[i]:=p[i]; ql[i]:=q[i] end;
      for i:=N2 to N-1 do
        begin ph[i-N2]:=p[i]; qh[i-N2]:=q[i] end;
      for i:=0 to N2-1 do t1[i]:=pl[i]+ph[i];
      for i:=0 to N2-1 do t2[i]:=ql[i]+qh[i];
      rm:=mult(t1,t2,N2);
      rl:=mult(pl,ql,N2);
      rh:=mult(ph,qh,N2);
      for i:=0 to N-2 do mult[i]:=rl[i]
      mult[N-1]:=0;
      for i:=0 to N-2 do mult[N+i]:=rh[i]
      for i:=0 to N-2 do
        mult[N2+i]:=mult[N2+i]+rm[i]-(rl[i]+rh[i]);
      end;
    end.

Obwohl das obige Programm eine komprimierte Beschreibung dieses Verfahrens darstellt, ist es leider kein zulässiges Pascal-Programm, da Funktionen nicht dynamisch Felder deklarieren können. Dieses Problem kann in Pascal gelöst werden, indem die Polynome als verkettete Listen dargestellt werden; wir überlassen dies dem Leser als Übung. Für das obige Programm wird vorausgesetzt, daß N eine Zweierpotenz ist, obwohl die Details für allgemeines N leicht ausgearbeitet werden können. Die Hauptschwierigkeiten sind, daß gewährleistet werden muß, daß die Rekursion ordnungsgemäß abbricht, und daß die Polynome richtig zerlegt werden, wenn N ungerade ist.

Warum ist diese auf dem Prinzip »Teile und Herrsche« beruhende Methode eine Verbesserung? Um die Antwort zu finden, müssen wir eine grundlegende rekurrente Beziehung lösen, die nur unwesentlich komplizierter ist als die in Kapitel 6 betrachteten.

Eigenschaft 36.1 Zwei Polynome vom Grad N können unter Verwendung von ungefähr N1,58 Multiplikationen multipliziert werden.

Aus dem rekursiven Programm ist ersichtlich, daß die Anzahl der ganzzahligen Multiplikationen, die für die Multiplikation von zwei Polynomen der Größe N erforderlich sind, gleich der Anzahl der Multiplikationen ist, die ausgeführt werden müssen, um drei Paare von Polynomen der Größe N/2 zu multiplizieren. (Wir bemerken, daß zum Beispiel keine Multiplikationen benötigt werden, um rh(x)xN zu berechnen, sondern nur Verschiebungen von Daten.) Falls MN die Anzahl der Multiplikationen bezeichnet, die erforderlich sind, um zwei Polynome der Größe N zu multiplizieren, so erhalten wir

MN = 3MN/2, für N>=2, mit M1 = 1.

Somit ist M(2) = 3, M(4) = 9, M(8) = 27 usw. Wie in Kapitel 6 können wir, wenn wir N = 2n wählen, die rekurrente Beziehung wiederholt auf sich selbst anwenden, um die Lösung zu finden:

M(2n) = 3M(2n-1) = 32M(2n-2) = 33M(2n-3) = ... = 3nM(1) = 3n.
M2n = 3M2n-1
= 32M2n-3
.
.
= 3nM20 + n
= 3n.

Falls N = 2n ist, so ist 3n = 2(lg 3)n = 2n lg 3 = Nlg 3. Obwohl diese Lösung nur für N = 2n exakt ist, zeigt es sich, daß allgemein gilt

MN rund Nlg 3 rund N1,58,

was im Vergleich zu N2 bei der primitiven Methode eine erhebliche Einsparung ist. w.z.b.w.

Wir bemerken, daß, wenn wir bei der einfachen Methode »Teile und Herrsche« alle vier Multiplikationen benutzt hätten, die Leistungsfähigkeit die gleiche wäre wie bei der elementaren Methode, denn die rekurrente Beziehung würde M(N) = 4M(N/2) lauten, mit der Lösung M(2n) = 4n = N2.

Dieses Verfahren ist eine schöne Veranschaulichung der Methode »Teile und Herrsche«, wird jedoch in der Praxis selten angewandt, da eine weit bessere Methode vom Typ »Teile und Herrsche« bekannt ist, die wir in Kapitel 41 betrachten. Diese Methode kommt mit der Zerlegung des ursprünglichen Problems in nur zwei Teilprobleme aus, mit etwas zusätzlichem Rechenaufwand. Dies führt zu unserer standardmäßigen rekurrenten Beziehung des Prinzips »Teile und Herrsche« MN = 2MN/2 + N für die Anzahl der erforderlichen Multiplikationen und ergibt die Lösung, daß MN ungefähr N lg N ist.


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