Donald Knuth — ein Wissenschaftler im Bereich Informatik, der so sehr auf die Richtigkeit seiner Bücher achtet, dass er einen hexadezimalen Dollar ($2,56, 0x$1,00) für jeden gefundenen „Fehler“ anbietet, wobei ein Fehler alles zählt, was „technisch, historisch, typografisch oder politisch inkorrekt“ ist. Ich wollte unbedingt einen Scheck von Knuth bekommen, also beschloss ich, nach Fehlern in seinem herausragenden Werk zu suchen „Die Kunst des Programmierens“ (TAOCP). Mir gelang es, drei zu finden. Treu der Wortwahl schickte Knuth einen Scheck über 0x$3,00.
Wie Sie sehen, ist das kein echter Scheck. Früher verschickte Knuth echte Schecks, hörte aber 2008 aufgrund von . Jetzt versendet er „persönliche Einzahlungszertifikate“ bei der (BoSS). Er sagt, dass er im Bedarfsfall echtes Geld verschicken kann, aber das scheint zu umständlich zu sein.
Ich fand zwei Tippfehler und einen historischen Fehler. Ich werde sie in absteigender Reihenfolge der Trivialität auflisten.
Tippfehler Nr. 1
Der erste Tippfehler — auf Seite 392 des dritten Bandes „Sortieren und Suchen“, achte Zeile von unten: „Nach einem gescheiterten Suchvorgang ist es manchmal (sometime) wünschenswert, einen neuen Eintrag in die Tabelle einzufügen, der K; die Methode, die dies tut, wird als Such- und Einfügemethode bezeichnet. Der Fehler besteht darin, dass anstelle von sometime sollte sometimes.
Natürlich ist an einem solchen Fehler nichts Überraschendes. In diesem Artikel wird es sicherlich einige Tippfehler geben (keine Belohnungen für deren Auffindung). Was wirklich überraschend ist, ist, dass es so lange übersehen wurde. Seite 392 ist nicht tief im Mathematikbereich vergraben, es ist die erste Seite des sechsten Kapitels „Suchen“! Vielleicht einer der am häufigsten gelesenen Abschnitte des Buches. Eigentlich sollte es dort am wenigsten Tippfehler geben, aber dem ist nicht so.
Übrigens, wenn Sie jemals darüber nachgedacht haben, TAOCP zu lesen, probieren Sie es aus. Viele werden sagen, dass es ein Nachschlagewerk, das nicht zum direkten Lesen gedacht ist, aber das ist nicht wahr. Der Autor hat eine klare Sichtweise und einen eigenwilligen Stil. Das Einzige, was die Lesbarkeit einschränkt, ist die Komplexität der Mathematik. Es gibt jedoch eine einfache Lösung: Lesen Sie weiter, bis Sie zur Mathematik gelangen, die Sie nicht verstehen, überspringen Sie sie und gehen Sie zum nächsten Abschnitt, den Sie verstehen können. Auf diese Weise lasse ich mindestens 80% des Buches aus, aber die restlichen 20% sind großartig!
Es wird auch gesagt, dass TAOCP nicht relevant ist, veraltet oder auf andere Weise nicht auf „reales Programmieren“ anwendbar. Das ist auch nicht wahr. Im ersten Abschnitt nach der Einleitung geht es um die Suche nach einem Element in einem unsortierten Array. Der einfachste Algorithmus ist allen Programmierern bekannt. Setzen Sie den Zeiger am Anfang des Arrays, und führen Sie dann die folgenden Schritte in einer Schleife aus:
- Überprüfen Sie, ob das aktuelle Element das gewünschte ist. Wenn ja, geben Sie es zurück; andernfalls
- Überprüfen Sie, ob der Zeiger außerhalb des Arrays liegt. Wenn ja, geben Sie einen Fehler zurück; andernfalls
- Erhöhen Sie den Zeiger und fahren Sie fort.
Nun betrachten wir: Wie viele Grenzkontrollen erfordert dieser Algorithmus im Durchschnitt? Im schlimmsten Fall, wenn das Array kein Element enthält, ist für jedes Element in der Liste eine Überprüfung erforderlich, und im Durchschnitt wird es etwa so aussehen 
. Ein intelligenterer Suchalgorithmus könnte mit nur einer Grenzkontrolle auskommen. Fügen Sie das benötigte Element ans Ende des Arrays an, setzen Sie den Zeiger am Anfang des Arrays und führen Sie dann die folgenden Schritte in einer Schleife aus:
- Überprüfen Sie, ob das aktuelle Element das gewünschte ist. Wenn ja, geben Sie die Antwort zurück, wenn der Zeiger innerhalb des Arrays liegt, oder einen Fehler, wenn dies nicht der Fall ist. Andernfalls
- Erhöhen Sie den Zeiger und fahren Sie fort.
So oder so wird das Element garantiert gefunden, und die Grenzkontrolle erfolgt nur einmal, wenn dies der Fall ist. Das ist eine tiefgründige Idee, aber sie ist einfach genug, selbst für einen Anfänger. Ich kann wahrscheinlich nicht über die Relevanz dieser Arbeit für andere sprechen, aber ich konnte diese Weisheit sofort in meinem persönlichen sowie professionellen Code anwenden. Das Buch TAOCP ist voll von solchen Perlen (um der Gerechtigkeit willen, dort sind auch viele merkwürdige Dinge, wie ).
„Suche, Suche
So lange
Suche, Suche
Ich wollte einfach nur tanzen“
— Luther Vandross, „Suche“ (1980)
Tippfehler Nr. 2
Der zweite Druckfehler befindet sich in Band 4A, "Kombinatorische Algorithmen", Teil 1. Auf Seite 60 wird eine Aufgabe zur Planung von Auftritten von Komikern in verschiedenen Casinos beschrieben. Als Beispiele werden mehrere echte Komiker genannt, darunter Lily Tomlin, "Weird Al" Yankovic und Robin Williams, der noch lebte, als das Buch veröffentlicht wurde. Knut führt im Register immer die vollen Namen an, weshalb Williams auf Seite 882 als "Williams, Robin Mac-Lorin" erwähnt wird. Aber sein zweiter Vorname endet mit einem "n" und nicht mit einem "m", also Mac-Lorin.
Mac-Lorin ist der Mädchennamen seiner Mutter. Sie war die Urenkelin von Anselm Joseph Mac-Lorin, dem 34. Gouverneur von Mississippi. Seine Amtszeit ist anscheinend nicht mit etwas Positivem in Erinnerung geblieben. Aus dem Buch :
"Das wichtigste Ereignis während der Amtszeit von Mac-Lorin war die Kriegserklärung der Vereinigten Staaten an Spanien im Frühling 1898... Leider bot der Krieg möglicherweise einigen Beamten die Gelegenheit, Bestechung zu praktizieren. Mac-Lorin wurde verschiedener fragwürdiger Praktiken beschuldigt, einschließlich Nepotismus und übermäßiger Nutzung seiner Begnadigungsbefugnisse. In der Ära der Abstinenz beschuldigten die Kritiker den Gouverneur des Alkoholmissbrauchs, was er öffentlich zugab."
Historischer Fehler
Betrachten wir traditioneller Multiplikationsalgorithmus aus dem Schulprogramm. Wie viele einstellige Multiplikationen benötigt er? Angenommen, Sie multiplizieren 
-stellige Zahl 
auf 
-stellige 
. Zuerst multiplizieren Sie die erste Ziffer 
mit jeder Ziffer 
der Reihe nach. Dann multiplizieren Sie die zweite Ziffer 
mit jeder Ziffer 
der Reihe nach und so weiter, bis Sie alle Ziffern durchlaufen haben 
. So erfordert die traditionelle Multiplikation 
primitive Multiplikationen. Insbesondere erfordert die Multiplikation von zwei Zahlen nach 
-stellen 
einstellige Multiplikationen.
Das ist schlecht, aber der Prozess kann durch eine Methode optimiert werden, die vom sowjetischen Mathematiker Anatoli Alexejewitsch Karazuba entwickelt wurde. Angenommen, 
und 
sind zweistellige Dezimalzahlen; das heißt, es gibt Zahlen 
, 
, 
, 
so dass 
und 
(die Verallgemeinerung dieses Algorithmus auf größere Ziffern erfordert bestimmte Manipulationen; obwohl das nicht zu kompliziert ist, werde ich besser bei diesem einfachen Beispiel bleiben, um keine Details falsch zu machen). Dann 
, 
, 
. Die Multiplikation von Binomen ergibt 
. Bis zu diesem Zeitpunkt haben wir immer noch 
einstellige Multiplikationen: 
, 
, 
, 
. Jetzt addieren und subtrahieren wir 
. Nach mehreren Umstellungen, die ich als Übung für den Leser lasse, ergibt sich 
— insgesamt drei einstellige Multiplikationen! (Es gibt einige konstante Koeffizienten, aber die können nur durch Addition und Verschieben der Stellen berechnet werden).
Bitte verlangen Sie keinen Beweis, aber der Karatsuba-Algorithmus (rekursiv verallgemeinert aus dem obigen Beispiel) verbessert die traditionelle Multiplikationsmethode von 
Operationen auf 
. Beachten Sie, dass dies eine echte Verbesserung des Algorithmus ist und keine Optimierung für das Rechnen im Kopf. Tatsächlich ist der Algorithmus nicht für das Kopfrechnen geeignet, da er große Overheads für die rekursiven Operationen erfordert. Außerdem wird der Effekt nicht voll zur Geltung kommen, solange die Zahlen nicht groß genug sind (zum Glück sind anstelle des Karatsuba-Algorithmus noch schnellere Methoden entstanden: Im März 2019 wurde ein Algorithmus veröffentlicht, der nur Multiplikationen erfordert; die Beschleunigung gilt nur für unvorstellbar große Zahlen).
Dieser Algorithmus ist auf Seite 295 des zweiten Bandes der „Berechneten Algorithmen“ beschrieben. Dort schreibt Knuth: „Es ist interessant, dass diese Idee erst im 1962 Jahr“ entdeckt wurde, als ein Artikel veröffentlicht wurde, der den Karatsuba-Algorithmus beschreibt. Aber! Im Jahr 1995 veröffentlichte Karatsuba einen Artikel mit dem Titel „Die Komplexität der Berechnungen“, in dem er einige Dinge sagt: 1) um 1956 vermutete Kolmogorov, dass Multiplikation nicht unter 
Schritten durchgeführt werden kann; 2) Im 1960 Jahr nahm Karatsuba an einem Seminar teil, in dem Kolmogorov seine Hypothese n² darlegte. 3) „Genau eine Woche nachher“ entwickelte Karatsuba den Algorithmus „Teile und herrsche“; 4) 1962 schrieb und veröffentlichte Kolmogorov einen Artikel im Namen von Karatsuba mit einer Beschreibung des Algorithmus. „Ich erfuhr erst davon, nachdem er nachgedruckt wurde“.
Somit liegt der Fehler darin, dass statt 1962 angegeben werden sollte 1960 Jahr. Das ist alles.
Analyse
Die Fehlersuche erforderte kein besonderes Können.
- Der erste Fehler war so banal, wie es nur sein kann, und befand sich an einer relativ sichtbaren Stelle (Anfang des Kapitels). Jeder Idiot hätte ihn gefunden; nur ich war der Idiot.
- Die Suche nach dem zweiten Druckfehler erforderte Glück und Fleiß, aber kein Können. Das Index für „Williams“ befindet sich auf der vorletzten Seite des Bands, ein recht auffälliger Teil des Buches. Ich blätterte gerade im Index (es ist nicht so schlimm, wie es scheint, denn in Knuths Indizes sind Ostereier versteckt. Zum Beispiel gibt es Einträge auf Arabisch und Hebräisch, die beide auf Seite 66 verweisen. Aber auf dieser Seite wird keine der Sprachen erwähnt; stattdessen geht es um „Sprachen, die von rechts nach links gelesen werden“). Und meine Aufmerksamkeit zog der zweite Name an. Da ich normalerweise Wikipedia lese, habe ich Robin Williams überprüft und eine Unstimmigkeit festgestellt.
- Ich wünschte, ich könnte sagen, dass ich eine ernsthafte Forschung betrieben habe, um den historischen Fehler zu finden, aber tatsächlich habe ich einfach nur geschaut . In den ersten Zeilen steht: „Der Karatsuba-Algorithmus ist ein Algorithmus zum schnellen Multiplizieren. Entdeckt von Anatolij Karatsuba im Jahr 1960 und veröffentlicht im Jahr 1962“. Danach blieb es nur noch, zwei und zwei zusammenzuzählen.
In Zukunft möchte ich einen erheblicheren Fehler finden, insbesondere im Code von Knuth. Ich würde auch gerne einen Bug im ersten Band „Fundamentale Algorithmen“ finden. Vielleicht würde ich einen finden, aber in der örtlichen Bibliothek gibt es aus irgendeinem Grund nur die Bände 2, 3 und 4A.
Finanzielle Fakten:
- Insgesamt besteht mein Beitrag zu TAOCP nur aus drei Symbolen: einer Addition s, einem Austausch m auf n und 2 auf 0. Bei einem Preis von 2,56 $ sind das ziemlich lukrative Symbole; wenn man Ihnen so viel Geld bezahlt, würde ein Artikel mit 1000 Wörtern (im Durchschnitt vier Symbole) Ihnen zehn Stück bringen.
- Mit drei hexadezimalen Dollar teile ich zusammen mit 29 anderen Bürgern den 69. Platz auf der Liste der reichsten Einleger der Bank San Seriffe (Stand 1. Mai 2019).
Weitere Diskussionen über Knuths Schecks
Allgemeine Empfehlungen zur Fehlersuche in Knuths Büchern. Betreffen hauptsächlich technische Fehler, die ich nicht habe. Es gibt einen Satz, den ich ernst genommen habe:
Es ist besser zu warten, bis Sie eine Sammlung von Fehlern zum Einreichen haben. Indem Sie mehrere echte, aber nicht sehr wertvolle Fehler kombinieren, erhöhen Sie die Wahrscheinlichkeit, dass einer von ihnen tatsächlich als Fehler oder Hinweis betrachtet wird. Wenn Sie Fehler einzeln einreichen, kann jeder von ihnen einzeln abgelehnt werden.
Ich wollte keine ausgedachten Tippfehler senden, sondern habe den Rat befolgt und das Schreiben erst abgeschickt, als ich einen historischen Fehler gefunden hatte, der mir ernst genug erschien.
Ashutosh Mehra ist der drittreichste Investor in San-Serif mit einem gewaltigen Vermögen von 0x$207,f0 in BoSS.
- Verschiedenes:
Quelle: habr.com
