Die Algorithmik ist offenbar ein ganz einfaches Geschäft. So einfach, daß Donald E. Knuth es für nötig befand, darüber ein dreibändiges Standardwerk zu schreiben - ursprünglich war es auf sieben Bände ausgelegt. Da es nun schon Standardwerke und -algorithmen gibt, was liegt näher, als sie anzuwenden? Das ist legitim und erwünscht, doch Vorsicht! Oft wird übersehen, daß ein oder mehrere Aspekte einer Aufgabe nicht recht zu dem Algorithmus passen, mit dem diese Aufgabe bearbeitet werden soll.
Näher betrachtet, ist Algorithmik dann garnicht mehr so einfach, insbesondere, wenn klassische Denkbarrieren nicht überwunden werden.
Die Sammlung ist unvollständig und subjektiv. Die Beiträge hier entstanden aus der Laune heraus, einmal nicht den Lehrbuchpfaden zu folgen und wie dort wohlbekannte Rechenverfahren zu klassifizieren unnd analysieren. Hier geht's darum, ein wenig die schlechten ausgetretenen Pfade zu verlassen und sie zu vermeiden. Gelegentlich ist es sogar sinnvoll, eine neue Umgehungsstraße um ein altes Sumpfgebiet zu bauen - schön, wenn diese Straße noch dazu kürzer ist als der verfaulte Knüppeldamm durch's Hochmoor. Diese Seite soll dazu anregen, die eigene Kreativität in der Softwareentwicklung zu erwecken.
Ein paar eher unkonventionelle Betrachtungen konventioneller Gedanken habe ich hier aufbereitet:
Um es hervorzuheben: Die Unkonventionalität mancher Lösung besteht
nicht in ihrer Komplexität, sondern darin, daß sie manchmal sehr
naheliegend ist, manchmal wenig bekanntes Wissen nutzt.
Anmerkung: Die Betonung des letzen Halbsatzes läßt zwei ebenso
schlüssige, wie praktisch untermauerte Lesungen zu..
Jener Herr Alchwarizmi (auch Algorithmi, al Kwarizmi)- verballhornt aus dem Namen eines usbekischen Mathmatikers, unweit der legendär-märchenhaften Stadt Samarkand geboren - war der erste, der die Formalisierung (und damit auch auch die potentielle Mechanisierung) von Rechenverfahren beschrieb. Al Chorezmi war einer der arabischen Wissenschaftler, der das klassische griechische Erbe der Mathematik in die beginnende Neuzeit herüberrettete. Die christlichen Kreuzzüge waren glücklicherweise nicht in der Lage, das Erbe der klassischen Philiosophen und Mathematiker vollständig auszulöschen. Speziell im arabischen Kulturkreis wurden viele Schriften und Fakten bewahrt, die im Mittelmeerraum durch Kriege vernichtet wurden. Unsere heutige Algebra basiert zu einem wesentlichem Teil auf den Grundlagen, die die islamischen Mathematiker bewahrt und weiterentwickelt haben. Die Erfindung der "Null" basiert primär auf den Arbeiten der Inder und Perser - Übergangsgebiete für geistige Grenzgänger. (in der neuen Welt wurde das Konzept der "Null" von den Azteken ebenfalls erfunden, genauso wie im ägyptischen Kulturkreis ca. 300 v. Chr. - und geriet in Vergessenheit).
Warum all' die Worte? Von al Chorezmi lernte ich zweierlei:
Jede Aufgabe benötigt eine Aufschreibung. Unter all' den Aufgaben, die aufgeschrieben werden können, nehmen jene eine Sonderstellung ein, die den Eindruck erwecken, mit formalen Verfahren gelöst werden zu können. Manchmal ist die Aufschreibung der Aufgabe ein bequemes Verfahren, sich vor der Lösung der Aufgabe zu drücken, insbesondere wenn man die Aufgabe nur ansatzweise lösen kann.
Beispiel-Aufgabe: "Schreibe das Verhältnis von Umfang zu Durchmesser eines Kreises auf."
Bekanntlich ist dieses Verhältnis transzendent und seine Aufschreibung im Dezimalsystem hat unendlich viele Stellen. Es ist hier das Einfachste, die Aufgabe liegen zu lassen und die Aufgabenstellung durch den kleinen griechichen Buchstaben pi abzukürzen.
Erfreulicherweise erfordert die mathematische Praxis fast ausschließlich den Gebrauch des Buchstabens pi - und in der technischen Praxis genügen in der Regel 10 Dezimalstellen.
Dieses Konzept der Aufschreibung erlaubt, viele bequeme Abkürzungen einzuführen, wie z.B. "ack(4,4)" für eine wohlbestimmte positive ganze Zahl, die sich als als Resultat der Ackermann-Funktion ergibt, obwohl sämtliche Betriebsmitel des Universums nicht ausreichen, um diese Zahl aufzuschreiben. Denkbar ja - oder eher abkürzbar. Bei näherem Hinsehen entpuppen sich viele mathematische Begrifflichtkeiten als Schreibabkürzungen für Konzepte, die hypothetisch auszuführen zwar denkbar, aber praktisch nicht durchführbar sind.
Die algorithmische Praxis, die nach verwertbaren Lösungen für bestimmte Aufgabenstellungen sucht, fragt demnach nicht nur nach der prinzipiellen Durchführbarkeit, sondern nach der Bereitstellung der Lösung innerhalb eines angemessen erscheinenden Zeitraumes.
Die Division ack(4,4) / ack(4,4) = 1 liefert ein offensichtliches Ergebnis. Ein Computer, der die Funktion "ack" kent, und dem man die nachstehende Programmzeile vorlegt, wird sehr lange brauchen, um das offenkundige Ergebnis zu finden:
res = ack(4, 4) / ack(4, 4);
Es sei denn, der Autor des Compilers, mit dem diese Zeile übersetzt wird, hat einigen Aufwand getrieben, um offenkundige Doppelberechnungen zu eliminieren und Divisionen der Bauart a/a zur Konstanten 1 zusammenzufassen (Vorsicht! Wie ist 0/0 definiert?).
Das Denkbare aufzuschreiben genügt nicht - das Durchführbare zu erkennen und herauszukristallisieren, ist der für die Algorithmik notwendige Schrittt.
Das vorige Beispiel der berühmt-berüchtigten Ackermann-Funktion hat deutlich gezeigt, daß es kein schlechter Gedanke ist, eine Formel oder einen Programmabschnitt genauer zu analysieren. Die voreilige Berechnung des Funktionsaufrufes führt in den Abgrund, die Betrachtung der gesamten Formel liefert ein banal zu ermittelndes Ergebnis. Was lernen wir hieraus? Funktionsauswertungen sollten so spät wie irgend möglich berechnet werden.
Eine größere Arbeitslast gleichförmiger Art verführt dazu, diese Aufgabe einer Maschine zu delegieren. Ganz im Leibniz'schen Sinne, sich selbst von eintöniger Arbeit zu entlasten. Vor der Freude steht der Schweiß der Software-Entwicklung und Programmierung.
Diese Regel ist für die Auftraggeber und Kunden der Softwareentwickler der Antrieb, ihre Dienste zu beanspruchen. Für uns Informatiker bleibt nichts davon übrig... Waren wir für andere fleißig, geben wir unsere Lösung ab - dann dürfen wir schon für den Nächsten arbeiten. Was uns keiner nehmen kann, das ist das Wissen um die Algorithmen, die wir uns ausgedacht haben. Dieses Wissen lohnt sich zu dokumentieren.
Und eine persönliche Regel, um Arbeit zu vermeiden (To break the rules, you must know them):
Sobald ich in Lehrbüchern oder Vorlesungsausarbeitungen auf die Einführung der Rekursion stoße, stockt mir der Atem. Ich lese ängstlich die nächsten Worte: "... Die mathematische Funktion 'Fakultät' ist definiert durch...." Aaahhrgh! Stöhn! Läßt sich natürlich noch steigern: "...die Fibonaccifolge ist durch folgende Rekursionsformel definiert:..." Aufschrei! Qual! Ich habe nichts gegen die mathematischen Definitionen - sie sind vollkommen in Ordnung. Ich habe aber sehr viel gegen diese Definitionen, um in der Informatik das Prinzip der Rekursion einzuführen! Sicher, die Ergebnisse lassen sich mithilfe dieser Definitionen berechnen - aber zwischen potentielles Können und praktischer Anwendbarkeit haben die Götter die Hürde der Dummheit gesetzt. Ich will hier nicht die Verfahrensweise beschreiben, wie die diversen Zwischenschritte lehrbuchartig vollzogen werden. Ich frage mich nur, warum ein Mensch so dumm sein soll, diese Werte berechnen zu wollen.... Wenigstens häufiger als einmal...
Klassisch ist etwa dieser Ansatz:
long in fac (long int x)
{
if (x == 0L)
return(1L)
else return(x * fac(x-1L));
}
Was fällt an dieser Funktion auf? Sie ist rekursiv - sie wurde als Lehrbeispiel dafür erfunden. Und sonst? Sie ist elend schlecht. PUNKT! Eine nähere Analyse zeigt, daß bei der Berechnung der Fakultät gerade mal das Argument 13 noch zu einem gültigen Ergebnis führt. Was liegt ferner (oder näher?), die wenigen Werte zu tabellieren:
long int fac [] = {
1l, 1l, 2l, 6l, 24l,
120l,720l,5040l,40320l,
362880l,3628800l,39916800l,
479001600l, 1932053504l};
Siehe da! aus der sperrigen Rekursion mit ihrem Betriebsmitelhunger wurde ein simpler Tabellenzugriff. Im uniformen Komplexitätsmaß schnurrt die Arbeit auf die Konstante 1 zusammen. Ein nettes und billiges Ergebnis, insbesondere wenn bedacht wird, daß ausführbarer Code ebenfalls Speicher benötigt.
Die Fibonacci-Funktion benötigt ein wenig mehr Speicher...
long int fib[] = {
0l, 1l, 1l, 2l, 3l, 5l,
8l, 13l, 21l, 34l, 55l, 89l,
144l, 233l, 377l, 610l, 987l, 1597l,
2584l, 4181l, 6765l, 10946l,
17711l, 28657l, 46368l, 75025l,
121393l, 196418l, 317811l, 514229l,
832040l, 1346269l, 2178309l, 3524578l,
5702887l, 9227465l, 14930352l, 24157817l,
39088169l, 63245986l, 102334155l,
165580141l, 267914296l, 433494437l,
701408733l, 1134903170l, 1836311903l};
Übrigens: wer die Fakultät über den genannten Wert hinaus benötigt, ist entweder Statistker oder schlechter Rechner (oder Beides) - mit sehr unaufwendigen Methoden läßt sich die Gamma-Funktion (beachte den subtilen Zusammenhang zur Fakultät!) durch ein rationales Polynom annähern:
Standardalgorithmen haben den enormen Vorteil, daß man nicht mehr nachdenken muß, wenn man sie einsetzen will. Wirklich? Ich habe erlebt, wie ein (noch dazu falsch) implementierter Quicksort dazu verwendet wurde, einen Bestand von max. 8 Dateneinträgen zu sortieren. Die Programmierer dieser Routine hatten nicht im mindesten darüber nachgedacht, wie "quick" der Quicksort bei kleinen Datenmengen ist. Im Vertrauen gesagt: miserabel. Verfahren wie Quicksort entfalten ihre Wirkung erst ab Datenmengen, die deutlich oberhalb der genannten Anzahl liegen. Der Punkt, an dem von einem einfachen Verfahren wie z.B. Bubblesort abgewichen werden sollte, kann leicht berechnet werden. Warum macht's dann niemand? Heraus kommt dann solcher Stuß...
Merke: Standardalgorithmen sind gut - aber man muß schon prüfen, welchen Schaden ihre Anwendung anrichtet.
Dieser Aufsatz beschreibt Algorithmen, die die Berechnung von Zahlenkonstanten wie z.B. p auf eine große Anzahl Dezimalstellen zu ermöglichen, wobei keine Arithmetik für „lange" Zahlen verwendet wird, sondern nur Grundoperationen auf kleinen ganzen Zahlen. Die durch die Algorithmen ermittelten Ziffern werden als Ausgabe erzeugt, aber im weiteren Verlauf der Berechnung nicht mehr benutzt bzw. benötigt. Da je ein Durchlauf je eine Ziffer als Ergebnis „heraustropfen" läßt, werden diese Algorithmen auch als „Tröpfel"-Algorithmen (engl. spigot algorithms) bezeichnet. Vorteilhaft an diesen Verfahren ist ihre einfache Implementierung. Die Laufzeit wächst etwa proportional zum Quadrat der benötigten Stellenzahl.
Grundprinzip der Tröpfel-Algorithmen sind die Tatsachen:
Werden beide Tatsachen kombiniert, und liegt zudem die Möglichkeit vor, eine Konstante in der Form einer „gemischten Basis" darzustellen, dann ist ihre Berechnung durch einen Tröpfel-Algorithmus möglich:
Seit vielen Jahren werden Zahlenkonstanten mittels Reihenentwicklungen berechnet. Die bekannteste dieser Konstanten ist wohl p, die von Ludolph van Ceulen in mühsamer Arbeit auf 20 Stellen ermittelt wurde, weswegen sie im deutschen Sprachraum auch als Ludolphsche Zahl bezeichnet wird. Ihm standen noch keine so eleganten Reihenentwicklungen zur Verfügung, wie z.B. eine der hübschen Formeln von Ramanujan:
Soll eine bestimmte, vorgegebene Stellenzahl n ermittelt werden, so ist die Berechnung mit einer Stellenzahl erforderlich, die min. n+2 ist, um numerische Ungenauigkeiten nicht in die interessierenden Stellen zu verschleppen. Erfordert die Berechnung eine große Anzahl von Schritten, so sind ggf. weitere Schutzstellen nötig. Gewöhnliche Computer und Programmier-sprachen erlauben nur Berechnungen mit einer begrenzten Stellenzahl, die in der Größenordnung von 16 liegt. Sind mehr Stellen erforderlich, so müssen spezielle Algorithmen eingesetzt werden, die insbesondere im Fall der Division überproportional Rechenzeit gegenüber dem Anstieg der Stellenzahl erfordern. Die Berechnung von Zahlenkonstanten geriet damit zur Domäne der Supercomputer und führte im Fall der Konstanten p letztlich dazu, daß sie zu einem Benchmarktest degradiert wurde (Nebenbei sei bemerkt, daß die Kenntnis numerischer Konstanten auf ca. 20 Dezimalstellen zumindest für rein praktische Zwecke völlig ausreichend ist.). Störend an allen Verfahren, die mit Reihenentwicklungen arbeiten, ist der Zwang, daß alle Stellen jedes Zwischenergebnisses für das Endresultat erforderlich sind; die einzelnen Ziffern einer solchen Konstanten können damit nicht unabhängig voneinander berechnet werden.
Spigot Algorithms („Tröpfel-Algorithmen", Stewart[]) arbeiten anders als die vorhin genannten Verfahren. Ihr Grundprinzip liegt darin, eine Zahlenkonstante auf einfache Weise bzgl. einer gemischten Basis darzustellen und dann diese Darstellung in unser gewohntes Dezimalsystem umzurechnen. Jedem Informatiker ist z.B. das Dualsystem vertraut. So hat der dezimale Zahlenwert 14 im Dualsystem die Darstellung 1110. All den herkömmlichen Basen ist gemeinsam, daß die i-te Ziffer bzgl. der Aufschreibung mit dem Wert der Basiszahl bi multipliziert gedacht wird. Für die Basiszahl 10 bedeutet folglich die Dezimalzahl 134,89 :
1 × 103 + 3 × 102 + 4 × 101 + 8 × 10-1 +9 × 10-2
Für Nachkommastellen wird die Basis b mit negativen Exponenten versehen. Zahlenkonstanten wie p und e haben bzgl. des Dezimalsystems keine einfach durchschaubare und damit berechenbare Ziffernfolge. Ansatz zu den neuen, hier beschriebenen Algorithmen ist, eine Zahlenkonstante in der nachstehenden Weise zu berechnen:
Hinter dieser Aufschreibung der ersten Ziffern von p verbirgt sich das altbekannte Hornerschema. Die verwendete Dezimalbasis für die Nachkommastellen Bd ist gemäß dieser Aufschreibung:
Die Konstante p kann gemäß einer anderen Basis Bp günstiger aufgeschrieben werden.Da die nachstehende Reihenentwicklung gilt
ist Bp eine geeignete gemischte Basis zur Berechnung von p:
denn bezüglich Bp hat p die triviale Darstellung:
pp = 2,22222222.....
Da hier alle Ziffern bekannt bzw. einfach anzugeben sind, muß der „Tröpfel-Algorithmus" zur Berechnung von p lediglich die Dezimalziffernfolge ermitteln, die der gesuchten Konstanten bzgl. der Basis Bd entspricht. Der Vorteil des Algorithmus besteht darin, daß bei jedem Durchlauf eine Dezimalziffer erzeugt wird, deren Wert im folgenden Berechnungsdurchlauf nicht mehr benötigt wird. Alle Rechnungen finden in kleinen ganzen Zahlen statt, die in jedem Computer unmittelbar ohne spezielle Bibliotheken verfügbar sind.
Um p auf n Dezimalstellen zu berechnen, sind z=(10n/3) Werte im Arbeitspuffer nötig. Die nachstehende C-Funktion (nur Kernfunktion eines auf Datenträger verfügbaren Programms) setzt diesen Algorithmus in eine konkrete Programmiersprache um. Die Funktion benutzt einige Vorabberechnungen, um laufzeitgünstiger zu arbeiten, als die direkte Umsetzung des Original-Algorithmus:
/*---------------------------------------------------------------------------+
| Funktion : CalcPi |
| Aufgabe : Funktion zur Berechnung der Kreiszahl Pi |
| Parameter : res Zeiger auf Ergebnispuffer; da nur Zahlenwerte |
| 0..9 vorkommen koennen, wird aus Gruenden der |
| Speicherersparnis ein char-Array verwendet |
| n Anzahl zu berechnender Stellen |
| Ret.val. : int 1 = Erfolg, 0 = Fehler |
| Seiteneff. : - |
| Autor : Gra. Beginn: 25.11.1995 Stand: 26.11.1995 |
| Updates : - |
+---------------------------------------------------------------------------*/
int CalcPi ( /* Berechne Kreiszahl Pi */
char * res, /* Puffer fuer Ergebnis */
int n ) /* Anzahl Stellen */
/*-----------------------------------*/
{ /*###### Lokale Variablen: */
size_t i, j, k; /* Hilfszaehler */
size_t len; /* Laenge des Puffer- und Arbeits- */
/* bereichs */
long * a; /* Zeiger fuer Pufferbereich */
long * ap; /* Hilfszeiger */
long teiler; /* Puffer fuer Teiler bei Division */
long r; /* ... Divisionsrest */
long q; /* ... Divisionsergebnis */
long u; /* ... Uebertrag */
long b; /* Puffer fuer Dividend */
size_t e_idx; /* Index fuer endgueltige Stellen */
char * kp; /* Zeifer fuer Nachbaerbeitung der */
/* Uebertraege */
/******* Ablauf CalcPi ***************/
len = (size_t)((10l * n)/3l); /* Ermittle Speicherbedarf fuer Ar- */
/* beitspuffer */
a = (long*)malloc(len * sizeof(long)); /* Lege Arbeitspuffer an */
if(NULL == a) /* Bei Misserfolg: */
{ /* ... */
printf("Allokationsfehler bei" /* Melde Allokationsfehler */
" 'a' - Abbruch\n\n"); /* ... */
return(0); /* Abbruch der Berechnung */
} /* ENDE THEN (Allokationsfehler) */
/*-----------------------------------*/
e_idx = 0; /* Bisheriger Index fuer gueltige */
/* Stellen */
/* Startwerte fuer Iteration ein- */
/* tragen: */
for(i = (size_t)0; i < len; i++) /* Bearbeite alle Werte des Arbeits- */
a[i] = 20l; /* Puffers: Startwert = 20 */
/*-----------------------------------*/
for(j = (size_t)0; j < n; j++) /* Erzeuge nun n Stellen des Ergeb- */
{ /* nisses von Pi */
#if defined (TEST) /* NUR fuer Testzwecke */
if(!(j%100)) /* Kontrollausgabe alle 100 Werte, */
printf("%d ",j); /* damit der User nicht einpennt */
#endif /* ENDIF (NUR fuer Testzwecke) */
u = 0; /* Startuebertrag loeschen */
for(i=len-1, ap = &(a[len-1]); /* Arbeitspuffer stellenbezogen von */
i > 0; i--, ap--) /* 'hinten' nach 'vorne' durchgehen */
{ /* ... */
b = u + *ap; /* Arbeitswert aus Uebertrag und */
/* Arbeitspuffer bilden */
teiler = ((i << 1) + 1); /* Berechne Teiler fuer Divisions- */
/* Schritt */
q = b / teiler; /* Ermittle Divisionsergebnis */
r = b % teiler; /* ... und -Rest */
u = q * i; /* Berechne neuen Uebertrag */
*ap = 10 * r; /* Rest mit 10 multiplizieren und um-*/
/* kopieren fuer den naechsten Durch-*/
/* lauf */
} /* ENDE FOR (Arbeitspuffer durch- */
/* werkeln) */
/* Eintrag mit Index 0 benoetigt */
/* Sonderbehandlung: */
b = u + *a; /* Arbeitswert aus Uebertrag und */
/* Arbeitspuffer am Index 0 bilden */
teiler = 10l; /* Teiler ist hier 10 */
q = b / teiler; /* Ermittle Divisionsergebnis */
r = b % teiler; /* ... und -Rest */
*a = 10l * r; /* Rest mit 10 multiplizieren und um-*/
/* kopieren fuer den naechsten Durch-*/
/* lauf */
res[j] = (char)(int)q; /* Puffere Resultatziffer */
/* Nachbearbeitung fuer Uebertraege */
/* q ist noch vorlaeufige Stelle ! */
if(q < 9l) /* Falls q hoechstens 8 ist, dann */
e_idx = j-1; /* sind die bisherigen Stellen end- */
/* gueltig geworden */
else /* sonst: */
if (q == 9l) /* q = 9, Stelle ist zwar eingetra- */
continue; /* gen, aber nicht endgueltig */
else /* sonst q = 10; Korrektur der Ueber-*/
{ /* traege noetig */
kp = &(res[j-1]); /* Hilfszeiger auf letzten relevan- */
/* ten Eintrag legen */
for (k=j-1; k > e_idx; k--, kp--)/* Bearbeite rueckwaerts alle noch */
{ /* nicht endgueltigen Stellen */
(*kp)++; /* Schalte Ziffer um 1 nach oben */
if(*kp > 9) /* Bei echtem Uebertrag -> */
*kp -= 10; /* Ziffer wird zu 0 */
} /* ENDE FOR (korrigiere Ziffern) */
res[j] = 0; /* neu ermittelte Stelle wird statt */
/* zu 10 auf 0 gesetzt */
} /* ENDE ELSE (q = 10) */
} /* ENDE FOR (Berechne n Stellen) */
/*-----------------------------------*/
free(a); /* Loesche den nun unnoetig gewor- */
/* denen Arbeitspuffer */
return(1); /* Rueckkehr mit Erfolg */
} /* ENDE int CalcPi() */
Bei einer gemischten Basis, besteht im Gegensatz zur Dezimal- oder einer anderen g-adischen Darstellung die Gefahr, daß der Wert der Konstanten nicht eindeutig, sondern auf verschiedene Weisen darstellbar ist. Veranschaulichen kann man sich das an dem konstruierten dezimalen Beispiel
1 10 + 11 10 = 10 10 + 1 10 = 1 100 + 1 10 + 0 = 110
Wird der erste Faktor (=„Ziffer") größer als die Basiszahl, dann ist die Darstellung auf verschiedene Weisen möglich. In g-adischen Zahlsystemen wird dieser Gefahr vorgebeugt, indem gefordert wird, daß jede Ziffer kleiner als die Basiszahl ist. Bei gemischten Basen existiert die notwendige, aber nicht hinreichende Bedingung:
Für die später kurz angeschnittene Konstante e ist diese Bedingung hinreichend, während sie für die Berechnung von p nicht genügt. Deshalb müssen die Resultatziffern erforderlichenfalls korrigiert werden. Im Zuge des Rechnungsganges auftretende Divisionsergebnissse q, die größer als 8 sind, benötigen eine Sonderbehandlung:
| q<8: | Alle davorliegenden Ziffern sind gültig, da ein Übertrag nicht mehr auftreten kann. |
| q=9: | Die Ziffer muß als vorläufig betrachtet werden, da durch einen Übertrag aus der danach folgenden Ziffer eine Änderung auf 0 mit Weitergeben des Übertrages nötig werden könnte |
| q>9: | Addiere 1 und rechne q-10; Korrigiere alle davorliegenden Ziffern um den auftretenden Übertrag. Durch diese Maßnahme werden alle davorliegenden Resultatziffern ebenfalls gültig. |
Diese Dezimalkorrektur läßt sich als Pseudocode wie folgt wiedergeben:
Die Berechnung der Konstanten e durch einen Tröpfel-Algorithmus ist einfacher als die der Kreiszahl. Bereits 1965 wurde von xxx[] ein Verfahren angegeben, das die nachstehende Darstellung von e ausnutzt:
Wähle gemischte Basis b:
Bezüglich der Basis b gilt:
eb = 2,11111111....
Die Berechnung von e bezüglich dieser Basis erfordert keine Dezimalkorrektur, da die Zahldarstellung eindeutig ist.
Zeitmessungen sind wenig repräsentativ bei der immer weiter gesteigerten Arbeitsgeschwindigkeit der Computer. Erhellend können jedoch Relativmaße sein, wenn Rechenoperationen in Zahlen mit hoher Stellenzahl gegenüber dem Zeitbedarf eines Spigot-Algorithmus betrachtet werden.
Zahlenwerte, die sich einer Darstellung durch eine gemischte Basis entziehen, sind nicht auf die vorstehend beschriebene einfache Art berechenbar. So sind zwar für viele wichtige Funktionen der Mathematik Reihenentwicklungen bekannt, die jedoch keine Rücksicht auf die Berechenbarkeit von numerischen Konstanten mittels Spigot-Algorithmen Rücksicht nehmen.
Die ganzzahligen Werte werden mit wachsender Stellenzahl so groß, daß bei arithmetischen Operationen Überlauf eintreten kann. Die maximale Anzahl Stellen, die bei der C-konformen longint-Genauigkeit erreicht werden kann, liegt in der Größenordnung von ca. 104, was auch unter dem Gesichtspunkt des Zeitbedarfs angenehme Obergrenze für PC´s oder Workstations darstellt.
Die Laufzeit des Verfahrens wächst quadratisch mit der Anzahl n der zu ermittelnden Stellen.
Die Werte wurden mit dem Programm auf 1001 Stellen, also 1000 Nachkommastellen berechnet. Bei jeder Berechnung wurden 2 Schutzstellen mitgeführt.
Kreiszahl p:
3.14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 59230 78164 06286 20899 86280 34825 34211 70679 82148 08651 32823 06647 09384 46095 50582 23172 53594 08128 48111 74502 84102 70193 85211 05559 64462 29489 54930 38196 44288 10975 66593 34461 28475 64823 37867 83165 27120 19091 45648 56692 34603 48610 45432 66482 13393 60726 02491 41273 72458 70066 06315 58817 48815 20920 96282 92540 91715 36436 78925 90360 01133 05305 48820 46652 13841 46951 94151 16094 33057 27036 57595 91953 09218 61173 81932 61179 31051 18548 07446 23799 62749 56735 18857 52724 89122 79381 83011 94912 98336 73362 44065 66430 86021 39494 63952 24737 19070 21798 60943 70277 05392 17176 29317 67523 84674 81846 76694 05132 00056 81271 45263 56082 77857 71342 75778 96091 73637 17872 14684 40901 22495 34301 46549 58537 10507 92279 68925 89235 42019 95611 21290 21960 86403 44181 59813 62977 47713 09960 51870 72113 49999 99837 29780 49951 05973 17328 16096 31859 50244 59455 34690 83026 42522 30825 33446 85035 26193 11881 71010 00313 78387 52886 58753 32083 81420 61717 76691 47303 59825 34904 28755 46873 11595 62863 88235 37875 93751 95778 18577 80532 17122 68066 13001 92787 66111 95909 21642 01989
Eulersches e:
2.71828 18284 59045 23536 02874 71352 66249 77572 47093 69995 95749 66967 62772 40766 30353 54759 45713 82178 52516 64274 27466 39193 20030 59921 81741 35966 29043 57290 03342 95260 59563 07381 32328 62794 34907 63233 82988 07531 95251 01901 15738 34187 93070 21540 89149 93488 41675 09244 76146 06680 82264 80016 84774 11853 74234 54424 37107 53907 77449 92069 55170 27618 38606 26133 13845 83000 75204 49338 26560 29760 67371 13200 70932 87091 27443 74704 72306 96977 20931 01416 92836 81902 55151 08657 46377 21112 52389 78442 50569 53696 77078 54499 69967 94686 44549 05987 93163 68892 30098 79312 77361 78215 42499 92295 76351 48220 82698 95193 66803 31825 28869 39849 64651 05820 93923 98294 88793 32036 25094 43117 30123 81970 68416 14039 70198 37679 32068 32823 76464 80429 53118 02328 78250 98194 55815 30175 67173 61332 06981 12509 96181 88159 30416 90351 59888 85193 45807 27386 67385 89422 87922 84998 92086 80582 57492 79610 48419 84443 63463 24496 84875 60233 62482 70419 78623 20900 21609 90235 30436 99418 49146 31409 34317 38143 64054 62531 52096 18369 08887 07016 76839 64243 78140 59271 45635 49061 30310 72085 10383 75051 01157 47704 17189 86106 87396 96552 12671 54688 95703 50354
Seitdem es schnelle Numerik-Coprozessoren gibt, womöglich noch mit dem Hauptprozessor integriert, macht sich nahezu niemand mehr Gedanken um die zweckmäßige Implementierung von mathematischen Funktionen. Der Autor dieser Site hat vor vielen Jahren (1983) einmal ein Echtzeitsystem drastisch beschleunigt, indem er die gesamte Rechnerei auf ein 32-Bit-Festpunktformat umstellte. 16Bit vor, 16Bit nach dem Dualpunkt. Von Numerikprozessoren konnte ich damals nur träumen. Allein der Parametertransfer hätte bei der speziellen Rechnerarchitektur den Faktor 5 gegenüber einer Addition gekostet. Die Grundrechenarten waren leicht implementiert, doch wie wird eine Quadratwurzel gezogen? Sicher, der Algorithmus von Newton/Gauß ist ganz simpel - aber er mußte in dieser speziellen Anwendung schnell sein. Bei dem Startwert, der üblicherweise verwendet wird, nämlich dem Ausgangswert, konvergiert die ganze Geschichte elend langsam. Ich wollte ein Verfahren, das mit höchstens einer echten (und zeitintensiven) Ganzzahl-Division den gesuchten Wert auf 32Bit genau ermittelte. Zuerst verfiel ich auf's Tabellieren, was aber nur Speicher kostete und wenig Fortschritt brachte. Der Durchbruch ergab sich nach einer Analyse der Ergebnisse der Qudratwurzelberechnung:
Beispiel:
Erkenntnis 1: Die Ergebnisse alternieren, haben aber ansonsten dieselbe Ziffernfolge. Die Ziffernfolge hängt davon ab, wieviele Dezimalstellen das Argument der Berechnung hat.
Frage: Wie sieht das dann bei dritten, vierten, allgemein n-ten Wurzeln aus?
Gedanke: Gegeben sei eine positive ganze Zahl n mit k Ziffern, k
>30.
Wird aus dieser Zahl die Quadratwurzel gezogen, dann ist die Anzahl ihre
Ziffern K/2 (+/-1 Stelle möglich)
Erkenntnis 2: Jede beliebige Zahl mit k/2 Ziffern ist sehr nahe an der Quadratwurzel von n.Das Verfahren von Newton/Gauss konvergiert mit diesem Startwert rasend schnell.
Aus diesen Erkenntnissen, die in gleicher Weise auf die Rechnung mit Dualzahlen übertragbar sind, läßt sicht ein hübscher Algorithmus basteln.....
---------coming soon!
Die Quersumme einer nicht-negativen ganzen Dezimalzahl x ist durch die Summe ihrer Ziffern definiert. Eine offenbar sehr einfache Aufgabe stellt das Berechnen der Quersumme einer ganzen Zahl mittels Computer dar. Das sollte natürlich hübsch verpackt als wiederverwendbare Funktion bereitgestellt werden. Aufgaben mit diesem Schwierigkeitsgrad kommen durchaus in der Praxis vor. Als Anfängerübung werden sie ebenfalls gerne verwendet.
Der spontane Ansatz wird von einem geübten C-Programmierer direkt in den Rechner gehackt - langes Nachdenken erübrigt sich offenbar:
int qsum(int x)
{
int sum = 0;
while (x)
{
sum += x % 10;
x /= 10;
}
return sum;
}
Das ist eine ganz entzückende Funktion. Solange die Eingabe nicht verbraucht wurde, spaltet sie mit einer modulo-Division die jeweils letzte Ziffer ab und addiert sie zu einem Puffer. Anschließend wird die Eingabe um die letzte Ziffer verkürzt. Rückgabe des Ergebnisses - fertig!
Wie schon erwähnt, eine entzückende Funktion - nur hat sie zwei Schönheitsfehler:
Der erste Einwand läßt sich entkräften, indem die aufrufende Funktion dafür sorgt, daß kein negativer Wert als Aufrufparameter übergeben wird. Der zweite Schönheitsfehler läßt sich auch durch eine solche Maßnahme nicht beseitigen, da der Wertebereich bei int für gewöhnlich nur bis 32767 reicht. Der geübte C-Programmierer weiß natürlich auch hier sofortige Abhilfe. Es müssen eben der Formalparameter x und die Variable sum auf long int umgestellt werden - und bei der Konstanten 10 schadet es auch nicht:
long int qsum(long int x)
{
long int sum = 0L
while (x)
{
sum += x % 10L;
x /= 10L;
}
return sum;
}
Die neue Funktion berechnet die Quersumme von 54321 ganz vorzüglich, scheitert aber an der Quersumme einer 12-ziffrigen Zahl. Mancher Kunstprogrammierer fängt jetzt das Meckern an: „Du weißt wirklich nicht, was Du willst. Erst gefällt Dir int nicht, dann long int nicht - und nun willst Du etwas, was keiner in der Praxis braucht."
Da ist was dran. Die Aufgabenstellung war unpräzise formuliert. Also gut, nehmen wir an, meine Praxis bräuchte das Berechnen der Quersumme ganzer Zahlen, die gelegentlich mal 200 Ziffern lang sein können. Vor einigen Jahren brauchte meine Praxis tatsächlich so was...
Ein Wechsel der Sichtweise auf die Aufgabenstellung ist zwangsweise nötig. Ein genauerer Blick zeigt, daß das Abtrennen jeder Ziffer zwei Divisionen durch 10 erfordert. Das ist ganz schön aufwendig. Das Aufaddieren der einzelnen Ziffern will ich hier nicht gesondert bewerten, da es unabhängig von der Rechenmethode ohnehin geschehen muß.
Wer sich bewußt macht, daß im gewöhnlichen Leben Zahlen durch das Aufschreiben von Ziffern dargestellt werden, kommt der Lösung der Aufgabe ein gutes Stück näher. Die Divisionen sind genaugenommen nur durch die interne Darstellung der Zahlen im Rechner bedingt. Folgerung: Wenn die bisherige Darstellung ungünstig war, dann muß eine bessere verwendet werden. Eine, die eine Aufschreibung darstellt, aber keine Codierung. Wie wäre es, einen Eingabestring zu verwenden?
long int qsum(char * x)
{
long int sum = 0L;
while (*x)
{
sum += (long)(int)(*x - '0');
x++;
}
return sum;
}
Unter der Voraussetzung, daß eine gültige Zifferneingabe vorliegt, was billigerweise angenommen darf (haben wir nämlich vorhin auch zugestanden), verringert sich der Rechenaufwand pro Ziffer auf eine Subtraktion, eine Addition und das Weiterschalten eines Lesezeigers. Auf der untersten Maschinenebene sind das also drei Additionen pro Ziffer, was eine erfreuliche Verbesserung darstellt. Das gilt auch bei kurzen Zifferneingaben. Der einzige Wermutstropfen dieser Funktion: Auch sie verarbeitet nur ganze Zahlen bis zu einer bestimmten Länge n, die durch den Wertebereich des Typs long int gegeben ist. Eine Abschätzung kann davon ausgehen, daß pro Ziffer die Summe um maximal 9 wächst. Eine Zahl, die nur aus der Ziffer 9 aufgebaut ist, erreicht am frühesten das Limit.
n = ((231)-1)/9 = 238609294
Fazit: da Ganzzahlen von knapp 2,4 Milliarden Ziffern Länge in der Praxis eher selten verarbeitet werden, sollte uns das Ergebnis vorerst genügen. Aber auch für kurze Ziffernfolgen lohnt es sich, über die geeignete interne Darstellung des Datenobjektes nachzudenken.
| Stand: 19.11.2002 / |
|