Summenwert einer Reihe - Die Gauß-Methode
Als ein einführendes Beispiel, mit welchem die Effizienzsteigerung bei der Konstruktion von Algorithmen illustriert werden soll, sei hier das Berechnen der Summe einer Reihe angeführt. Es ist wirklich simpel und doch werden wichtige Grundvoraussetzungen wie Algorithmusanalyse und Kreativität darin zum Ausdruck gebracht.
Gegeben sei: ein eindimensionales, n-komponentiges Feld im Wertebereich der reellen Zahlen...
Wobei gilt: a[i] = i
Gesucht ist: die Summe der Elemente des Feldes a[1...n]
Eine sequentielle Lösung zu dieser Problemstellung ist, alle Elemente des Feldes miteinander zu addieren, sodass man am Ende die Summe erhält:
In C-Code ausgedrückt ergibt sich in etwa Folgendes:
long summe(long a[], long n){
long s=0, i;
for(i=0; i<n; ++i)
s+=a[i];
return s;
}D.h. hierbei benötigen wir n Additionen, um die Lösung zu erhalten. Bei Millionen von Array-Elementen erscheint dies zu aufwendig. Gibt es denn keine bessere Lösung? Doch! "Entdeckt" wurde sie von Carl Friedrich Gauß (1777-1855, Mathematiker, Physiker und Astronom - bahnbrechend auf fast allen Gebieten der Mathematik). Zu dieser Entdeckung gibt es eine kleine Anekdote: Gauß war noch klein, ging zur Schule und im Mathematik-Unterricht stellte der Lehrer den Kindern die Aufgabenstellung, die Summe aller Zahlen von 1-100 zu finden. Während die anderen eifrig los rechneten, überlegte der kleine Gauß kurz, kritzelte etwas auf seine Rechentafel und hob die Hand: "Ich habe das Ergebnis!" Alle schauten ihn erschüttert an und der Lehrer, der sich gerade ein wenig Freizeit gönnen wollte, musste selbst erst einmal nachrechnen, ob das Ergebnis stimmt. Doch es war richtig.
Für uns stellt sich jetzt natürlich die Frage: wie kam das kleine Genie so schnell zu dieser Lösung?
Schauen wir uns einfach mal die folgende Grafik an:
Und was erkennen wir? Die Summe der Elemente, die genausoweit vom Ende wie auch vom Anfang entfernt sind, ist in jedem Fall gleich, vorausgesetzt die Anzahl der Elemente entspricht einer geraden Zahl. In diesem Fall muss man, um einen Algorithmus zur Lösung des Problems zu erhalten, z.B. das letzte mit dem ersten Element des Feldes addieren und dann mit der Anzahl der Elemente durch 2 dividiert multiplizieren:
In C notiert ergibt sich somit der folgende Code-Teil:
long gauss_summe1(long a[], long n){
long s = n/2 * (a[0]+a[n-1]);
return s;
}Doch was ist, wenn die Anzahl der Elemente ungerade ist? Für diesen Fall muss man sich etwas einfallen lassen, da es hier nicht zwei, sondern genau ein mittleres Element gibt, welches mit keinem anderen addiert werden kann. Im Prinzip ist es einfach: ist die Zahl ungerade, so addiert man auf das erste Element das vorletzte und addiert das letzte Element dann ganz zum Schluss seperat dazu. Es gilt also folgende Formel:
Wiederum die C-Notation dazu:
long gauss_summe2(long a[], long n){
long s = (n-1)/2 * (a[0]+a[n-2]) + a[n-1];
return s;
}Führt man beide Funktionen zusammen, so kann man eine allgemeingültige Funktion aufstellen:
long gauss_summe(long a[], long n){
long s;
if(n%2==0)
s = n/2 * (a[0]+a[n-1]);
else
s = (n-1)/2 * (a[0]+a[n-2]) + a[n-1];
return s;
}Hierbei wird zunächst mit
n%2==0 überprüft, ob es sich um eine gerade Zahl handelt. Trifft dies
zu, so findet die Berechnung anhand der ersten Funktion statt, ansonsten anhand der zweiten. Da die Arrayindizierung
in C bei 0 und nicht bei 1 beginnt, muss man natürlich auch bis n-1 und nicht bis n zählen, das Ergebnis ist
allerdings dasselbe. Für Kritiker: die explizite Zuweisung an die Integer-Variable s habe ich hier so
vorgesehen, damit die obigen Formeln zur Lösung des Problems noch einmal besonders zur Geltung kommen.
Selbstverständlich hätte ich das Ergebnis der Berechnung auch sofort mit return an die
aufrufende Funktion zurückgeben können ;o)Und was hat uns das gebracht?
Hier zunächst der Sourcecode eines Programms, das ich schnell mal als Demonstrationsbeispiel programmiert habe: [download]
Wie im Code schon angemerkt ist, soll nur mal schnell grob ein Vergleich geschaffen werden, zu einer objektiven Laufzeitberechnung ist es nicht zu gebrauchen.
Auf meinem System (Athlon XP 2400+, 786 MB RAM) ergibt sich beispielsweise folgende Ausgabe:
Anzahl der Elemente?: 1000000
Gauß-Summe: 500000500000, benoetigte Zeit: 0.010
Summe: 500000500000, benoetigte Zeit: 62.320
Die Frage nun: woher nimmt der Gauß-Algorithmus seine Geschwindigkeit?
Machen wir mal auf die Schnelle eine Analyse beider Algorithmen:
| "sequentieller" Algorithmus | Gauß-Algorithmus |
|
|
| Wie man sieht, benötigt der Algorithmus n Additionen, um ans Ziel zu gelangen. | Das Gauß-Verfahren benötigt nur eine Addition, eine Division und eine Multiplikation. |
| Fazit: Wie man erkennen kann, benötigt der Gauß-Algorithmus für n gegen unendlich immer nur 3 Grundrechenoperationen. Hingegen führt der sequentielle Algorithmus für n gegen unendlich auch gegen unendlich viele Additionen durch. Dies mag bei niedriger Elementzahl nicht großartig ins Gewicht fallen und bei sehr niedriger Elementzahl ist der sequentielle Algorithmus gar schneller wie das Gauß-Verfahren (da Additionen schneller sind als Multiplikationen und Divisionen), bei einer höheren Anzahl steigen die Rechenoperationen und damit die verbrauchte Rechenzeit aber unverhältnismäßig stark an. | |
Ich hoffe, dass ich mit diesem Einführungsbeispiel ein wenig das Verständnis für die Notwendigkeit zur Konstruktion effizienter Algorithmen und auch teilweise die Neugier in jedem wecken konnte, der sich mit dieser Thematik eingehend befassen will. Und vielleicht erkennt man nach dem Durcharbeiten dieses Beispiels etwas besser, warum auch in Zeiten von Gigahertz-Rechnern effiziente Algorithmen eine große Rolle spielen. Eine Lösung, die zwar funktioniert, aber 1000 Jahre für die Berechnung benötigt, nützt schließlich keinem etwas! Wie immer hat der Text keinen Anspruch auf Vollständigkeit/absolute Richtigkeit, weswegen Kommentare durchaus erlaubt und erwünscht sind.