Das Horner-Schema - Berechnung des Funktionswertes eines reellen Polynoms
Als oft auftretende mathematische und informatische Objekte eignen sich Polynome hervorragend für algorithmische Untersuchungen. In diesem Text soll neben der effizienten Berechnung des Funktionswertes eines Polynoms wieder einmal verdeutlicht werden, wie leicht es sein kann, mittels einfacher mathematischer Verfahren eine erhebliche Effizienzsteigerung bei einem Algorithmus zu erlangen, was den Leser dazu inspirieren soll, dies in Zukunft auch bei seinen eigenen Projekten zu berücksichtigen.
Gegeben sei: ein reelles Polynom n. Grades (Beispiel hier: n=5)...
Gesucht ist: der Funktionswert des Polynoms bei gegebenen a und x
Triviallösung
Die "Triviallösung" besteht darin, die Exponenten durch Multiplikation zu beseitigen und dadurch den Funktionswert zu erhalten:
Eine nähere Betrachtung zeigt, dass dabei folgende Rechenoperationen benötigt werden:
Für p5(x):
- 5+4+3+2+1 = 15 Multiplikationen
- 5 Additionen
- n Additionen
Es ist nie gut, viele Multiplikationen/Divisionen in einem Algorithmus zu enthalten. Diese gehören zwar zu den Grundrechenoperationen, sollten aber nicht mit der Addition/Subtraktion gleichgesetzt werden. Grund: alle Grundrechenoperationen können auf die Addition zurück geführt werden und der Rechner verbraucht dementsprechend mehr Ressourcen, wenn er eine Multiplikation/Division ausführen will...
(Optimale) Lösung: Das Horner-Schema
Die Lösungsidee besteht darin, durch geschickte Anwendung des Distributivgesetzes (Ausklammern) so wenig wie möglich Multiplikationen zu erhalten. Für p5(x) ließe sich diese Umformung in einen geschachtelten Klammerausdruck (nested expression) wie folgt darstellen:
Aus o.a. Abbildung ergibt sich die folgende Rekursionsgleichung:
Was bringt uns das?
Vergleichen wir doch einmal die Anzahl der Rechenoperationen beider Lösungsideen:
| Triviallösung | Horner-Schema |
Für p5(x):
|
Für p5(x):
|
Hier wird die bedeutende Effizienzsteigerung erkennbar. Anstatt einer annähernden Quadratur von n (1/2n(n+1) entspricht (n²+n)/2) bei der Triviallösung ist die Anzahl der Multiplikationen beim Horner-Schema vollkommen linear. Implementiert man diese optimale Lösung also in seinen Programmen, so ist mit einer gewaltigen Laufzeitverbesserung für sehr große Zahlen zu rechnen.
Beispiel: für n=1.000.000 würde die Triviallösung 1.000.000 Additionen und 500.000.500.000 (über 500 Milliarden) Multiplikationen benötigen. Bei einer Lösung mittels des Horner-Schemas kommt man auf 1.000.000 Additionen und ebenso viele Multiplikationen. D.h. in dem Fall, dass man über 499 Milliarden Multiplikationen eingespart hätte! Na wenn das nichts ist ;)
Last but not least
Nun hätten wir ja fast eine Implementierung in C vergessen. Aber nein, hier ist sie:
int horner(int a[], int x, int n){
int h;
if(n>0)
h=horner(a, x, n-1);
else
return a[n];
return h*x+a[n];
}Vielleicht noch eine kurze Erklärung dazu. Zum Funktionskopf: a[] ist ein Array, welches den Werten a0 bis an in obigem Text gleichkommt. x ist klar, n ist der Grad des Polynoms, d.h. der momentane Grad, da es aufgrund des rekursiven Funktionsaufrufes immer weiter dekrementiert wird. h ist der momentane Funktionswert des Polynoms, der zur Berechnung des nächsten Funktionswertes benötigt wird (siehe auch o.a. rekurrente Funktionsgleichung).
Wenn der momentane Grad des Polynoms (n) >0 ist, so wird die Funktion horner() erneut mit einem dekrementierten n aufgerufen. Ansonsten (d.h. wenn n=0 (oder n<0, was aber nicht eintreten darf, wofür der Programmierer beim Einlesen von n sorgen muss)) wird der Funktionswert des Polynoms 0. Grades (n=0) zurück gegeben. Wenn die rekursive Funktion zurückkehrt, dann wird mittels h*x+a[n] der Funktionswert des Polynoms mit aktuellem Grad zurück gegeben. Bemerkenswert ist hierbei die große Ähnlichkeit zur rekurrenten Gleichung nach dem Horner-Schema.
Sind alle rekursiven Aufrufe beendet, so wird zur aufrufenden Funktion (z.B. main()) zurück gekehrt und der dortige Rückgabewert der Funktion horner() entspricht dem Funktionswert des Polynoms.
Mit diesem Text wollte ich zeigen, wie leicht es doch manchmal sein kann, mithilfe einfacher mathematischer Regeln (hier Distributivgesetz zum Erzeugen einer nested expression) eine enorme Effizienzsteigerung zu erreichen. Ziel eines jeden Algorithmen-Programmierers sollte es sein, sich eine gewisse "Toolbox" anzueignen, in der er solche mathematischen Kenntnisse abspeichert und bei Bedarf abrufen kann. Wie oben gezeigt, kann so ganz einfach aus einer Triviallösung ein optimaler Algorithmus werden (aus N² wird N), was im Normalfall immer angestrebt werden sollte. Mithilfe effizienter Algorithmen kann man nahezu jedes Problem in annehmbarer Zeit lösen und ob man nun 1 Million oder 500 Milliarden Rechenoperationen benötigt, das ist schon ein gewaltiger Unterschied! Des weiteren sollte jeder Programmierer bestrebt sein, so wenig wie möglich Multiplikationen und Divisionen in seinen Programmen zu verwenden und immer der Strichrechnung den Vortritt zu lassen. Auch hier gilt: was bei kleinen Zahlen trivial erscheint, kann bei sehr großen Zahlen eine Menge Zeit sparen.
Ich hoffe, dass ich mit diesem Text ein paar neue Anregungen geben konnte. Bei Fragen, Lob und Kritik stehe ich natürlich wie immer zur Verfügung ;)