Donald Knuth ist ein Informatiker, der sich so sehr um die Richtigkeit seiner Bücher kümmert, dass er einen Hex-Dollar (2,56 USD, 0x 1,00 USD) für jeden gefundenen „Fehler“ anbietet, bei dem alles, was „technisch, historisch, typografisch“ ist, als Fehler betrachtet wird. oder politisch falsch. " Ich wollte unbedingt einen Scheck von Knut bekommen, deshalb habe ich mich entschlossen, in seiner herausragenden Arbeit „The Art of Programming“ (TAOCP) nach Fehlern zu suchen. Ich habe drei gefunden. Getreu dem Wort schickte Knut einen Scheck über 0x $ 3,00 .



Wie Sie sehen können, ist dies keine echte Prüfung. Knut schickte früher echte Schecks, hörte aber 2008 wegen zügellosen Betrugs auf . Jetzt verschickt er "persönliche Einlagenzertifikate" bei der Bank of San Serriff (BoSS). Er sagt, er sei bereit, bei Bedarf echtes Geld zu senden, aber es scheint zu mühsam zu sein.

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

Tippfehler Nummer 1

Der erste Tippfehler befindet sich auf Seite 392 des dritten Bandes „Sortieren und Suchen“, die achte Zeile von unten: „Nach einer erfolglosen Suche ist es manchmal (manchmal) ratsam, einen neuen Datensatz in die Tabelle mit K aufzunehmen . Die Methode, die dies tut, wird als Such- und Einfügealgorithmus bezeichnet. Der Fehler ist, dass statt irgendwann manchmal sein sollte.

Ein solcher Fehler ist natürlich nicht überraschend. Nur in diesem Artikel gibt es sicher ein paar Tippfehler (keine Belohnungen dafür, sie zu finden). Was wirklich überrascht, ist, dass es so lange nicht bemerkt wurde. Seite 392 ist nicht tief im Abschnitt mit Mathematik vergraben, dies ist die allererste Seite des sechsten Kapitels von „Suche“! Vielleicht einer der meistgelesenen Abschnitte des Buches. Theoretisch sollte es die geringsten Tippfehler geben, aber nein.

Übrigens, wenn Sie jemals daran gedacht haben, TAOCP zu lesen, probieren Sie es aus. Viele werden sagen, dass dies ein Leitfaden ist, der nicht zum direkten Lesen gedacht ist, aber dies ist nicht wahr. Der Autor hat einen klaren Standpunkt und einen besonderen Stil. Das einzige, was die Lesbarkeit verhindert, ist die Komplexität der Mathematik. Es gibt jedoch eine einfache Lösung: Lesen Sie, bis Sie zu der Mathematik gelangen, die Sie nicht verstehen, überspringen Sie sie und öffnen Sie den nächsten Abschnitt, den Sie verstehen können. Wenn ich so lese, vermisse ich mindestens 80% des Buches, aber die restlichen 20% sind großartig!

Sie sagen auch, dass TAOCP irrelevant , veraltet oder auf andere Weise nicht auf „echte Programmierung“ anwendbar ist. Dies ist auch nicht wahr. Beispielsweise wird im ersten Abschnitt nach der Einführung die Suche nach einem Element in einem unsortierten Array berücksichtigt. Der einfachste Algorithmus ist allen Programmierern bekannt. Führen Sie den Zeiger am Anfang des Arrays aus und führen Sie dann die folgenden Schritte in einer Schleife aus:

1. Überprüfen Sie, ob der aktuelle Artikel gewünscht wird. Wenn ja, geben Sie es zurück. sonst
   
2. Überprüfen Sie, ob sich der Zeiger außerhalb des Arrays befindet. Wenn ja, geben Sie einen Fehler zurück. sonst
   
3. Erhöhen Sie den Zeiger und fahren Sie fort.

Bedenken Sie nun: Wie viele Grenzkontrollen benötigt dieser Algorithmus durchschnittlich? Im schlimmsten Fall, wenn das Array kein Element enthält, ist für jedes Element in der Liste eine Prüfung erforderlich, und im Durchschnitt ist es so etwas wie $$$N / 2$. Ein intelligenterer Suchalgorithmus kann mit nur einer Grenzprüfung durchgeführt werden. Fügen Sie das gewünschte Element an das Ende des Arrays an, führen Sie den Zeiger am Anfang des Arrays aus und führen Sie die folgenden Schritte in einer Schleife aus:

1. Überprüfen Sie, ob der aktuelle Artikel gewünscht wird. In diesem Fall geben wir die Antwort zurück, wenn sich der Zeiger innerhalb des Arrays befindet, oder einen Fehler, wenn dies nicht der Fall ist. Sonst
   
2. Erhöhen Sie den Zeiger und fahren Sie fort.

Auf die eine oder andere Weise wird das Element garantiert gefunden, und die Grenzprüfung wird in diesem Fall nur einmal durchgeführt. Dies ist eine tiefe Idee, aber selbst für einen unerfahrenen Programmierer einfach genug. Wahrscheinlich kann ich nicht über die Relevanz der Arbeit für andere sprechen, aber ich konnte diese Weisheit sofort sowohl im persönlichen als auch im beruflichen Code anwenden. Das TAOCP-Buch ist voll von solchen Perlen (fairerweise gibt es viele seltsame Dinge, wie das Sortieren von Blasen ).

