Donald Knuth — en forsker inden for datalogi, der bekymrer sig så meget om nøjagtigheden af sine bøger, at han tilbyder en hexadecimal dollar ($2,56, 0x$1,00) for enhver fundet "fejl", hvor en fejl defineres som alt, hvad der er "teknisk, historisk, typografisk eller politisk forkert". Jeg ønskede virkelig at modtage en check fra Knuth, så jeg besluttede at lede efter fejl i hans fremragende værk "Kunstens Programmering" (TAOCP). Jeg lykkedes med at finde tre. Trods ordet, Knuth sendte en check på 0x$3,00.
Som du kan se, er dette ikke en rigtig check. Tidligere sendte Knuth rigtige checks, men stoppede i 2008 på grund af . Nu sender han "personlige indbetalingscertifikater" fra (BoSS). Han siger, at han er villig til at sende rigtige penge, hvis nødvendigt, men det ser ud til at være for besværligt.
Jeg fandt to trykfejl og en historisk fejl. Jeg vil nævne dem i rækkefølge efter faldende trivialisering.
Trykfejl nr. 1
Den første trykfejl findes på side 392 af tredje bind "Sortering og søgning", ottende linje fra bunden: "Efter et mislykket søgning er det nogle gange (sometime) ønskeligt at indtaste en ny post i tabellen, der indeholder K; metoden, der gør dette, kaldes søge- og indsætningsalgoritmen. Fejlen er, at i stedet for sometime skal være sometimes.
Selvfølgelig er der ikke noget overraskende ved en sådan fejl. I denne artikel er der uden tvivl flere trykfejl (ingen belønninger for at finde dem). Det, der faktisk er overraskende, er, at de er blevet overset så længe. Side 392 er ikke begravet dybt i matematikafsnittet, det er den allerførste side af det sjette kapitel "Søgning"! Måske en af de mest læste sektioner i bogen. Idéen er, at der burde være færre trykfejl der, men nej.
Forresten, hvis du nogensinde har overvejet at læse TAOCP, så prøv. Mange vil sige, at det er en opslagsbog, der ikke er beregnet til direkte læsning, men det er ikke sandt. Forfatteren har en klar synsvinkel og en særpræget stil. Det eneste, der hindrer læsbarheden, er kompleksiteten af matematikken. Men der er en simpel løsning: Læs, indtil du når til den matematik, du ikke forstår, spring over den, og åbn næste afdeling, som du kan forstå. På den måde springer jeg over mindst 80 % af bogen, men de resterende 20 % er fremragende!
Det siges også, at TAOCP er irrelevant, forældet eller på anden måde uanvendelig til «rigtig programmering». Dette er også usandt. For eksempel behandles søgning efter et element i et usorteret array i første sektion efter introduktionen. Den simpleste algoritme er kendt af alle programmører. Start pegeren i begyndelsen af arrayet, og udfør derefter følgende trin i en løkke:
- Tjek om det nuværende element er det ønskede. Hvis ja, returnér det; ellers
- Tjek om pegeren er uden for arrayet. Hvis ja, returnér en fejl; ellers
- Øg pegeren og fortsæt.
Lad os nu overveje: hvor mange grænsekontroller kræver denne algoritme i gennemsnit? I værste fald, når arrayet ikke indeholder elementet, kræves der en kontrol for hvert element i listen, og i gennemsnit vil det være noget i stil med 
. En klogere søgealgoritme kan klare sig med kun én grænsekontrol. Føj det ønskede element til slutningen af arrayet, start derefter pegeren i begyndelsen af arrayet og udfør følgende trin i en løkke:
- Tjek om det nuværende element er det ønskede. Hvis ja, returnér svaret, hvis pegeren er inden for arrayet, eller en fejl, hvis ikke. Ellers
- Øg pegeren og fortsæt.
Uanset hvad, vil elementet blive fundet, og grænsekontrollen udføres kun én gang, når det sker. Dette er en dyb idé, men den er enkel nok selv for en nybegyndende programmør. Jeg kan nok ikke tale om relevansen af arbejdet for andre, men jeg kunne straks anvende denne visdom i både mit personlige og professionelle kode. Bogen TAOCP er fuld af sådanne perler (for retfærdighedens skyld, der er også mange underlige ting, såsom ).
«Søgningen, søgningen
Så længe
Søgningen, søgningen
Jeg ville bare danse»
— Luther Vandross, «Søgning» (1980)
Trykfejl nr. 2
Den anden trykfejl er i bind 4A, "Kombinatoriske algoritmer", del 1. På side 60 beskrives en opgave med at planlægge optrædener for komikere i forskellige kasinoer. Som eksempel nævnes flere virkelige komikere, herunder Lily Tomlin, Weird Al Yankovic og Robin Williams, som stadig var i live, da bogen blev udgivet. Knuth angiver altid de fulde navne i indekset, så Williams nævnes på side 882 som "Williams, Robin McLaurin". Men hans mellemnavn slutter med "n" og ikke "m", det vil sige McLaurin.
McLaurin er hans moders efternavn. Hun var oldebarn af Anselm Joseph McLaurin, den 34. guvernør i Mississippi. Hans embedsperiode huskes åbenbart ikke for noget godt. Fra bogen :
"Det vigtigste begivenhed under McLaurins administration var, at De Forenede Stater erklærede krig mod Spanien i foråret 1898... Desværre gav krigen muligvis nogle offentlige embedsmænd mulighed for at praktisere bestikkelse. McLaurin blev beskyldt for forskellige tvivlsomme praksisser, herunder nepotisme og overdreven brug af benådning. I en tid med afholdenhedsbevægelsen blev guvernøren kritiseret for sin alkoholisme, som han offentligt tilstod."
Historisk fejl
Lad os overveje den traditionelle multiplikationsalgoritme fra skolepensum. Hvor mange en-cifrede multiplikationer kræver den? Antag, at du multiplicerer 
-cifret tal 
og få en fungerende kommando. 
-cifret 
. Først multiplicerer du det første ciffer 
med hvert ciffer 
en ad gangen. Dernæst multiplicerer du det andet ciffer 
med hvert ciffer 
en ad gangen og så videre, indtil du har passeret alle cifre 
. Således kræver traditionel multiplikation 
primitive multiplikationer. Især kræver multiplikationen af to tal med 
cifre 
en-cifrede multiplikationer.
Det er ikke godt, men processen kan optimeres ved hjælp af en metode udviklet af den sovjetiske matematiker Anatolij Alexejevitsj Karatsuba. Antag, at 
og 
- to-cifrede decimaler; det vil sige, at der findes tal 
, 
, 
, 
således at 
og 
(generaliseringen af denne algoritme til større cifre kræver visse manipulationer; selvom det ikke er så svært, vil jeg hellere holde mig til et simpelt eksempel for ikke at lave fejl i detaljerne). Så 
, 
, 
. Multiplikation af to led giver 
. Indtil nu har vi stadig 
en-cifrede multiplikationer: 
, 
, 
, 
. Lad os nu lægge sammen og trække fra 
. Efter flere omarrangementer, som jeg vil lade være som en opgave for læseren, får man 
— i alt tre ensteges multiplikationer! (Der er nogle permanente koefficienter, men de kan kun beregnes ved addition og bit-shifting).
Bed ikke om bevis, men Karatsuba-algoritmen (rekursivt generaliseret fra det ovenfor nævnte eksempel) forbedrer den traditionelle multiplikationsmetode fra 
operationer til 
. Bemærk, at dette er en reel forbedring af algoritmen og ikke en optimering til mentale beregninger. Faktisk er algoritmen ikke velegnet til hovedregning, da den kræver store omkostninger til rekursive operationer. Desuden vil effekten ikke fuldt ud vise sig, før tallene bliver store nok (heldigvis kom der endnu hurtigere metoder efter Karatsuba-algoritmen: i marts 2019 blev der offentliggjort en algoritme, der kun kræver multiplikationer; accelerationen gælder kun for ubegribeligt store tal).
Denne algoritme er beskrevet på side 295 i den anden bind af 'De beregnede algoritmer'. Der skriver Knuth: 'Det er interessant, at denne idé kun blev opdaget i 1962 året', da der blev offentliggjort en artikel, der beskrev Karatsuba-algoritmen. Men! I 1995 offentliggjorde Karatsuba en artikel 'Computationskompleksitet', hvor han nævner flere ting: 1) Omkring 1956 antog Kolmogorov, at multiplikation ikke kan udføres med mindre end 
trin; 2) i 1960 året deltog Karatsuba i et seminar, hvor Kolmogorov fremlagde sin hypotese n². 3) 'Bare en uge' senere udviklede Karatsuba 'divide and conquer'-algoritmen; 4) i 1962 skrev og offentliggjorde Kolmogorov en artikel på vegne af Karatsuba med beskrivelsen af algoritmen. 'Jeg hørte først om denne artikel, efter at den blev genoptrykt.'
Således ligger fejlen i, at i stedet for 1962 skal der angives 1960 året. Det er det hele.
Analyse
Fejlsøgningen krævede ikke stor dygtighed.
- Den første fejl var så banal, som det overhovedet kan være, og lå et relativt synligt sted (starten af kapitlet). Enhver idiot ville have fundet den; det var bare mig, der var den idiot.
- At finde den anden fejl krævede held og flid, men ikke nødvendigvis dygtighed. Indekset for 'Williams' findes på næstsidste side af bindet, en ganske væsentlig del af bogen. Jeg var lige i gang med at bladre i indekslisten (det er ikke så slemt, som det lyder, fordi Knuths indekser gemmer på påskeæg. For eksempel er der poster på arabisk og hebraisk, og begge henviser til side 66. Men på denne side omtales ingen af de sprog; i stedet nævnes 'sprog, der læses fra højre mod venstre'). Og mit opmærksomhed blev fanget af det andet navn. Da jeg normalt læser Wikipedia, tjekkede jeg Robin Williams og opdagede en uoverensstemmelse.
- Jeg ville ønske, jeg kunne sige, at jeg havde udført en seriøs undersøgelse for at finde den historiske fejl, men jeg kiggede faktisk bare på . I de første sætninger står der: 'Karatsuba-algoritmen er en algoritme til hurtig multiplikation. Opdaget af Anatoly Karatsuba i 1960 og offentliggjort i 1962'. Efter dette var det kun at lægge to og to sammen.
I fremtiden ville jeg gerne finde en mere væsentlig fejl, især i Knuths kode. Jeg ville også gerne finde en fejl i første bind af 'Fundamentale algoritmer'. Måske ville jeg finde en, men i det lokale bibliotek findes der af en eller anden grund kun bind 2, 3 og 4A.
Finansielle fakta:
- I alt består mit bidrag til TAOCP kun af tre tegn: én tilføjelse s, én erstatning m og få en fungerende kommando. n og 2 og få en fungerende kommando. 0. Til $2,56 er det ret lukrative tegn; hvis du blev betalt sådan, ville en artikel på 1000 ord (i gennemsnit fire tegn) give dig ti enheder.
- Med tre hexadecimale dollars deler jeg sammen med 29 andre borgere 69. pladsen på listen over de rigeste indskydere i banken San Serriff (pr. 1. maj 2019).
Andre diskussioner om checks fra Knuth
Generelle anbefalinger til fejlfinding i Knuths bøger. De handler primært om tekniske fejl, som jeg ikke har. Der er én sætning, jeg tog alvorligt:
Det er bedre at vente, indtil du har samlet et sæt fejl til at sende. Ved at samle flere reelle, men ikke særlig værdifulde fejl, øger du chancerne for, at en af dem faktisk bliver anset som en fejl eller en anbefaling. Hvis du sender fejl én ad gangen, kan hver enkelt blive afvist.
Jeg ønskede ikke bare at sende ligegyldige skrivefejl, så jeg fulgte rådet og sendte brevet først, da jeg fandt en historisk fejl, som syntes at være alvorlig nok.
Ashutosh Mehra – den tredje rigeste bidragyder i San-Seriff med en kolossal formue på 0x$207,f0 i BoSS.
- Diverse:
Kilde: habr.com
