Donald Knuth ist ein Informatiker, dem die Genauigkeit seiner Bücher, die er vorschlägt, sehr am Herzen liegt ein Hex-Dollar ($2,56, 0x$1,00) für jeden gefundenen „Fehler“, wobei ein Fehler als alles definiert ist, was „technisch, historisch, typografisch oder politisch falsch“ ist. Ich wollte unbedingt einen Scheck von Knuth bekommen, also beschloss ich, in seinem Hauptwerk nach Fehlern zu suchen „Die Kunst des Programmierens“ (TAOCP). Es ist uns gelungen, drei zu finden. Getreu seinem Wort schickte Knut einen Scheck 0x3,00 $.

Wie Sie sehen, handelt es sich hierbei nicht um einen echten Scheck. Knuth verschickte früher echte Schecks, hörte aber 2008 auf grassierender Betrug. Er verschickt nun „persönliche Einlagenzertifikate“ an Bank von San Serriff (Chef). Er sagt, er sei bereit, bei Bedarf echtes Geld zu schicken, aber es scheint, als wäre das ein zu großer Aufwand.

Ich habe zwei Tippfehler und einen historischen Fehler gefunden. Ich werde sie in der Reihenfolge abnehmender Trivialität auflisten.

Tippfehler Nr. 1

Der erste Tippfehler befindet sich auf Seite 392 des dritten Bandes „Sortieren und Suchen“, achte Zeile von unten: „Nach einer erfolglosen Suche ist es manchmal (manchmal) wünschenswert, einen neuen Datensatz in die Tabelle einzugeben, die Folgendes enthält.“ K; Die Methode, die dies tut, wird als Such- und Einfügealgorithmus bezeichnet. Der Fehler liegt stattdessen darin irgendwann sollte sein manchmal.

Natürlich ist ein solcher Fehler nicht überraschend. Allein in diesem Artikel gibt es sicher ein paar Tippfehler (keine Belohnung für deren Entdeckung). Was wirklich überraschend ist, ist, dass es so lange unbemerkt blieb. Seite 392 ist nicht tief im Mathematikteil vergraben, das ist es die allererste Seite Kapitel XNUMX „Suchen“! Möglicherweise einer der meistgelesenen Abschnitte des Buches. Theoretisch sollte es die wenigsten Tippfehler geben, aber nein.

Übrigens, wenn Sie jemals darüber nachgedacht haben, TAOCP zu lesen, probieren Sie es aus. Viele werden sagen, dass dies der Fall ist Verzeichnis, nicht zum direkten Lesen gedacht, aber das stimmt nicht. Der Autor hat einen klaren Standpunkt und einen unverwechselbaren Stil. Das Einzige, was die Lesbarkeit beeinträchtigt, ist die Komplexität der Mathematik. Es gibt jedoch eine einfache Lösung: Lesen Sie so lange, bis Sie die Mathematik nicht mehr verstehen, überspringen Sie sie und fahren Sie mit dem nächsten Abschnitt fort, den Sie verstehen können. Wenn ich es so lese, vermisse ich mindestens 80 % des Buches, aber die anderen 20 % sind großartig!

Es wird auch gesagt, dass TAOCP irrelevant, ist veraltet oder aus anderen Gründen nicht auf die „echte Programmierung“ anwendbar. Auch das stimmt nicht. Im ersten Abschnitt nach der Einleitung geht es beispielsweise darum, ein Element in einem unsortierten Array zu finden. Der einfachste Algorithmus ist allen Programmierern bekannt. Starten Sie den Zeiger am Anfang des Arrays und führen Sie dann in einer Schleife Folgendes aus:

1. Überprüfen Sie, ob das aktuelle Element das gewünschte ist. Wenn ja, geben wir es zurück; sonst
2. Überprüfen Sie, ob der Zeiger außerhalb der Array-Grenze liegt. Wenn ja, geben Sie einen Fehler zurück. sonst
3. Vergrößern und fortfahren.

Überlegen Sie nun: Wie viele Grenzüberprüfungen erfordert dieser Algorithmus im Durchschnitt? Im schlimmsten Fall, wenn das Array kein Element enthält, muss jedes Element in der Liste einmal überprüft werden, und im Durchschnitt wird es in etwa so aussehen . Ein intelligenterer Suchalgorithmus könnte mit nur einer Grenzüberprüfung auskommen. Hängen Sie das gewünschte Element an das Ende des Arrays an, starten Sie dann den Zeiger am Anfang des Arrays und führen Sie in einer Schleife Folgendes aus:

1. Überprüfen Sie, ob das aktuelle Element das gewünschte ist. Wenn ja, geben wir eine Antwort zurück, wenn sich der Zeiger innerhalb des Arrays befindet, oder einen Fehler, wenn dies nicht der Fall ist. Sonst
2. Vergrößern und fortfahren.

