3.7 Einen Algorithmus optimieren
Ein bestimmtes mathematisches Problem kann häufig spontan mit einem naiven Algorithmus gelöst werden. Genauere Analysen der spontanen Lösung zeigen mitunter Lösungswege auf, die weniger Rechenschritte verlangen. Am Beispiel des Potenzierens und der Auswertung eines Polynoms soll gezeigt werden, wie mathematische Algorithmen optimiert werden können.
3.7.1 Binäre Exponentiation
Für das Potenzieren gilt die Rechenvorschrift:
Ein naiver Algorithmus (Zeilen 04 bis 10, Listing 3.17) multipliziert die Basis a (n – 1)-mal mit sich selbst.
Man kann aber einzelne Multiplikationen zusammenfassen, wie Tabelle 3.5 für 28 zeigt.
|
Schritte i |
Multiplikationen |
Anzahl der Multiplikationen |
Wert |
|---|---|---|---|
|
1 |
2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 |
7 |
256 |
|
2 |
4 ⋅ 4 ⋅ 4 ⋅ 4 |
3 |
256 |
|
3 |
16 ⋅ 16 |
1 |
256 |
Tabelle 3.5 Optimierung des Potenzierens für geraden Exponenten
Aus jeweils zwei nebeneinanderstehenden Zahlen wird so lange das Produkt gebildet, bis nur zwei Faktoren übrigbleiben. Es sind für n = 8 nur drei Rechenschritte erforderlich. Wenn der Exponent ungerade ist, muss noch eine zusätzliche Multiplikation mit der Basis durchgeführt werden. Allgemein gilt: Die Anzahl der Rechenschritte ist proportional zu log2(n). Diesen Algorithmus bezeichnet man als binäre Exponentiation.
Listing 3.17 zeigt die Implementierung des naiven und optimierten Algorithmus.
01 #17_potenz.py
02 from math import log2
03 #einfache Lösung, Basis a, Exponent n
04 def pow1(a,n):
05 p=a
06 i=0 #zum zählen
07 for _ in range(n-1):
08 p=p*a
09 i=i+1 #proportional n
10 return p,i
11 #optimierte Lösung
12 def pow2(a,n):
13 p=1
14 i=0 #zum zählen
15 while n > 0:
16 if n%2==1: #Exponent ungerade
17 p=p*a
18 a=a*a #Basis quadrieren
19 n=n//2 #Exponent halbieren
20 i=i+1 #proportional log2(n)
21 return p,i
22 #Hauptprogramm
23 a=2
24 n=50 #n > 0
25 print("Exponent:",n)
26 print(pow1(a,n))
27 print(pow2(a,n))
28 print("log2(%d) = %3.3f" %(n,log2(n)))
Listing 3.17 Zwei Algorithmen für das Potenzieren
Ausgabe
Exponent: 50
(1125899906842624, 49)
(1125899906842624, 6)
log2(50) = 5.644
Analyse
In den Zeilen von 04 bis 10 berechnet die Funktion pow1() mit dem naiven Algorithmus, und in den Zeilen 12 bis 21 berechnet die Funktion pow2() mit dem optimierten Algorithmus den Potenzwert von an.
In den Zeilen 09 und 20 hat die Hilfsvariable i die Aufgabe, die Schleifendurchläufe zu zählen.
In Zeile 07 legt das Argument n-1 in der range-Funktion die Anzahl der Multiplikationen fest.
In Zeile 08 wird die Basis a (n-1)-mal mit sich selbst multipliziert.
Zurückgegeben werden der Potenzwert p und die Anzahl der Schleifendurchläufe i als Tupel (Zeile 10).
Die while-Schleife (15 bis 20) wird so oft ausgeführt, wie n>0 ist. In Zeile 19 wird nach jedem Rechenschritt mit der Ganzzahldivision n=n//2 die Anzahl der Schleifendurchläufe halbiert. Der Algorithmus der binären Exponentiation kann mit Tabelle 3.6 veranschaulicht werden:
|
n |
n%2 |
n//2 |
|---|---|---|
|
10 |
0 |
5 |
|
5 |
1 |
2 |
|
2 |
0 |
1 |
|
1 |
1 |
0 |
Tabelle 3.6 Veranschaulichung der binären Exponentiation
Die fortlaufende Ganzzahldivision (Zeile 19) erzeugt mit n=n//2 während der Schleifendurchläufe immer ungerade Zahlen, sodass p=p*a in Zeile 17 mindestens einmal berechnet wird und der Wert von p in Zeile 21 zurückgegeben werden kann.
Mit dem Profiler von Spyder können Sie die Laufzeiten von pow1() und pow2() untersuchen: Geben Sie für den Exponenten in Zeile 24 den Wert 1000 ein, und klicken Sie auf Run • Run profiler. Das Profiler-Fenster zeigt die Laufzeiten für die Funktionen pow1() und pow2() an. Sie werden feststellen, dass der optimierte Algorithmus wesentlich (etwa 20-mal) schneller ausgeführt wird.
3.7.2 Das Horner-Schema
Das Polynom
soll an der Stelle x = z ausgewertet werden. Zunächst untersuchen wir den notwendigen Aufwand für die elementaren Rechenschritte Multiplikation und Addition:
Es werden n2 / 2 + n / 2 Multiplikationen und n Additionen benötigt. Der Aufwand beträgt also
Wenn man das Polynom umformt
erhält man die Berechnungsvorschrift für das Horner-Schema. Es werden nur n Multiplikationen und n Additionen benötigt. Der Aufwand beträgt also nur
Der Funktionswert p(x) eines Polynoms kann mit dem Algorithmus
p=an
für i von n-1 bis 0
p=p⋅x + ai
berechnet werden. Tabelle 3.7 stellt den Algorithmus als rechteckiges Schema dar.
|
an-1 |
... |
a1 |
a0 |
||
|---|---|---|---|---|---|
|
x⋅bn-1 |
... |
x⋅b1 |
x⋅b0 |
||
|
x |
bn-1 |
bn-2 |
... |
b0 |
p |
Tabelle 3.7 Horner-Schema
Wenn Sie die Werte der Koeffizienten eines Polynoms in der ersten Zeile einer solchen Tabelle einsetzen, können Sie Polynome ohne großen Aufwand an der Stelle x = z auswerten.
Am Beispiel des Polynoms
soll das Verfahren des Horner-Schemas, bevor es programmiert wird, manuell für die Stelle x = 2 ausgewertet werden (Tabelle 3.8).
|
5 |
4 |
3 |
2 |
1 |
2 |
|
|---|---|---|---|---|---|---|
|
10 |
28 |
62 |
128 |
258 |
||
|
x = 2 |
5 |
14 |
31 |
64 |
129 |
260 |
Tabelle 3.8 Anwendungsbeispiel für Horner-Schema
In der ersten Zeile der Tabelle 3.8 stehen alle Koeffizienten des Polynoms, geordnet in absteigender Reihenfolge der Potenzen von x. In der dritten Zeile der ersten Spalte steht der Wert x = z, an der das Polynom ausgewertet werden soll. Der erste Koeffizient a5 wird aus der ersten Zeile in die dritte Zeile der zweiten Spalte übertragen. Er wird mit der Auswertungsstelle (hier 2) multipliziert und in die zweite Zeile der dritten Spalte rechts davon eingesetzt. Aus dem Koeffizienten a4 und dem Produkt z ⋅ a5 wird die Summe gebildet. Sie wird in die dritte Zeile der dritten Spalte eingetragen. Diese Berechnungen werden so lange wiederholt, bis alle Koeffizienten erfasst worden sind. Das Ergebnis steht in der letzten Spalte der dritten Zeile. Die Einträge der Spalten werden addiert und in die dritte Zeile eingetragen. Diese Summen werden danach mit dem Wert der Auswertungsstelle (hier 2) multipliziert und in die zweite Zeile der rechts davon liegenden nächsten Spalte eingetragen.
Listing 3.18 berechnet den Funktionswert des obigen Polynoms mit dem naiven Algorithmus und dem Horner-Schema. In Zeile 17 können Sie eine andere Auswertungsstelle und in Zeile 18 die Koeffizienten eines anderen Polynoms eintragen.
01 #18_horner_schema.py
02 #naive Methode
03 def polynom(a,x):
04 n=len(a)
05 p=a[0]
06 for i in range(1,n):
07 p = p + a[i]*x**i
08 return p
09 #Horner-Schema
10 def horner(a,x):
11 n=len(a)-1
12 p=a[n]
13 for i in range(n-1,-1,-1):
14 p = x*p + a[i]
15 return p
16 #Hauptprogramm
17 z=2
18 a=[2,1,2,3,4,5]
19 print("Wert des Polynoms an der Stelle",z)
20 print(polynom(a,z))
21 print(horner(a,z))
Listing 3.18 Horner-Schema
Ausgabe
Wert des Polynoms an der Stelle 2
260
260
Analyse
In Zeile 07 berechnet der Summenalgorithmus den Wert des Polynoms an der Stelle x. Es werden die Produkte a[i]*x**i aus den Koeffizienten und den Potenzen so lange aufsummiert, bis alle Koeffizienten a[i] erfasst worden sind. Ob die theoretische Voraussage, dass n2 / 2 + n / 2 Multiplikationen verwendet werden, zutrifft, ist allerdings anzuzweifeln. Denn die Potenzen von x werden mit hoher Wahrscheinlichkeit mit dem optimierten Algorithmus der binären Exponentiation berechnet.
Der Algorithmus des Horner-Schemas (Zeilen 12 bis 14) ist erstaunlich einfach. In Zeile 14 werden die Koeffizienten a[i] und die Produkte p*x einfach aufaddiert. In Zeile 11 wird die Anzahl der Koeffizienten um 1 vermindert, weil für die Auswertung des Polynoms nur die Koeffizienten an-1 bis a0 benötigt werden. Der Koeffizient an wird in Zeile 12 der Variablen p=a[n] zugewiesen.
In Zeile 13 nimmt die Zählvariable i die Werte 4, 3, 2, 1 und 0 an. Die for-Schleife zählt also rückwärts. Dieses Konstrukt wurde gewählt, damit die Werte der Zählvariablen mit den Indices der Liste a aus Zeile 18 übereinstimmen. Wenn Sie unter der Zeile 13 die Anweisung print(i,p) einfügen, gibt das Programm die Werte der dritten Zeile der Tabelle 3.8 aus.
In Zeile 17 können Sie andere Polynom-Koeffizienten einfügen. Sie müssen geordnet in ansteigender Reihenfolge der Potenzen von x in die Liste a eingetragen werden.