"Suchen, suchen
So lange
Suchen, suchen
Ich wollte nur tanzen. "
- Luther Wandross, Suche (1980)

Tippfehler Nummer 2

Der zweite Tippfehler ist in Band 4A, Kombinatorische Algorithmen, Teil 1. Auf Seite 60 beschreiben wir die Aufgabe, die Leistungen von Comedians in verschiedenen Casinos zu planen. Einige echte Comedians werden als Beispiel angeführt, darunter Lily Tomlin, Strange Al Jankovic und Robin Williams, die noch am Leben waren, als das Buch herauskam. Whip gibt im Index immer vollständige Namen an , daher wird Williams auf Seite 882 als "Williams, Robin McLorim" bezeichnet. Aber sein zweiter Vorname endet mit "n" und nicht mit "m", dh McLoreen.

McLorin ist der Mädchenname seiner Mutter. Sie war die Urenkelin von Anselm Joseph McLorin, dem 34. Gouverneur von Mississippi. An seine Herrschaft erinnerte sich anscheinend nichts Gutes. Aus dem Buch Mississippi: Geschichte :

„Das wichtigste Ereignis während der McLorin-Regierung war, dass die Vereinigten Staaten im Frühjahr 1898 einen Spanienkrieg erklärt haben ... Leider hat der Krieg möglicherweise einigen Regierungsbeamten ermöglicht, Bestechung zu praktizieren. McLorin wurde verschiedene zweifelhafte Praktiken vorgeworfen, darunter Vetternwirtschaft und übermäßiger Einsatz von Begnadigungsbefugnissen. In Zeiten der Nüchternheit warfen Kritiker dem Gouverneur Trunkenheit vor, was er öffentlich zugab. “

Historischer Fehler

Betrachten Sie den traditionellen Multiplikationsalgorithmus aus dem Lehrplan. Wie viel erfordert es Ein-Bit-Multiplikationsoperationen? Angenommen, Sie multiplizieren $$$m$-bit Nummer $$$x$auf $$$n$-bit $$$y$. Multiplizieren Sie zuerst die erste Ziffer $$$x$für jede Ziffer $$$y$abwechselnd. Dann multiplizieren Sie die zweite Ziffer $$$x$für jede Ziffer $$$y$abwechselnd und so weiter, bis Sie alle Zahlen durchgehen $$$x$. Daher erfordert die traditionelle Multiplikation $$$mn$primitive Multiplikationen. Insbesondere die Multiplikation zweier Zahlen mit $$$n$Entladungen erfordern $$$n ^ 2$Einzelbitmultiplikationen.

Das ist schlecht, aber Sie können den Prozess mit der vom sowjetischen Mathematiker Anatoly Alekseevich Karatsuba entwickelten Methode optimieren. Nehmen Sie das an $$$x$und $$$y$- zweistellige Dezimalzahlen; es gibt Zahlen $$$a$, $$$b$, $$$c$, $$$d$so dass $$$x = (ab) _ {10}$und $$$y = (cd) _ {10}$(Die Verallgemeinerung dieses Algorithmus auf große Zahlen erfordert bestimmte Manipulationen; obwohl dies nicht zu schwierig ist, halte ich mich besser an ein einfaches Beispiel, um mich nicht im Detail zu irren). Dann $$$x = 10a + b$, $$$y = 10c + d$, $$$xy = (10a + b) (10c + d)$. Die Multiplikation von Binomen ergibt $$$xy = 100ac + 10ad + 10bc + bd$. Im Moment sind wir noch $$$n ^ 2 = 4$Einzelbitmultiplikation: $$$ac$, $$$ad$, $$$bc$, $$$bd$. Nun addiere und subtrahiere $$$10ac + 10bc$. Nach ein paar Permutationen, die ich dem Leser als Übung überlassen werde, stellt sich heraus $$$xy = 110ac + 11bd + 10 (a - b) (d - c)$- nur drei einstellige Multiplikationen! (Es gibt einige konstante Koeffizienten, die jedoch nur durch Hinzufügen und Verschieben der Ziffern berechnet werden können.)

Bitten Sie nicht um Beweise, aber der Karatsuba-Algorithmus (rekursiv verallgemeinert aus dem obigen Beispiel) verbessert die traditionelle Multiplikationsmethode mit $$$O (n ^ 2)$Operationen vor $$$O (n ^ {(lg 3)})$. Bitte beachten Sie, dass dies eine echte Verbesserung des Algorithmus ist, keine Optimierung für mentale Berechnungen. In der Tat ist der Algorithmus nicht für die Berechnung im Kopf geeignet, da er einen großen Overhead für rekursive Operationen erfordert. Darüber hinaus wird der Effekt erst dann vollständig sichtbar, wenn die Zahlen groß genug sind (glücklicherweise kamen anstelle des Karatsuba-Algorithmus noch schnellere Methoden: Im März 2019 wurde ein Algorithmus veröffentlicht, der nur n log n Multiplikationen erforderte, die Beschleunigung gilt nur für unvorstellbar große Zahlen).

