Donald Knuth ist ein Informatiker, der so sehr auf die Genauigkeit seiner Bücher achtet, dass er einen hexadezimalen Dollar (2,56 $, 0x$1,00) für jeden gefundenen „Fehler“ anbietet, wobei als Fehler alles angesehen wird, was „technisch, historisch, typografisch oder politisch inkorrekt“ ist. Ich wollte unbedingt einen Scheck von Knuth erhalten, also beschloss ich, nach Fehlern in seinem herausragenden Werk „Die Kunst des Programmierens“ (TAOCP) zu suchen. Es gelang mir, drei zu finden. Wahrhaftig, Knuth schickte einen Scheck über 0x$3,00.
Wie Sie sehen, handelt es sich nicht um einen echten Scheck. Früher schickte Knuth echte Schecks, stellte dies jedoch 2008 aufgrund von ein. Jetzt verschickt er „persönliche Einlagenzertifikate“ bei (BoSS). Er sagt, dass er im Bedarfsfall echtes Geld senden kann, aber es scheint ihm zu umständlich zu sein.
Ich fand zwei Tippfehler und einen historischen Fehler. Ich werde sie der Reihenfolge nach auflisten, beginnend mit dem unbedeutendsten.
Tippfehler Nr. 1
Der erste Tippfehler befindet sich auf Seite 392 des dritten Bandes „Sortierung und Suche“, achte Zeile von unten: „Nach einem erfolglosen Suchvorgang ist es manchmal (sometime) wünschenswert, einen neuen Eintrag in die Tabelle einzufügen, der enthält K; die Methode, die dies tut, wird als Einfüge- und Suchalgorithmus bezeichnet. Der Fehler besteht darin, dass anstelle von manchmal sollte sein manchmal.
Natürlich ist es nicht überraschend, dass ein solcher Fehler auftritt. In diesem Artikel werden sicherlich einige Tippfehler zu finden sein (keine Auszeichnungen für deren Auffindung). Was wirklich erstaunlich ist, ist, dass man sie so lange nicht bemerkt hat. Seite 392 ist nicht tief im Mathematikabschnitt vergraben; das ist die erste Seite des sechsten Kapitels „Suche“! Wahrscheinlich einer der am häufigsten gelesenen Abschnitte des Buches. Dort sollten eigentlich die wenigsten Tippfehler zu finden sein, aber dem ist nicht so.
Übrigens, wenn Sie jemals gedacht haben, TAOCP zu lesen, probieren Sie es aus. Viele werden sagen, dass es ein Nachschlagewerk, das nicht zum direkten Lesen gedacht ist, aber das stimmt nicht. Der Autor hat eine klare Perspektive und einen eigenen Stil. Das einzige, was die Lesbarkeit behindert, ist die Komplexität der Mathematik. Es gibt jedoch eine einfache Lösung: Lesen Sie, bis Sie zur Mathematik gelangen, die Sie nicht verstehen, übergehen Sie diese und öffnen Sie das nächste Kapitel, das Sie verstehen können. Durch dieses Vorgehen überspringe ich mindestens 80 % des Buches, aber die restlichen 20 % sind großartig!
Es wird auch gesagt, dass TAOCP irrelevant ist, ist veraltet oder auf andere Weise nicht anwendbar auf „echte Programmierung“. Das stimmt ebenfalls nicht. Zum Beispiel wird im ersten Abschnitt nach der Einführung die Suche nach einem Element in einem unsortierten Array behandelt. Der einfachste Algorithmus ist allen Programmierern bekannt. Starten Sie den Zeiger am Anfang des Arrays und führen Sie dann folgende 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 Grenzüberprüfungen 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 
erfordern. Ein ausgeklügelterer Suchalgorithmus könnte nur eine Grenzüberprüfung benötigen. Fügen Sie das gesuchte Element ans Ende des Arrays an, starten Sie dann den Zeiger am Anfang des Arrays und führen Sie folgende Schritte in einer Schleife aus:
- Überprüfen Sie, ob das aktuelle Element das gewünschte ist. Wenn ja, geben wir eine Antwort zurück, wenn der Zeiger im Array liegt, oder einen Fehler, wenn nicht. Andernfalls
- Erhöhen Sie den Zeiger und fahren Sie fort.
Wie dem auch sei, das Element wird garantiert gefunden, und die Grenzüberprüfung erfolgt nur einmal, wenn dies geschieht. Es ist eine tiefgreifende Idee, aber sie ist einfach genug, selbst für einen Anfängerprogrammierer. Vielleicht kann ich nicht über die Relevanz der Arbeit für andere sprechen, aber ich konnte diese Weisheit sofort sowohl in meinem persönlichen als auch in meinem beruflichen Code anwenden. Das Buch TAOCP ist voll von solchen Perlen (um fair zu sein, es gibt auch viele seltsame Sachen darin, wie ).
„Suchen, suchen“
So lange
Suchen, suchen
Ich wollte einfach nur tanzen“
— Luther Vandross, „Suchen“ (1980)
Tippfehler Nr. 2
Der zweite Druckfehler befindet sich im Band 4A, "Kombinatorische Algorithmen", Teil 1. Auf Seite 60 wird das Problem der Planung von Auftritten von Comedians in verschiedenen Casinos beschrieben. Als Beispiel werden mehrere echte Comedians genannt, darunter Lily Tomlin, "Weird Al" Yankovic und Robin Williams, der noch am Leben war, als das Buch veröffentlicht wurde. Knuth führt im Index immer vollständige Namen an, weshalb Williams auf Seite 882 als "Williams, Robin McLaurin" erwähnt wird. Doch sein zweiter Vorname endet auf "n" und nicht auf "m", also McLaurin.
McLaurin ist der Mädchenname seiner Mutter. Sie war die Ururenkelin von Anselm Joseph McLaurin, dem 34. Gouverneur von Mississippi. Seine Amtszeit ist anscheinend nicht durch etwas Positives in Erinnerung geblieben. Aus dem Buch :
„Das wichtigste Ereignis während der Amtszeit von MacLorin war die Kriegserklärung der Vereinigten Staaten an Spanien im Frühjahr 1898... Leider bot der Krieg möglicherweise einigen Regierungsbeamten die Gelegenheit, Bestechung auszunehmen. MacLorin wurde verschiedener fragwürdiger Praktiken beschuldigt, einschließlich Nepotismus und übermäßigen Einsatz der Begnadigungsbefugnisse. In der Ära der Abstinenz warf man dem Gouverneur Trunkenheit vor, was er öffentlich einräumte.“
Historischer Fehler
Lassen Sie uns betrachten traditioneller Multiplikationsalgorithmus aus dem Lehrplan. Wie viele eindimensionale Multiplikationsoperationen sind erforderlich? Angenommen, Sie multiplizieren 
-stellige Zahl 
findet man 
-stellig 
. Zuerst multiplizieren Sie die erste Ziffer 
mit jeder Ziffer 
nacheinander. Dann multiplizieren Sie die zweite Ziffer 
mit jeder Ziffer 
nacheinander und so weiter, bis Sie alle Ziffern durchlaufen haben. 
. Auf diese Weise erfordert die traditionelle Multiplikation 
primitive Multiplikationen. Insbesondere die Multiplikation zweier Zahlen nach 
Stellen erfordert 
eindimensionale Multiplikationen.
Das ist nicht ideal, aber der Prozess kann durch eine Methode optimiert werden, die von dem sowjetischen Mathematiker Anatoli Alexejewitsch Karazub entwickelt wurde. Angenommen, dass 
und 
es zweistellige Dezimalzahlen gibt; das heißt, es existieren Zahlen 
, 
, 
, 
sodass 
und 
(die Generalisierung dieses Algorithmus für größere Ziffern erfordert bestimmte Manipulationen; obwohl das nicht allzu kompliziert ist, halte ich es für besser, bei einem einfachen Beispiel zu bleiben, um Missverständnisse zu vermeiden). Dann 
, 
, 
. Das Multiplikation von Binomen ergibt 
. Bis jetzt haben wir immer noch 
einfache Multiplikationen: 
, 
, 
, 
. Jetzt addieren und subtrahieren wir 
. Nach mehreren Umstellungen, die ich dem Leser als Übung überlasse, erhält man 
— insgesamt drei einfache Multiplikationen! (Es gibt einige feste Koeffizienten, die nur durch Addition und Verschiebung der Stellen berechnet werden können).
Bitte verlangen Sie keinen Beweis, aber der Karazuba-Algorithmus (rekursiv aus dem obigen Beispiel generalisiert) verbessert die traditionelle Multiplikationsmethode von 
Operationen auf 
. Bitte beachten Sie, dass dies eine tatsächliche Verbesserung des Algorithmus ist und keine Optimierung für das Kopfrechnen. In der Tat ist der Algorithmus nicht für das Kopfrechnen geeignet, da er hohe Overheadkosten für rekursive Operationen erfordert. Darüber hinaus wird der Effekt nicht vollständig sichtbar, bis die Zahlen groß genug sind (zum Glück kamen nach dem Karatsuba-Algorithmus noch schnellere Methoden: Im März 2019 wurde ein Algorithmus veröffentlicht, der nur Multiplikationen benötigt; die Beschleunigung ist nur für unvorstellbar große Zahlen anwendbar).
Dieser Algorithmus wird auf Seite 295 des zweiten Bandes von «Die Kunst des Programmierens» beschrieben. Dort schreibt Knuth: „Es ist merkwürdig, 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 den Artikel „Die Komplexität der Berechnungen“, in dem er mehrere Dinge sagt: 1) etwa 1956 vermutete Kolmogorov, dass Multiplikation nicht in weniger als 
Schritten durchgeführt werden kann; 2) in 1960 Im Jahr präsentierte Karatsuba auf einem Seminar, wo Kolmogorov seine Hypothese n² darlegte. 3) „Genau eine Woche später“ entwickelte Karatsuba den Algorithmus „Teile und herrsche“; 4) 1962 schrieb und veröffentlichte Kolmogorov einen Artikel. im Namen von Karatsuba mit der Beschreibung des Algorithmus. „Ich erfuhr von diesem Artikel erst, nachdem er nachgedruckt wurde.“
Somit liegt der Fehler darin, dass anstelle von 1962 das Jahr angegeben werden sollte. 1960 Das ist alles.
Analyse
Die Fehlersuche erforderte kein besonderes Geschick.
- Der erste Fehler war so banal, wie es nur sein konnte, und befand sich an einer relativ auffälligen Stelle (Anfang des Kapitels). Jeder Idiot hätte ihn gefunden; nur ich war der Idiot.
- Die Suche nach dem zweiten Fehler erforderte Glück und Fleiß, aber nicht unbedingt Können. Das Verzeichnis für „Williams“ befindet sich auf der vorletzten Seite des Bandes, ein ziemlich bemerkenswerter Teil des Buches. Ich blätterte gerade durch das Inhaltsverzeichnis (es ist nicht so traurig, wie es scheint, denn in Knuths Verzeichnissen sind einige Easter Eggs versteckt. Zum Beispiel gibt es Einträge in Arabisch und Hebräisch, die beide auf Seite 66 verweisen. Aber auf dieser Seite wird keine der Sprachen erwähnt; stattdessen wird von „Sprachen, die von rechts nach links gelesen werden“ gesprochen). Und meine Aufmerksamkeit wurde auf den zweiten Namen gelenkt. Da ich normalerweise Wikipedia lese, habe ich Robin Williams überprüft und eine Diskrepanz bemerkt.
- Ich wünschte, ich könnte sagen, dass ich ernsthaft recherchiert habe, um den historischen Fehler zu finden, aber tatsächlich habe ich einfach nur einen Blick auf . In den ersten Zeilen steht: „Der Karatsuba-Algorithmus ist ein Algorithmus für schnelles Multiplizieren. Er wurde von Anatoli Karatsuba 1960 entdeckt und 1962 veröffentlicht.“ Danach blieb nur noch, zwei plus zwei zu addieren.
In Zukunft möchte ich einen bedeutenderen Fehler finden, insbesondere im Knuth-Code. Ich würde auch gerne einen Fehler im ersten Band von „Die Kunst der Programmierung“ finden. Vielleicht würde ich das 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 Hinzufügung s, einer Ersetzung m findet man n und 2 findet man 0. Bei einem Preis von 2,56 $ sind das ziemlich lukrative Symbole; wenn man so viel bezahlt würde, würde ein Artikel mit 1000 Wörtern (im Durchschnitt vier Zeichen) einem zehn solcher Beträge bringen.
- Mit drei hexadezimalen Dollar teile ich zusammen mit 29 anderen Bürgern den 69. Platz auf der Liste der reichsten Bankeinleger von San-Serrif (Stand: 1. Mai 2019).
Weitere Diskussionen über Knuths Schecks
Allgemeine Hinweise 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, darauf zu warten, bis Sie eine Sammlung von Fehlern zum Einreichen erstellt haben. Indem Sie mehrere echte, jedoch nicht besonders wertvolle Fehler kombinieren, erhöhen Sie die Wahrscheinlichkeit, dass einer von ihnen tatsächlich als Fehler oder Hinweis anerkannt wird. Wenn Fehler einzeln eingereicht werden, könnte jeder von ihnen abgelehnt werden.
Ich wollte nicht einfach belanglose Tippfehler einreichen und habe den Rat befolgt, die E-Mail erst zu senden, als ich einen historischen Fehler gefunden hatte, der ernst genug erschien.
Ashutosh Mehra ist der drittreichste Investor in San-Serif mit einem beeindruckenden Vermögen von 0x$207,f0 in BoSS.
- Diverse:
Quelle: habr.com