Auf die eine oder andere Weise wird garantiert, dass das Element gefunden wird, und die Überprüfung der Grenzen wird in diesem Fall nur einmal durchgeführt. Das ist eine tiefgründige Idee, aber selbst für einen unerfahrenen Programmierer einfach genug. Ich kann wahrscheinlich nicht über die Relevanz der Arbeit für andere sprechen, aber ich war sofort in der Lage, diese Weisheit sowohl auf den persönlichen als auch auf den beruflichen Code anzuwenden. Das TAOCP-Buch ist voll von solchen Juwelen (um fair zu sein, es gibt dort auch viele seltsame Dinge, wie z Blasensortierung).

"Suche Suche
So lang
Suche Suche
Ich wollte einfach nur tanzen“
— Luther Vandross, „The Search“ (1980)

Tippfehler Nr. 2

Der zweite Tippfehler befindet sich in Band 4A, Kombinatorische Algorithmen, Teil 1. Seite 60 beschreibt ein Problem bei der Planung von Auftritten von Komikern in verschiedenen Casinos. Als Beispiele werden mehrere echte Komiker genannt, darunter Lily Tomlin, Weird Al Yankovic und Robin Williams, der zum Zeitpunkt der Veröffentlichung des Buches noch am Leben war. Knuth listet im Index immer die vollständigen Namen auf, daher wird Williams auf Seite 882 als „Williams, Robin McLorim“ aufgeführt. Aber sein zweiter Vorname endet mit „n“ und nicht mit „m“, also McLaurin.

McLaurin war der Mädchenname seiner Mutter. Sie war die Urenkelin von Anselm Joseph McLaurin, dem 34. Gouverneur von Mississippi. An seine Herrschaft blieb offenbar nichts Gutes in Erinnerung. Aus Buch „Mississippi: Geschichte“:

„Das wichtigste Ereignis während der McLaurin-Regierung war die Kriegserklärung der Vereinigten Staaten an Spanien im Frühjahr 1898 … Leider hat der Krieg einigen Regierungsbeamten möglicherweise die Möglichkeit geboten, sich an Bestechungen zu beteiligen. McLaurin wurden verschiedene fragwürdige Praktiken vorgeworfen, darunter Vetternwirtschaft und der übermäßige Einsatz von Begnadigungsbefugnissen. Während der Abstinenzbewegung beschuldigten Kritiker den Gouverneur, ein Trunkenbold zu sein, was er auch öffentlich zugab.“

Historischer Fehler

Betrachten traditioneller Multiplikationsalgorithmus aus dem Schullehrplan. Wie viele einstellige Multiplikationen sind erforderlich? Angenommen, Sie multiplizieren -stellige Nummer auf -bisschen . Multiplizieren Sie zunächst die erste Ziffer für jede Ziffer Einer nach dem anderen. Dann multiplizieren Sie die zweite Ziffer für jede Ziffer eine nach der anderen und so weiter, bis Sie alle Zahlen durchgegangen sind . Dies erfordert die traditionelle Multiplikation primitive Multiplikationen. Insbesondere die Multiplikation zweier Zahlen mit Ränge erforderlich einstellige Multiplikationen.

Das ist schlecht, aber es ist möglich, den Prozess mit einer vom sowjetischen Mathematiker Anatoly Alekseevich Karatsuba entwickelten Methode zu optimieren. Tun wir mal so и  - zweistellige Dezimalzahlen; das heißt, es gibt Zahlen , , , so dass и (Die Verallgemeinerung dieses Algorithmus auf größere Zahlen erfordert einige Manipulationen; obwohl es nicht allzu schwierig ist, werde ich mich besser an ein einfaches Beispiel halten, um keine Fehler in den Details zu machen.) Dann , , . Die Multiplikation von Binomialen ergibt . Im Moment haben wir noch einstellige Multiplikation: , , , . Jetzt addieren und subtrahieren wir . Nach ein paar Umstellungen, die ich dem Leser als Übung überlasse, klappt es  - nur drei einstellige Multiplikationen! (Es gibt einige konstante Koeffizienten, die jedoch nur durch Addition und Verschiebung der Ziffern berechnet werden können.)

Bitten Sie nicht um Beweise, aber Karatsuba-Algorithmus (rekursiv verallgemeinert aus dem obigen Beispiel) verbessert die traditionelle Multiplikationsmethode mit Operationen vor . Bitte beachten Sie, dass es sich hierbei um eine echte Verbesserung des Algorithmus und nicht um eine Optimierung für mentale Berechnungen handelt. Tatsächlich ist der Algorithmus nicht für Kopfrechnen geeignet, da er hohe Overhead-Kosten für rekursive Operationen erfordert. Darüber hinaus wird sich der Effekt erst vollständig manifestieren, wenn die Zahlen groß genug sind (glücklicherweise wurde Karatsubas Algorithmus durch noch schnellere Methoden ersetzt: Im März 2019 wurde ein Algorithmus veröffentlicht, der nur benötigt n anmelden n Multiplikationen; Beschleunigung gilt nur für unvorstellbar große Zahlen).

