Robert Sedgewick: Algorithmen

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


36. Arithmetik



Berechnung und Interpolation von Polynomen

Untersuchen wir, wie der Wert eines gegebenen Polynoms in einem gegebenen Punkt zu berechnen ist. Um zum Beispiel

p(x) = x4 + 3x3 - 6x2 + 2x + 1

für irgendein gegebenes x zu berechnen, könnte man x4 berechnen, dann 3x3 berechnen und addieren usw. Diese Methode erfordert die wiederholte Berechnung der Potenzen von x; eine andere Variante wäre, die Potenzen von x bei ihrer Berechnung zu speichern, doch das erfordert zusätzlichen Speicherplatz.

Eine einfache Methode, bei der eine wiederholte Berechnung vermieden und kein zusätzlicher Speicherplatz benötigt wird, ist unter der Bezeichnung Horner-Schema bekannt: Indem die Operationen der Multiplikation und Addition in zweckmäßiger Weise abwechselnd ausgeführt werden, kann ein Polynom vom Grad N unter Anwendung von nur N - 1 Multiplikationen und N Additionen berechnet werden. Die Schreibweise unter Benutzung von Klammern

p(x) = x(x(x(x + 3) - 6) + 2) + 1

macht die Reihenfolge der Berechnung offensichtlich:

    y:=p[N];
    for i:=N-1 downto 0 do y:=x*y+p[i];

Wir haben bereits bei einer sehr wichtigen praktischen Anwendung eine Variante dieses Verfahrens verwendet, als wir Hash-Funktionen von langen Schlüsseln berechneten (siehe Kapitel 16).

Ein komplizierteres Problem ist die Auswertung (Berechnung) eines gegebenen Polynoms in vielen verschiedenen Punkten. Dafür sind unterschiedliche Algorithmen geeignet, je nachdem, wie viele Auswertungen auszuführen sind und ob sie gleichzeitig auszuführen sind oder nicht. Wenn eine sehr große Anzahl von Auswertungen vorgenommen werden soll, lohnt es sich eventuell, eine gewisse »vorbereitende Berechnung« auszuführen, wodurch der Aufwand der späteren Auswertungen leicht reduziert werden kann. Wir bemerken, daß das Horner-Schema ungefähr N2 Multiplikationen erfordert, um ein Polynom vom Grad N in N verschiedenen Punkten zu berechnen. Es wurden wesentlich ausgeklügeltere Verfahren entwickelt, mit denen das Problem in N (log N)2 Schritten gelöst werden kann, und in Kapitel 41 werden wir eine Methode kennenlernen, die für eine spezielle Menge von N interessierenden Punkten nur N log N Multiplikationen erfordert.

Falls das gegebene Polynom nur ein Glied besitzt, reduziert sich das Problem der Auswertung des Polynoms auf das Problem der Potenzierung: Man berechne xN. Das Horner-Schema entartet in diesem Fall zu einem trivialen Algorithmus, der N - 1 Multiplikationen erfordert. Um zu sehen, wie wir viel besser zum Ziel kommen können, betrachten wir die folgende Folge zur Auswertung von x32:

x, x2, x4, x8, x16, x32.

Jedes Glied dieser Folge ergibt sich durch Quadrieren des vorangegangenen Glieds, so daß nur fünf Multiplikationen erforderlich sind, nicht 31.

Das Verfahren des »sukzessiven Quadrierens« kann leicht auf allgemeines N verallgemeinert werden, wenn die berechneten Werte gespeichert werden. Zum Beispiel kann x55 aus den obigen Werten mit Hilfe von vier weiteren Multiplikationen berechnet werden:

x55 = x32x16x4x2x1.

Im allgemeinen kann die Binärdarstellung von N benutzt werden, um zu bestimmen, welche berechneten Werte zu verwenden sind. (Im angegebenen Beispiel werden alle Werte außer x8 verwendet, da 55 = (110111)2 gilt.) Die Berechnung der sukzessiven Quadrate und die Prüfung der Bits von N können innerhalb der gleichen Schleife erfolgen. Zur Implementation dieses Ansatzes stehen zwei Verfahren zur Verfügung, die wie das Horner-Schema nur einen »Zwischenspeicher« benutzen. Ein Algorithmus besteht im Durchsuchen der Binärdarstellung von N von links nach rechts, beginnend mit 1 im Zwischenspeicher. Bei jedem Schritt wird der Zwischenspeicher quadriert, und wenn in der Binärdarstellung von N die Ziffer 1 steht, wird er außerdem noch mit x multipliziert. Mit Hilfe dieses Verfahrens wird für N = 55 die nachfolgende Wertfolge berechnet:

