{"id":34164,"date":"2019-10-31T21:56:44","date_gmt":"2019-10-31T18:56:44","guid":{"rendered":"https:\/\/prohoster.info\/blog\/ya-poluchil-ot-knuta-chek-na-0x-3-00\/"},"modified":"2019-10-31T21:56:44","modified_gmt":"2019-10-31T18:56:44","slug":"ya-poluchil-ot-knuta-chek-na-0x-3-00","status":"publish","type":"post","link":"https:\/\/prohoster.info\/de\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Ich habe von Knut einen Scheck \u00fcber 0x$3,00 erhalten","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 ein Wissenschaftler im Bereich Informatik, der so sehr auf die Richtigkeit seiner B\u00fccher achtet, dass er einen hexadezimalen Dollar<\/b> ($2,56, 0x$1,00) f\u00fcr jeden gefundenen \u201eFehler\u201c anbietet, wobei ein Fehler alles z\u00e4hlt, was \u201etechnisch, historisch, typografisch oder politisch inkorrekt\u201c ist. Ich wollte unbedingt einen Scheck von Knuth bekommen, also beschloss ich, nach Fehlern in seinem herausragenden Werk zu suchen \u201eDie Kunst des Programmierens\u201c<\/b> (TAOCP). Mir gelang es, drei zu finden. Treu der Wortwahl schickte Knuth einen Scheck \u00fcber 0x$3,00<\/b>.<\/p>\n

\"Ich
\n
\nWie Sie sehen, ist das kein echter Scheck. Fr\u00fcher verschickte Knuth echte Schecks, h\u00f6rte aber 2008 aufgrund von ungebremstem Betrug<\/a><\/noindex>. Jetzt versendet er \u201epers\u00f6nliche Einzahlungszertifikate\u201c bei der Bank von San Serriffe<\/a><\/noindex> (BoSS). Er sagt, dass er im Bedarfsfall echtes Geld verschicken kann, aber das scheint zu umst\u00e4ndlich zu sein.
\n<\/a><\/noindex>
\nIch fand zwei Tippfehler und einen historischen Fehler. Ich werde sie in absteigender Reihenfolge der Trivialit\u00e4t auflisten.<\/p>\n

Tippfehler Nr. 1<\/h1>\n

\nDer erste Tippfehler \u2014 auf Seite 392 des dritten Bandes \u201eSortieren und Suchen\u201c, achte Zeile von unten: \u201eNach einem gescheiterten Suchvorgang ist es manchmal (sometime) w\u00fcnschenswert, einen neuen Eintrag in die Tabelle einzuf\u00fcgen, der K<\/i>; die Methode, die dies tut, wird als Such- und Einf\u00fcgemethode bezeichnet. Der Fehler besteht darin, dass anstelle von sometime<\/i><\/b> sollte sometimes<\/i><\/b>.<\/p>\n

Nat\u00fcrlich ist an einem solchen Fehler nichts \u00dcberraschendes. In diesem Artikel wird es sicherlich einige Tippfehler geben (keine Belohnungen f\u00fcr deren Auffindung). Was wirklich \u00fcberraschend ist, ist, dass es so lange \u00fcbersehen wurde. Seite 392 ist nicht tief im Mathematikbereich vergraben, es ist die erste Seite<\/b> des sechsten Kapitels \u201eSuchen\u201c! Vielleicht einer der am h\u00e4ufigsten gelesenen Abschnitte des Buches. Eigentlich sollte es dort am wenigsten Tippfehler geben, aber dem ist nicht so.<\/p>\n

\u00dcbrigens, wenn Sie jemals dar\u00fcber nachgedacht haben, TAOCP zu lesen, probieren Sie es aus. Viele werden sagen, dass es ein Nachschlagewerk<\/b>, 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\u00e4nkt, ist die Komplexit\u00e4t der Mathematik. Es gibt jedoch eine einfache L\u00f6sung: Lesen Sie weiter, bis Sie zur Mathematik gelangen, die Sie nicht verstehen, \u00fcberspringen Sie sie und gehen Sie zum n\u00e4chsten Abschnitt, den Sie verstehen k\u00f6nnen. Auf diese Weise lasse ich mindestens 80% des Buches aus, aber die restlichen 20% sind gro\u00dfartig!<\/p>\n

Es wird auch gesagt, dass TAOCP nicht relevant ist<\/b>, veraltet oder auf andere Weise nicht auf \u201ereales Programmieren\u201c 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\u00fchren Sie dann die folgenden Schritte in einer Schleife aus:<\/p>\n

    \n
  1. \u00dcberpr\u00fcfen Sie, ob das aktuelle Element das gew\u00fcnschte ist. Wenn ja, geben Sie es zur\u00fcck; andernfalls\n<\/li>\n
  2. \u00dcberpr\u00fcfen Sie, ob der Zeiger au\u00dferhalb des Arrays liegt. Wenn ja, geben Sie einen Fehler zur\u00fcck; andernfalls\n<\/li>\n
  3. Erh\u00f6hen Sie den Zeiger und fahren Sie fort.<\/li>\n<\/ol>\n

    \nNun betrachten wir: Wie viele Grenzkontrollen erfordert dieser Algorithmus im Durchschnitt? Im schlimmsten Fall, wenn das Array kein Element enth\u00e4lt, ist f\u00fcr jedes Element in der Liste eine \u00dcberpr\u00fcfung erforderlich, und im Durchschnitt wird es etwa so aussehen \"Ich. Ein intelligenterer Suchalgorithmus k\u00f6nnte mit nur einer Grenzkontrolle auskommen. F\u00fcgen Sie das ben\u00f6tigte Element ans Ende des Arrays an, setzen Sie den Zeiger am Anfang des Arrays und f\u00fchren Sie dann die folgenden Schritte in einer Schleife aus:<\/p>\n

      \n
    1. \u00dcberpr\u00fcfen Sie, ob das aktuelle Element das gew\u00fcnschte ist. Wenn ja, geben Sie die Antwort zur\u00fcck, wenn der Zeiger innerhalb des Arrays liegt, oder einen Fehler, wenn dies nicht der Fall ist. Andernfalls\n<\/li>\n
    2. Erh\u00f6hen Sie den Zeiger und fahren Sie fort.<\/li>\n<\/ol>\n

      \nSo oder so wird das Element garantiert gefunden, und die Grenzkontrolle erfolgt nur einmal, wenn dies der Fall ist. Das ist eine tiefgr\u00fcndige Idee, aber sie ist einfach genug, selbst f\u00fcr einen Anf\u00e4nger. Ich kann wahrscheinlich nicht \u00fcber die Relevanz dieser Arbeit f\u00fcr andere sprechen, aber ich konnte diese Weisheit sofort in meinem pers\u00f6nlichen sowie professionellen Code anwenden. Das Buch TAOCP ist voll von solchen Perlen (um der Gerechtigkeit willen, dort sind auch viele merkw\u00fcrdige Dinge, wie Bubble Sort<\/a><\/noindex>).<\/p>\n

      \u201eSuche, Suche
      \nSo lange
      \nSuche, Suche
      \nIch wollte einfach nur tanzen\u201c<\/i>
      \n\u2014 Luther Vandross, \u201eSuche\u201c (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Tippfehler Nr. 2<\/h1>\n

      \nDer 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\u00f6ffentlicht wurde. Knut f\u00fchrt im Register immer die vollen Namen an, weshalb Williams auf Seite 882 als \"Williams, Robin Mac-Lorin\" erw\u00e4hnt wird. Aber sein zweiter Vorname endet mit einem \"n\" und nicht mit einem \"m\", also Mac-Lorin.<\/p>\n

      Mac-Lorin ist der M\u00e4dchennamen 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 \"Mississippi: Geschichte\"<\/a><\/noindex>:<\/p>\n

      \"Das wichtigste Ereignis w\u00e4hrend der Amtszeit von Mac-Lorin war die Kriegserkl\u00e4rung der Vereinigten Staaten an Spanien im Fr\u00fchling 1898... Leider bot der Krieg m\u00f6glicherweise einigen Beamten die Gelegenheit, Bestechung zu praktizieren. Mac-Lorin wurde verschiedener fragw\u00fcrdiger Praktiken beschuldigt, einschlie\u00dflich Nepotismus und \u00fcberm\u00e4\u00dfiger Nutzung seiner Begnadigungsbefugnisse. In der \u00c4ra der Abstinenz beschuldigten die Kritiker den Gouverneur des Alkoholmissbrauchs, was er \u00f6ffentlich zugab.\"<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Historischer Fehler<\/h1>\n

      \nBetrachten wir traditioneller Multiplikationsalgorithmus<\/b> aus dem Schulprogramm. Wie viele einstellige Multiplikationen ben\u00f6tigt er? Angenommen, Sie multiplizieren \"Ich-stellige Zahl \"Ich auf \"Ich-stellige \"Ich. Zuerst multiplizieren Sie die erste Ziffer \"Ich mit jeder Ziffer \"Ich der Reihe nach. Dann multiplizieren Sie die zweite Ziffer \"Ich mit jeder Ziffer \"Ich der Reihe nach und so weiter, bis Sie alle Ziffern durchlaufen haben \"Ich. So erfordert die traditionelle Multiplikation \"Ich primitive Multiplikationen. Insbesondere erfordert die Multiplikation von zwei Zahlen nach \"Ich -stellen \"Ich einstellige Multiplikationen.<\/p>\n

      Das ist schlecht, aber der Prozess kann durch eine Methode optimiert werden, die vom sowjetischen Mathematiker Anatoli Alexejewitsch Karazuba entwickelt wurde. Angenommen, \"Ich und \"Ich\u00a0sind zweistellige Dezimalzahlen; das hei\u00dft, es gibt Zahlen \"Ich, \"Ich, \"Ich, \"Ich so dass \"Ich und \"Ich (die Verallgemeinerung dieses Algorithmus auf gr\u00f6\u00dfere 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 \"Ich, \"Ich, \"Ich. Die Multiplikation von Binomen ergibt \"Ich. Bis zu diesem Zeitpunkt haben wir immer noch \"Ich einstellige Multiplikationen: \"Ich, \"Ich, \"Ich, \"Ich. Jetzt addieren und subtrahieren wir \"Ich. Nach mehreren Umstellungen, die ich als \u00dcbung f\u00fcr den Leser lasse, ergibt sich \"Ich\u00a0\u2014 insgesamt drei einstellige Multiplikationen! (Es gibt einige konstante Koeffizienten, aber die k\u00f6nnen nur durch Addition und Verschieben der Stellen berechnet werden).<\/p>\n

      Bitte verlangen Sie keinen Beweis, aber der Karatsuba-Algorithmus<\/b> (rekursiv verallgemeinert aus dem obigen Beispiel) verbessert die traditionelle Multiplikationsmethode von \"Ich Operationen auf \"Ich. Beachten Sie, dass dies eine echte Verbesserung des Algorithmus ist und keine Optimierung f\u00fcr das Rechnen im Kopf. Tats\u00e4chlich ist der Algorithmus nicht f\u00fcr das Kopfrechnen geeignet, da er gro\u00dfe Overheads f\u00fcr die rekursiven Operationen erfordert. Au\u00dferdem wird der Effekt nicht voll zur Geltung kommen, solange die Zahlen nicht gro\u00df genug sind (zum Gl\u00fcck sind anstelle des Karatsuba-Algorithmus noch schnellere Methoden entstanden: Im M\u00e4rz 2019 wurde ein Algorithmus ver\u00f6ffentlicht, der nur n log n<\/i><\/a><\/noindex> Multiplikationen erfordert; die Beschleunigung gilt nur f\u00fcr unvorstellbar gro\u00dfe Zahlen).<\/p>\n

      Dieser Algorithmus ist auf Seite 295 des zweiten Bandes der \u201eBerechneten Algorithmen\u201c beschrieben. Dort schreibt Knuth: \u201eEs ist interessant, dass diese Idee erst im 1962<\/b> Jahr\u201c entdeckt wurde, als ein Artikel ver\u00f6ffentlicht wurde, der den Karatsuba-Algorithmus beschreibt. Aber! Im Jahr 1995 ver\u00f6ffentlichte Karatsuba einen Artikel mit dem Titel \u201eDie Komplexit\u00e4t der Berechnungen\u201c, in dem er einige Dinge sagt: 1) um 1956 vermutete Kolmogorov, dass Multiplikation nicht unter \"Ich Schritten durchgef\u00fchrt werden kann; 2) Im 1960<\/b> Jahr nahm Karatsuba an einem Seminar teil, in dem Kolmogorov seine Hypothese n\u00b2 darlegte. 3) \u201eGenau eine Woche nachher\u201c entwickelte Karatsuba den Algorithmus \u201eTeile und herrsche\u201c; 4) 1962 schrieb und ver\u00f6ffentlichte Kolmogorov einen Artikel im Namen von Karatsuba<\/i> mit einer Beschreibung des Algorithmus. \u201eIch erfuhr erst davon, nachdem er nachgedruckt wurde\u201c.<\/p>\n

      Somit liegt der Fehler darin, dass statt 1962<\/i> angegeben werden sollte 1960<\/i> Jahr. Das ist alles.<\/p>\n

      Analyse<\/h1>\n

      \nDie Fehlersuche erforderte kein besonderes K\u00f6nnen.<\/b><\/p>\n

        \n
      1. 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\u00e4tte ihn gefunden; nur ich war der Idiot.\n<\/li>\n
      2. Die Suche nach dem zweiten Druckfehler erforderte Gl\u00fcck und Flei\u00df, aber kein K\u00f6nnen. Das Index f\u00fcr \u201eWilliams\u201c befindet sich auf der vorletzten Seite des Bands, ein recht auff\u00e4lliger Teil des Buches. Ich bl\u00e4tterte gerade im Index (es ist nicht so schlimm, wie es scheint, denn in Knuths Indizes sind Ostereier versteckt. Zum Beispiel gibt es Eintr\u00e4ge auf Arabisch und Hebr\u00e4isch, die beide auf Seite 66 verweisen. Aber auf dieser Seite wird keine der Sprachen erw\u00e4hnt; stattdessen geht es um \u201eSprachen, die von rechts nach links gelesen werden\u201c). Und meine Aufmerksamkeit zog der zweite Name an. Da ich normalerweise Wikipedia lese, habe ich Robin Williams \u00fcberpr\u00fcft und eine Unstimmigkeit festgestellt.\n<\/li>\n
      3. Ich w\u00fcnschte, ich k\u00f6nnte sagen, dass ich eine ernsthafte Forschung betrieben habe, um den historischen Fehler zu finden, aber tats\u00e4chlich habe ich einfach nur geschaut auf der Wikipedia-Seite zum Karatsuba-Algorithmus<\/a><\/noindex>. In den ersten Zeilen steht: \u201eDer Karatsuba-Algorithmus ist ein Algorithmus zum schnellen Multiplizieren. Entdeckt von Anatolij Karatsuba im Jahr 1960 und ver\u00f6ffentlicht im Jahr 1962\u201c. Danach blieb es nur noch, zwei und zwei zusammenzuz\u00e4hlen.<\/li>\n<\/ol>\n

        \nIn Zukunft m\u00f6chte ich einen erheblicheren Fehler finden, insbesondere im Code von Knuth. Ich w\u00fcrde auch gerne einen Bug im ersten Band \u201eFundamentale Algorithmen\u201c finden. Vielleicht w\u00fcrde ich einen finden, aber in der \u00f6rtlichen Bibliothek gibt es aus irgendeinem Grund nur die B\u00e4nde 2, 3 und 4A.<\/p>\n

        Finanzielle Fakten:<\/b><\/p>\n