Dieser Algorithmus wird auf Seite 295 von Band XNUMX, Semi-Numerical Algorithms, beschrieben. Dort schreibt Knuth: „Es ist merkwürdig, dass diese Idee erst in entdeckt wurde 1962 Jahr“, als ein Artikel veröffentlicht wurde, der Karatsubas Algorithmus beschreibt. Aber! Im Jahr 1995 veröffentlichte Karatsuba einen Artikel über „Computational Complexity“, in dem mehrere Dinge gesagt werden: 1) Um 1956 schlug Kolmogorov vor, dass die Multiplikation nicht in weniger als durchgeführt werden könne Schritte; 2) im 1960 Jahr besuchte Karatsuba das Seminar, in dem Kolmogorov seine Hypothese n² vorstellte. 3) „In genau einer Woche“ entwickelte Karatsuba den „Teile und herrsche“-Algorithmus; 4) 1962 schrieb und veröffentlichte Kolmogorov einen Artikel im Namen von Karatsuba mit einer Beschreibung des Algorithmus. „Ich habe von diesem Artikel erst erfahren, nachdem er erneut veröffentlicht wurde.“

Der Fehler ist also, dass statt 1962 muss angegeben werden 1960 Jahr. Das ist alles.

Analyse

Das Auffinden von Fehlern erforderte keine besonderen Fähigkeiten.

1. Der erste Fehler war möglichst trivial und befand sich an einer relativ sichtbaren Stelle (am Anfang des Kapitels). Jeder Idiot hätte es gefunden; Es stellte sich heraus, dass ich einfach dieser Idiot war.
2. Das Finden des zweiten Tippfehlers erforderte Glück und Fleiß, aber kein Geschick. Der Index für „Williams“ befindet sich auf der vorletzten Seite des Bandes, einem ziemlich prominenten Teil des Buches. Ich habe gerade den Index durchgeblättert (es ist nicht so erbärmlich, wie es klingt, denn in Knuths Indexen sind Easter Eggs versteckt. Beispielsweise gibt es Einträge auf Arabisch und Hebräisch, die beide auf Seite 66 verweisen. Aber auf dieser Seite wird nicht erwähnt beide Sprachen; stattdessen bezieht es sich auf „Sprachen, die von rechts nach links gelesen werden“). Und der zweite Name erregte meine Aufmerksamkeit. Da ich normalerweise Wikipedia lese, habe ich Robin Williams überprüft und eine Diskrepanz festgestellt.
3. Ich wünschte, ich könnte sagen, ich hätte ernsthafte Nachforschungen angestellt, um einen historischen Fehler zu finden, aber eigentlich habe ich nur nachgeschaut Wikipedia-Seite über Karatsubas Algorithmus. In den allerersten Zeilen heißt es: „Der Karatsuba-Algorithmus ist ein schneller Multiplikationsalgorithmus. 1960 von Anatoly Karatsuba entdeckt und 1962 veröffentlicht.“ Danach musste nur noch zwei und zwei addiert werden.

In Zukunft würde ich gerne einen schwerwiegenderen Fehler finden, insbesondere in Knuths Code. Ich würde auch gerne einen Fehler im ersten Band von Fundamental Algorithms finden. Vielleicht hätte ich es gefunden, aber aus irgendeinem Grund gibt es in der örtlichen Bibliothek nur die Bände 2, 3 und 4A.

Finanzielle Fakten:

• Insgesamt besteht mein Beitrag zu TAOCP nur aus drei Zeichen: einer Ergänzung s, Ersatz m auf n и 2 auf 0. Mit 2,56 $ sind dies einige ziemlich lukrative Symbole; Wenn Sie so viel Geld bekämen, würden Sie für einen Artikel mit 1000 Wörtern (durchschnittlich vier Zeichen) zehntausend Dollar verdienen.
• Mit drei hexadezimalen Dollars stehe ich gemeinsam mit 29 weiteren Bürgern auf Platz 69 der Liste der reichsten Einleger der San Serriff Bank (Stand: 1. Mai 2019).

Weitere Diskussionen über Schecks von Knuth

• So erhalten Sie einen Scheck von Knuth

  Allgemeine Empfehlungen zum Auffinden von Fehlern in Knuths Büchern. Meistens handelt es sich dabei um technische Fehler, die ich nicht habe. Da gibt es einen Vorschlag, den ich ernst genommen habe:

  Am besten warten Sie mit der Übermittlung, bis Sie eine Reihe von Fehlern gesammelt haben. Indem Sie mehrere echte, aber wenig wertvolle Fehler kombinieren, erhöhen Sie die Wahrscheinlichkeit, dass einer davon tatsächlich als Fehler oder Ratschlag angesehen wird. Wenn Sie Fehler einzeln einreichen, kann jeder einzeln abgelehnt werden.

  Ich wollte nicht nur unsinnige Tippfehler verschicken, sondern befolgte den Rat und schickte den Brief nur, wenn ich einen historischen Fehler fand, der schwerwiegend genug schien.

• Ashutosh Mehras Schecks

  Ashutosh Mehra ist der drittreichste Investor in San Serriff mit einem satten Nettovermögen von 0x$207.f0 in BoSS.

• Suchen Sie nach nicht funktionierenden Fehlern im echten TeX-Code
• Sonstiges: #1 #2 #3 #4 #5 #6

Source: habr.com