{"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\/nl\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Ik heb van Knuth een cheque ontvangen voor 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0is een wetenschapper op het gebied van informatica die zo veel geeft om de nauwkeurigheid van zijn boeken dat hij aanbiedt \u00e9\u00e9n hexadecimaal dollar<\/b> ($2,56, 0x$1,00) voor elke gevonden 'fout', waarbij een fout alles is wat 'technisch, historisch, typografisch of politiek onjuist' is. Ik wilde heel graag een cheque van Knuth krijgen, dus besloot ik fouten te zoeken in zijn uitstekende werk \"The Art of Computer Programming\"<\/b> (TAOCP). Ik vond er drie. Getrouwd aan zijn woord, stuurde Knuth een cheque ter waarde van 0x$3,00<\/b>.<\/p>\n

\"Ik
\n
\nZoals je ziet, is dit geen echte cheque. Vroeger stuurde Knuth echte cheques, maar hij is daar in 2008 mee gestopt vanwege ongekend bedrog<\/a><\/noindex>. Nu verstuurt hij 'persoonlijke deposito certificaten' bij de San Serif bank<\/a><\/noindex> (BoSS). Hij zegt dat hij bereid is echte geld te sturen als dat nodig is, maar het lijkt te veel gedoe.
\n<\/a><\/noindex>
\nIk vond twee typfouten en \u00e9\u00e9n historische fout. Ik zal ze opsommen in volgorde van afnemende trivialiteit.<\/p>\n

Typfout #1<\/h1>\n

\nDe eerste typfout staat op pagina 392 van deel drie \"Sorteren en zoeken\", achtste regel van onder: \"Na een mislukte zoekopdracht is het soms (sometime) wenselijk om een nieuwe invoer in de tabel te plaatsen, die K<\/i>; de methode die dit doet, wordt het zoek- en invoegalgoritme genoemd. De fout is dat in plaats van sometime<\/i><\/b> het moet zijn sometimes<\/i><\/b>.<\/p>\n

Natuurlijk is er niets verrassends aan zo'n fout. In dit artikel zijn ongetwijfeld een paar typfouten te vinden (geen beloningen voor het vinden ervan). Wat eigenlijk verrassend is, is dat het zo lang niet opgemerkt is. Pagina 392 ligt niet diep verborgen in het wiskundedeel, dit is de allereerste pagina<\/b> van hoofdstuk zes \"Zoeken\"! Misschien wel een van de meest gelezen secties van het boek. In theorie zouden er daar het minste typfouten moeten zijn, maar nee.<\/p>\n

Overigens, als je ooit hebt gedacht om TAOCP te lezen, probeer het. Veel mensen zullen zeggen dat het een naslagwerk<\/b>, dat niet bedoeld is om rechtstreekse leeservaring te bieden, maar dat is onjuist. De auteur heeft een duidelijke opvatting en een unieke stijl. Het enige dat de leesbaarheid belemmert, is de complexiteit van de wiskunde. Er is echter een eenvoudige oplossing: lees totdat je bij de wiskunde komt die je niet begrijpt, sla die over en ga naar de volgende sectie die je kan begrijpen. Op deze manier sla ik minstens 80% van het boek over, maar de resterende 20% is prachtig!<\/p>\n

Er wordt ook gezegd dat TAOCP irrelevant is<\/b>, verouderd of op een andere manier niet toepasselijk voor 'echte programmering'. Dit is ook niet waar. Bijvoorbeeld, in het eerste gedeelte na de inleiding wordt het zoeken van een element in een niet-gesorteerde array behandeld. Het eenvoudigste algoritme is bekend bij alle programmeurs. Start de pointer aan het begin van de array, voer vervolgens de volgende stappen in een lus uit:<\/p>\n

    \n
  1. Controleer of het huidige element het gewenste is. Als dat zo is, geven we het terug; zo niet,\n<\/li>\n
  2. Controleer of de pointer buiten de array ligt. Als dat zo is, geven we een foutmelding; zo niet,\n<\/li>\n
  3. Verhoog de pointer en ga verder.<\/li>\n<\/ol>\n

    \nLaten we nu overwegen: hoeveel grenscontroles vereist dit algoritme gemiddeld? In het slechtste geval, wanneer de array het element niet bevat, is er voor elk element in de lijst \u00e9\u00e9n controle nodig, en gemiddeld is dit ongeveer \"Ik. Een slimmer zoekalgoritme kan maar \u00e9\u00e9n grenscontrole vereisen. Hang het gewenste element aan het einde van de array, start vervolgens de pointer aan het begin van de array en voer de volgende stappen in een lus uit:<\/p>\n

      \n
    1. Controleer of het huidige element het gewenste is. Als dat zo is, geven we het antwoord terug als de pointer binnen de array ligt, of een foutmelding als dat niet het geval is. Zo niet,\n<\/li>\n
    2. Verhoog de pointer en ga verder.<\/li>\n<\/ol>\n

      \nHoe dan ook, het element zal gegarandeerd worden gevonden, en de grenscontrole wordt maar \u00e9\u00e9n keer uitgevoerd als dat gebeurt. Dit is een diep idee, maar het is eenvoudig genoeg, zelfs voor een beginnende programmeur. Ik kan misschien niet over de relevantie van dit werk voor anderen spreken, maar ik slaagde er meteen in om deze wijsheid toe te passen, zowel in persoonlijke als professionele code. Het boek TAOCP zit vol met zulke parels (om eerlijk te zijn, er zijn ook veel vreemde dingen, zoals bubbel sortering<\/a><\/noindex>).<\/p>\n

      \"Zoeken, zoeken
      \nZo lang
      \nZoeken, zoeken
      \nIk wilde gewoon dansen\"<\/i>
      \n\u2014 Luther Vandross, \"Zoeken\" (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Typfout #2<\/h1>\n

      \nDe tweede fout is in deel 4A, \"Combinatorische algoritmen\", deel 1. Op pagina 60 wordt een probleem beschreven over het plannen van optredens van komieken in verschillende casino's. Ter illustratie worden verschillende echte komieken genoemd, waaronder Lily Tomlin, Weird Al Yankovic en Robin Williams, die nog in leven was toen het boek uitkwam. Knuth vermeldt altijd volledige namen in de index, dus Williams wordt op pagina 882 genoemd als \"Williams, Robin McLaurin\". Maar zijn tweede naam eindigt op \"n\" en niet op \"m\", dat wil zeggen McLaurin.<\/p>\n

      McLaurin is de meisjesnaam van zijn moeder. Zij was de achterkleindochter van Anselm Joseph McLaurin, de 34ste gouverneur van Mississippi. Zijn regeerperiode staat duidelijk niet bekend om iets goeds. Uit het boek \"Mississippi: een geschiedenis\"<\/a><\/noindex>:<\/p>\n

      \"Het belangrijkste evenement tijdens de administratie van McLaurin was de verklaring van de Verenigde Staten van oorlog aan Spanje in het voorjaar van 1898... Helaas gaf de oorlog mogelijk sommige overheidsofficials de kans om corruptie te praktiseren. McLaurin werd beschuldigd van verschillende dubieuze praktijken, waaronder nepotisme en buitensporig gebruik van gratiebevoegdheden. In de tijd van de temperancebeweging beschuldigden critici de gouverneur van dronkenschap, wat hij publiekelijk erkende.\"<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Historische fout<\/h1>\n

      \nBinnen kun je wat informatie zien met behulp van de functie traditioneel vermenigvuldigingsalgoritme<\/b> uit het schoolcurriculum. Hoeveel eencijferige vermenigvuldigingen vereist het? Laten we veronderstellen dat je \"Ik-cijfergetal \"Ik en een werkende opdracht krijgen. \"Ik-cijfer \"Ik. Eerst vermenigvuldig je de eerste cijfer \"Ik met elk cijfer \"Ik om beurten. Vervolgens vermenigvuldig je het tweede cijfer \"Ik met elk cijfer \"Ik om beurten en ga zo door, totdat je alle cijfers hebt doorlopen \"Ik. Zo vereist traditionele vermenigvuldiging \"Ik primitieve vermenigvuldigingen. In het bijzonder vereist het vermenigvuldigen van twee getallen van \"Ik cijfers \"Ik eencijferige vermenigvuldigingen.<\/p>\n

      Dat is slecht, maar het proces kan worden geoptimaliseerd met behulp van een methode ontwikkeld door de Sovjet-wiskundige Anatoli Alexejevitsj Karatsuba. Laten we veronderstellen dat \"Ik en \"Ik\u00a0-tweecijferige decimale getallen zijn; dat wil zeggen, er bestaan getallen \"Ik, \"Ik, \"Ik, \"Ik zodat \"Ik en \"Ik (de generalisatie van dit algoritme naar grotere cijfers vereist bepaalde manipulaties; hoewel het niet al te moeilijk is, zal ik me voor de details liever aan een eenvoudig voorbeeld houden). Dan \"Ik, \"Ik, \"Ik. Vermenigvuldigen van tweetermen geeft \"Ik. Tot nu toe hebben we nog steeds \"Ik eencijferige vermenigvuldigingen: \"Ik, \"Ik, \"Ik, \"Ik. Laten we nu optellen en aftrekken \"IkNa afloop van enkele herschikkingen, die ik als een oefening voor de lezer zal achterlaten, krijgen we \"Ik\u00a0\u2014 in totaal drie eencijferige vermenigvuldigingen! (Er zijn enkele constante co\u00ebffici\u00ebnten, maar die kunnen alleen worden berekend door op te tellen en cijfers te verschuiven).<\/p>\n

      Vraag niet om bewijs, maar de Karatsuba-algoritme<\/b> (recursief gegeneraliseerd uit het bovenstaande voorbeeld) verbetert de traditionele vermenigvuldigingsmethode van \"Ik operaties tot \"Ik. Let op, dit is een echte verbetering van het algoritme, geen optimalisatie voor mentale berekeningen. Inderdaad, het algoritme is niet geschikt voor mentale berekeningen, omdat het hoge overheadkosten voor recursieve bewerkingen vereist. Bovendien komt het effect pas volledig tot zijn recht wanneer de getallen groot genoeg worden (gelukkig zijn er nog snellere methoden gekomen na het Karatsuba-algoritme: in maart 2019 werd er een algoritme gepubliceerd dat slechts vereist n log n<\/i><\/a><\/noindex> vermenigvuldigingen; de versnelling is alleen van toepassing op onvoorstelbaar grote getallen).<\/p>\n

      Dit algoritme wordt beschreven op pagina 295 van het tweede deel van 'Geavanceerde algoritmen'. Daar schrijft Knuth: 'Het is opmerkelijk dat dit idee pas is ontdekt in 1962<\/b> jaar', toen er een artikel werd gepubliceerd dat het Karatsuba-algoritme beschreef. Maar! In 1995 publiceerde Karatsuba het artikel 'Complexiteit van berekeningen', waarin hij enkele dingen zegt: 1) rond 1956 veronderstelde Kolmogorov dat vermenigvuldigen niet kan worden gedaan in minder dan \"Ik stappen; 2) in 1960<\/b> jaar was Karatsuba aanwezig op een seminar waar Kolmogorov zijn hypothese n\u00b2 uitlegde. 3) 'Precies een week later' ontwikkelde Karatsuba het 'verdeel en heers'-algoritme; 4) in 1962 schreef en publiceerde Kolmogorov een artikel namens Karatsuba<\/i> met een beschrijving van het algoritme. 'Ik hoorde pas over dit artikel nadat het was herdrukt.'<\/p>\n

      Dus de fout ligt erin dat in plaats van 1962<\/i> moet het 1960<\/i> jaar worden opgegeven. Dat is alles.<\/p>\n

      Analyse<\/h1>\n

      \nHet zoeken naar fouten vereiste geen bijzondere bekwaamheid.<\/b><\/p>\n

        \n
      1. De eerste fout was zo banaal als maar kan en bevond zich op een redelijk zichtbare plek (het begin van het hoofdstuk). Elke idioot zou het gevonden hebben; ik was gewoon die idioot.\n<\/li>\n
      2. Het vinden van de tweede drukfout vereiste geluk en toewijding, maar geen vaardigheid. De index voor 'Williams' staat op de voorlaatste pagina van de bundel, een vrij opmerkelijk deel van het boek. Ik was net de index aan het doorbladeren (dat is niet zo erg als het lijkt, omdat er in de indexen van Knuth verborgen paaseieren zitten. Bijvoorbeeld, er zijn vermeldingen in het Arabisch en Hebreeuws, en beide verwijzen naar pagina 66. Maar op die pagina komen geen van beide talen voor; in plaats daarvan wordt verwezen naar 'talen die van rechts naar links worden gelezen'). En mijn aandacht werd getrokken door de tweede naam. Aangezien ik meestal Wikipedia lees, controleerde ik Robin Williams en merkte ik een discrepantie op.\n<\/li>\n
      3. Ik wou dat ik kon zeggen dat ik serieus onderzoek had gedaan om een historische fout te vinden, maar eigenlijk heb ik gewoon gekeken naar de Wikipedia-pagina over het Karatsuba-algoritme<\/a><\/noindex>. In de eerste zin staat: 'Het Karatsuba-algoritme is een snel vermenigvuldigingsalgoritme. Ontdekt door Anatoli Karatsuba in 1960 en gepubliceerd in 1962.' Daarna was het nog maar een kwestie van twee keer twee optellen.<\/li>\n<\/ol>\n

        \nIn de toekomst zou ik graag een meer significante fout willen vinden, vooral in de code van Knuth. Ik zou ook graag een bug vinden in de eerste bundel 'Fundamentele algoritmen'. Misschien had ik dat gevonden, maar om de een of andere reden heeft de plaatselijke bibliotheek alleen de bundels 2, 3 en 4A.<\/p>\n

        Financi\u00eble feiten:<\/b><\/p>\n