Donald Knuth — vedec v oblasti informatiky, ktorý sa tak veľmi stará o správnosť svojich kníh, že ponúka jeden šestnástkový dolár ($2,56, 0x$1,00) za akúkoľvek nájdenú „chybu“, kde chybou sa považuje všetko, čo je „technicky, historicky, typograficky alebo politicky nesprávne“. Veľmi som chcel dostať šek od Knuta, preto som sa rozhodol hľadať chyby v jeho výnimočnom diele „Umění programování“ (TAOCP). Podarilo sa mi nájsť tri. Verne slovu, Knuth poslal šek na 0x$3,00.
Ako vidíte, nejde o skutočný šek. Kedysi posielal Knuth skutočné šeky, ale prestal s tým v roku 2008 z dôvodu . Teraz rozosiela „osobné depozitné certifikáty“ v (BoSS). Hovorí, že je pripravený poslať skutočné peniaze, ak to bude potrebné, ale zdá sa, že je to príliš zložité.
Našiel som dve preklepy a jednu historickú chybu. Vymením ich v poradí klesajúcej triviálnosti.
Preklep č. 1
Prvý preklep — na strane 392 tretieho zväzku „Zoradenie a vyhľadávanie“, ôsmy riadok zospodu: „Po neúspešnom hľadaní je niekedy (sometime) žiaduce vložiť do tabuľky nový záznam obsahujúci K; metóda, ktorá to robí, sa nazýva algoritmus hľadania a vloženia. Chyba spočíva v tom, že namiesto sometime má byť sometimes.
Samozrejme, v takej chybe nie je nič prekvapujúce. Iba v tomto článku určite nájdete niekoľko preklepov (žiadne ocenenie za ich nájdenie). Čo je však naozaj prekvapujúce, je to, že si ich tak dlho nikto nevšimol. Strana 392 nie je hlboko zakrytá v oddelení matematiky, je to najprvá strana šiestich kapitol „Vyhľadávanie“! Možno jeden z najčítanejších oddielov knihy. Teoreticky by tam malo byť najmenej preklepov, ale nie.
Mimochodom, ak ste niekedy rozmýšľali nad čítaním TAOCP, skúste to. Mnohí povedia, že ide o príručku, ktorá nie je určená na priame čítanie, ale to nie je pravda. Autor má jasný názor a svojský štýl. Jediné, čo bráni čítateľnosti, je zložitost matematiky. Existuje však jednoduché riešenie: čítajte, kým nedôjdete k matematike, ktorú nerozumiete, preskočte ju a otvoríte nasledujúcu časť, ktorú môžete pochopiť. Takto preskakujem aspoň 80 % knihy, ale ostatných 20 % je nádherných!
Taktiež sa hovorí, že TAOCP nerelevantná, zastaraná alebo inak nepoužiteľná na „reálne programovanie“. To je tiež nepravda. Napríklad v prvej časti po úvode sa zaoberá vyhľadávaním prvku v nesotrdenom poli. Najjednoduchší algoritmus je známy všetkým programátorom. Spustite ukazovateľ na začiatku poľa, potom vykonajte nasledujúce kroky v cykle:
- Skontrolujte, či je aktuálny prvok žiadaný. Ak áno, vráťte ho; v opačnom prípade
- Skontrolujte, či je ukazovateľ mimo poľa. Ak áno, vráťte chybu; v opačnom prípade
- Zvýšte ukazovateľ a pokračujte.
Teraz zvážte: koľko kontrol hraníc si tento algoritmus vyžaduje, v priemere? V najhoršom prípade, keď pole neobsahuje prvok, si pre každý prvok v zozname vyžaduje jednu kontrolu, a v priemere to bude niečo ako 
. Inteligentnejší algoritmus vyhľadávania môže zvládnuť len jednu kontrolu hraníc. Pripojte požadovaný prvok na koniec poľa, potom spustite ukazovateľ na začiatku poľa a vykonajte nasledujúce kroky v cykle:
- Skontrolujte, či je aktuálny prvok žiadaný. Ak áno, vráťte odpoveď, ak je ukazovateľ v rámci poľa, alebo chybu, ak nie je. V opačnom prípade
- Zvýšte ukazovateľ a pokračujte.
Tak či onak, prvok bude zaručene nájdený a kontrola hraníc sa vykoná len raz, keď k tomu dôjde. Je to hlboká myšlienka, ale dosť jednoduchá aj pre začiatočníka programátora. Asi nemôžem hovoriť o aktuálnosti tejto práce pre iných, ale hneď som bol schopný aplikovať túto múdrosť ako vo svojom osobnom, tak aj v profesionálnom kóde. Kniha TAOCP je plná takýchto perál (na spravodlivosť, sú tam aj mnohé podivné veci, ako napríklad ).
„Hľadanie, hľadanie
Tak dlho
Hľadanie, hľadanie
I simply wanted to dance"
— Luther Vandross, „Hľadanie“ (1980)
Tisková chyba č. 2
Druhá chyba sa nachádza vo zväzku 4A, „Kombinatorické algoritmy“, časť 1. Na strane 60 je opísaná úloha plánovania vystúpení komikov v rôznych kasínach. Ako príklad sú uvedení niektorí skutoční komici, vrátane Lily Tomlin, Weird Al Yankovic a Robin Williams, ktorý bol ešte nažive, keď kniha vyšla. Knuth vždy uvádza v indexe celé mená, takže Williams je uvedený na strane 882 ako „Williams, Robin Mac-Lorin“. No jeho druhé meno sa končí na „n“, a nie na „m“, teda Mac-Lorin.
Mac-Lorin je dievčenské priezvisko jeho matky. Bola pravnučkou Anselma Jozefa Mac-Lorina, 34. guvernéra Mississippi. Jeho pôsobenie, zdá sa, nebolo zapamätané ničím dobrým. Z knihy :
„Najdôležitejšou udalosťou počas administratívy Mac-Lorina bolo vyhlásenie USA vojny Španielsku na jar 1898... Žiaľ, vojna pravdepodobne poskytla niektorým štátnym úradníkom príležitosť praktizovať korupciu. Mac-Lorin bol obvinený z rôznych pochybnych praktík, vrátane rodinkárstva a nadmerného využívania právomocí na milosť. V dobe hnutia za triezvosť kritici obviňovali guvernéra z alkoholizmu, čo verejne priznal.“
Historická chyba
Zvážme tradičný algoritmus násobenia z učebného plánu. Koľko vyžaduje jednociferných operácií násobenia? Predpokladajme, že násobíte 
-ciferné číslo 
na 
-ciferné 
. Najprv násobíte prvú cifru 
každou cifrou 
po rade. Potom násobíte druhú cifru 
každou cifrou 
po rade a tak ďalej, kým neprejdete všetkými ciferami 
. Týmto spôsobom tradičné násobenie vyžaduje 
primitívne násobenia. Konkrétne, násobenie dvoch čísel po 
cifrách vyžaduje 
jednociferných násobení.
Je to zlé, ale proces môžeme optimalizovať pomocou metódy vyvinutej ruským matematikom Anatolijom Alexejevičom Karacubom. Predpokladajme, že 
a 
sú dvojciferné desatinné čísla; to znamená, že existujú čísla 
, 
, 
, 
také, že 
a 
(generalizácia tohto algoritmu na vyššie čísla si vyžaduje určité manipulácie; hoci to nie je príliš zložité, aby som sa vyhol chybám v detailoch, radšej sa budem držať jednoduchého príkladu). Potom 
, 
, 
. Násobenie dvojčlenov dáva 
. V tejto chvíli máme stále 
jednociferných násobení: 
, 
, 
, 
. Teraz sčítajme a odpočítajme 
. Po niekoľkých preskupeniach, ktoré nechám ako cvičenie pre čitateľa, vzniká 
— iba tri jednociferné násobenia! (Existujú niektoré konštantné koeficienty, ale tie sa dajú vypočítať len sčítaním a posúvaním číslic).
Nežiadajte o dôkaz, ale Karatsubov algoritmus (rekurzívne zobecnený z predchádzajúceho príkladu) zlepšuje tradičnú metódu násobenia s 
operáciami na 
. Majte na pamäti, že toto je skutočné zlepšenie algoritmu, a nie optimalizácia pre výpočty v hlave. Skutočne, algoritmus nie je vhodný na počítanie v hlave, pretože si vyžaduje veľké režijné náklady na rekurzívne operácie. Okrem toho sa efekt neprejaví naplno, kým čísla nie sú dostatočne veľké (šťastne, namiesto Karatsubovho algoritmu sa objavili ešte rýchlejšie metódy: v marci 2019 bol publikovaný algoritmus, ktorý si vyžaduje iba násobení; zrýchlenie sa uplatňuje len na nepredstaviteľne veľké čísla).
Tento algoritmus je popísaný na strane 295 druhého zväzku «Algoritmy a ich analýzy». Tam Knuth píše: „Zaujímavé je, že túto myšlienku objavili až v 1962 roku“, keď bola publikovaná článok popisujúci Karatsubov algoritmus. Ale! V roku 1995 publikoval Karatsuba článok „Zložitosti výpočtov“, v ktorom hovorí niekoľko vecí: 1) okolo roku 1956 Kolmogorov predpokladal, že násobenie nie je možné vykonať za menej ako 
krokov; 2) v 1960 roku bol Karatsuba na seminári, kde Kolmogorov zhrnul svoju hypotézu n². 3) „Práve za týždeň“ Karatsuba vyvinul algoritmus „rozdeľuj a panuj“; 4) v roku 1962 napísal a publikoval článok v mene Karatsubu s popisom algoritmu. „O tomto článku som sa dozvedel až po tom, čo ho pretláčali“.
Tým pádom chyba spočíva v tom, že namiesto 1962 mal byť uvedený 1960 rok. A to je všetko.
Analýza
Hľadanie chýb nevyžadovalo osobitné zručnosti.
- Prvá chyba bola tak banálna, ako len môže byť, a nachádzala sa v relatívne viditeľnom mieste (začiatok kapitoly). Každý idiot by ju našiel; jednoducho som bol tým idiotom.
- Hľadanie druhej chyby si vyžadovalo šťastie a usilovnosť, nie však zručnosť. Index pre „Williamsa“ sa nachádza na predposlednej strane zväzku, dosť výrazná časť knihy. Práve som prelistovával index (nie je to tak žiaduce, ako sa zdá, pretože v indexoch Knutha sú schované veľké prekvapenia. Napríklad, sú tam položky v arabčine a hebrejčine, a obidve ukazujú na stranu 66. Ale na tejto strane nie je spomenutý žiaden z týchto jazykov; namiesto toho sa tu spomínajú „jazyky, ktoré sa čítajú sprava doľava“). A moja pozornosť upútalo druhé meno. Keďže zvyčajne čítam Wikipédiu, skontroloval som Robina Williamsa a všimol si nesúlad.
- Rád by som povedal, že som urobil seriózny výskum, aby som našiel historickú chybu, ale v skutočnosti som sa len pozrel Už v prvých vetách sa píše: „Karatsubov algoritmus je algoritmus rýchlej násobilky. Objavil ho Anatolij Karatsuba v roku 1960 a publikoval v roku 1962.“ Po tom sa už len zdalo, že stačí spočítať dve a dve.
V budúcnosti by som chcel nájsť podstatnejšiu chybu, najmä v kóde Knutha. Rovnako by som chcel nájsť bug v prvom zväzku „Základné algoritmy“. Možno by som aj našiel, ale v miestnej knižnici z nejakého dôvodu majú iba zväzky 2, 3 a 4A.
Finančné fakty:
- Celkovo sa môj príspevok do TAOCP skladá len z troch symbolov: jedného prídavku s, výmeny m na n a 2 na 0. Pri cene 2,56 USD sú to celkom ziskové symboly; keby vám platili takéto peniaze, článok o 1000 slov (v priemere štyri znaky) by vám priniesol desať kusov.
- S tromi hexadecimálnymi dolármi som spolu s 29 ďalšími občanmi na 69. mieste v rebríčku najbohatších vkladateľov banky San-Serif (k 1. máju 2019).
Ďalšie diskusie o šekoch od Knutha
Všeobecné odporúčania na hľadanie chýb v knihách Knutha. Týkajú sa najmä technických chýb, ktoré ja nemám. Je tam jedna veta, ktorú som prijal vážne:
Je lepšie počkať, kým nezhrniete súbor chýb na odoslanie. Spojením niektorých skutočných, ale nie veľmi cenných chýb zvýšite pravdepodobnosť, že jednu z nich naozaj vyhodnotia ako chybu alebo radu. Ak budete zasielať chyby po jednej, každú samostatne môžu odmietnuť.
Nechcel som posielať len bezvýznamné preklepy, poslúchol som radu a poslal som e-mail až keď som našiel historickú chybu, ktorá sa zdala byť dostatočne vážna.
Ašutoš Mehra je tretím najbohatším investitorom v San-Serriff s ohromným majetkom 0x$207,f0 v BoSS.
- Rôzne:
Zdroj: habr.com