Dieser Algorithmus wird auf Seite 295 des zweiten Bandes, Algorithmen abgeleitet, beschrieben. Dort schreibt Knuth: „Es ist merkwürdig, dass diese Idee erst 1962 entdeckt wurde “, als ein Artikel veröffentlicht wurde, der den Karatsuba-Algorithmus beschreibt. Aber! 1995 veröffentlichte Karatsuba einen Artikel mit dem Titel „Complexity of Computing“, in dem mehrere Dinge gesagt werden: 1) Um 1956 schlug Kolmogorov vor, dass die Multiplikation nicht in weniger als erfolgen kann $$$O (n ^ 2)$Schritte; 2) 1960 nahm Karatsuba an einem Seminar teil, in dem Kolmogorov seine Hypothese n² vorstellte. 3) "Genau in einer Woche" Karatsuba entwickelte den Algorithmus "Teilen und Erobern"; 4) 1962 schrieb und veröffentlichte Kolmogorov im Auftrag von Karatsuba einen Artikel mit einer Beschreibung des Algorithmus. "Ich habe erst von diesem Artikel erfahren, nachdem er nachgedruckt wurde."

Der Fehler ist also, dass 1960 anstelle von 1962 angegeben werden sollte . Das ist alles.

Analyse

Die Suche nach Fehlern erforderte nicht viel Geschick.

1. Der erste Fehler war so häufig wie möglich und befand sich an einer relativ prominenten Stelle (am Anfang des Kapitels). Jeder Idiot würde sie finden; Ich habe mich gerade als dieser Idiot herausgestellt.
   
2. Einen zweiten Tippfehler zu finden, erforderte Glück und Fleiß, aber keine Geschicklichkeit. Der Index für "Williams" befindet sich auf der vorletzten Seite des Bandes, einem ziemlich wichtigen Teil des Buches. Ich habe gerade den Indexindex durchgeblättert (es ist nicht so erbärmlich, wie es scheint, weil Ostereier in Knuths Indizes versteckt sind. Zum Beispiel gibt es Einträge auf Arabisch und Hebräisch, und beide verweisen auf Seite 66. Aber diese Seite erwähnt auch nicht Sprachen, stattdessen bezieht es sich auf „Sprachen, die von rechts nach links gelesen werden“). Und meine Aufmerksamkeit wurde vom zweiten Vornamen angezogen. Da ich normalerweise Wikipedia lese, habe ich Robin Williams überprüft und eine Diskrepanz festgestellt.
   
3. Ich möchte sagen, dass ich viel recherchiert habe, um einen historischen Fehler zu finden, aber eigentlich nur die Wikipedia-Seite über den Karatsuba-Algorithmus angesehen habe . In den ersten Zeilen heißt es: „Der Karatsuba-Algorithmus ist ein Algorithmus zur schnellen Multiplikation. 1960 von Anatoly Karatsuba entdeckt und 1962 veröffentlicht. " Danach blieb es nur noch zweimal zwei zu folden.

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

Finanzielle Fakten:

• Insgesamt besteht mein Beitrag zu TAOCP nur aus drei Zeichen: eines, das s hinzufügt, m durch n und 2 durch 0 ersetzt . Bei einem Preis von 2,56 USD sind dies ziemlich lukrative Symbole. Wenn Sie diese Art von Geld erhalten würden, würde ein Artikel mit 1000 Wörtern (durchschnittlich jeweils vier Zeichen) Ihnen zehn Stücke bringen.
  
• Mit drei hexadezimalen Dollars teile ich zusammen mit 29 anderen Bürgern den 69. Platz in der Liste der reichsten Einleger der Bank of San Serriff (Stand 1. Mai 2019).

Andere Diskussionen über Knut-Checks

• So erhalten Sie einen Scheck von Knut
  
  Allgemeine Richtlinien zum Auffinden von Fehlern in Knuts Büchern. Meistens technische Fehler, die ich nicht habe. Es gibt einen Vorschlag, den ich ernst genommen habe:
  
  

  Warten Sie besser, bis Sie eine Reihe von Fehlern zum Senden gesammelt haben. Durch die Kombination mehrerer realer, aber nicht sehr wertvoller Fehler erhöhen Sie die Wahrscheinlichkeit, dass einer von ihnen tatsächlich als Fehler oder Ratschlag angesehen wird. Wenn Sie Fehler einzeln senden, kann jeder einzeln abgelehnt werden.

  
  Ich wollte keine unsinnigen Tippfehler senden, aber ich habe den Rat befolgt und nur dann einen Brief gesendet, wenn ich einen historischen Fehler gefunden habe, der ernst genug schien.
  
• Ashutosh Mehras Schecks
  
  Ashutosh Mehra ist der drittreichste Beitrag zu San Serriff mit einem unglaublichen Vermögen von 0x $ 207, f0 in BoSS.
  
• Überprüfen Sie den echten TeX-Code auf einige nicht funktionierende Fehler
  
• Verschiedenes: # 1 # 2 # 3 # 4 # 5 # 6