1, 1, x, x2, x3, x6, x12, x13, x26, x27, x54, x55.

Ein anderer gut bekannter Algorithmus läuft ähnlich ab, durchsucht jedoch N von rechts nach links. Dieses Problem ist eine Standardübung bei der Einführung in die Programmierung. Obwohl es kaum von praktischem Interesse zu sein scheint, daß man in der Lage ist, derart große Zahlen zu berechnen, werden wir weiter unten bei unserer Betrachtung von großen ganzen Zahlen sehen, daß dieses Verfahren bei der Implementation der Verschlüsselungssysteme mit öffentlichem Schlüssel aus Kapitel 23 eine Rolle spielt.

Das »inverse« Problem zur gleichzeitigen Berechnung eines Polynoms vom Grad N in N Punkten ist das Problem der Polynom-Interpolation: Zu einer gegebenen Menge von N Punkten x1, x2, ..., xN und zugehörigen Werten y1, y2, ..., yN ist das eindeutige Polynom vom Grad N - 1 zu bestimmen, für das gilt

p(x1) = y1, p(x2) = y2, ..., p(xN) = yN.

Das Problem der Interpolation ist die Bestimmung des Polynoms, wenn eine Menge von Punkten und Werten gegeben ist. Das Problem der Auswertung ist die Bestimmung der Werte, wenn das Polynom und die Punkte gegeben sind. (Das Problem der Bestimmung der Punkte, wenn das Polynom und die Werte gegeben sind, ist die Auswertung der Wurzeln.)

Die klassische Lösung für das Problem der Interpolation wird durch die Lagrangesche Interpolationsformel gegeben, welche oft als ein Beweis dafür benutzt wird, daß ein Polynom vom Grad N - 1 durch N Punkte vollständig bestimmt ist:

Formel

Diese Formel sieht zunächst sehr kompliziert aus, ist jedoch in Wirklichkeit recht einfach. Zum Beispiel ist das Polynom vom Grad 2, für das p(1) = 3, p(2) = 7 und p(3) = 13 gilt, durch

Formel

gegeben, was sich zu

x2 + x + 1

vereinfacht.

Für alle x aus der Menge x1, x2, ..., xN ist die Formel so aufgebaut, daß p(xk) = yk für 1 <= k <= N gilt, da das Produkt stets den Wert 0 hat, außer für j = k, wo es den Wert 1 hat. Im angegebenen Beispiel haben die letzten beiden Summanden den Wert null, wenn x = 1 ist, der erste und der letzte Summand haben den Wert null, wenn x = 2 ist, und die ersten beiden Summanden haben den Wert null, wenn x = 3 ist.

Die Umwandlung eines Polynoms von der durch die Lagrange-Formel gegebenen Form in unsere standardmäßige Darstellung mit Koeffizienten ist keineswegs einfach. Es scheinen wenigstens N2 Operationen erforderlich zu sein, da die Summe N Summanden enthält, von denen jeder ein Produkt aus N Faktoren darstellt. In Wirklichkeit muß sogar geschickt vorgegangen werden, um zu einem quadratischen Algorithmus zu gelangen, da die Faktoren nicht einfach Zahlen sind, sondern Polynome vom Grad N. Andererseits ist jeder Ausdruck dem vorangegangenen sehr ähnlich. Der Leser sollte versuchen herauszufinden, wie diese Tatsache ausgenutzt werden kann, um zu einem quadratischen Algorithmus zu gelangen. Im Ergebnis erhält man eine gewisse Vorstellung davon, daß es durchaus nicht einfach ist, ein effizientes Programm zu erstellen, das die sich aus einer mathematischen Formel ergebende Auswertung ausführt.

Wie im Falle der Auswertung von Polynomen existieren raffiniertere Verfahren, die das Problem in N (log N)2 Schritten lösen können, und in Kapitel 41 lernen wir eine Methode kennen, die für eine spezielle Menge aus N interessierenden Punkten nur N log N Multiplikationen benötigt.


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