Donald Knuth er en datalog, der bekymrer sig så meget om nøjagtigheden af ​​sine bøger, som han foreslår en hex dollar ($2,56, 0x$1,00) for enhver fundet "fejl", hvor en fejl er defineret som noget, der er "teknisk, historisk, typografisk eller politisk ukorrekt." Jeg ville virkelig gerne have en check fra Knuth, så jeg besluttede at lede efter fejl i hans magnum opus "Kunsten at programmere" (TAOCP). Det lykkedes os at finde tre. Tro mod sit ord sendte Knut en check efter 0x$3,00.

Som du kan se, er dette ikke en rigtig check. Knuth plejede at sende rigtige checks, men stoppede i 2008 pga udbredt svindel. Han udsender nu "personlige indskudsbeviser" til Bank of San Serriff (Chef). Han siger, at han er villig til at sende rigtige penge, hvis det er nødvendigt, men det ser ud til, at det er for meget besvær.

Jeg fandt to tastefejl og en historisk fejl. Jeg vil liste dem i rækkefølge efter faldende trivialitet.

Tastefejl #1

Den første tastefejl er på side 392 i tredje bind af "Sortering og søgning", ottende linje fra bunden: "Efter en mislykket søgning er det nogle gange (nogle gange) ønskeligt at indtaste en ny post i tabellen, der indeholder K; metoden, der gør dette, kaldes søge- og indsæt-algoritmen. Fejlen er, at i stedet stykke tid burde være sommetider.

Selvfølgelig er en sådan fejl ikke overraskende. Der er helt sikkert et par tastefejl alene i denne artikel (ingen belønning for at finde dem). Hvad der virkelig er overraskende er, at det gik ubemærket hen så længe. Side 392 er ikke begravet dybt i matematikafsnittet, det er det den allerførste side Kapitel 6 "Søg"! Muligvis et af de mest læste afsnit i bogen. I teorien burde der være færrest slåfejl, men nej.

Forresten, hvis du nogensinde har tænkt på at læse TAOCP, så prøv det. Mange vil sige, at dette er Vejviser, ikke beregnet til direkte læsning, men dette er ikke sandt. Forfatteren har et klart synspunkt og en markant stil. Det eneste, der hindrer læsbarheden, er matematikkens kompleksitet. Der er dog en simpel løsning: læs, indtil du kommer til matematik, du ikke forstår, spring det over, og gå til næste afsnit, du kan forstå. Når jeg læser på denne måde, savner jeg mindst 80% af bogen, men de andre 20% er fantastiske!

Det siges også, at TAOCP irrelevant, er forældet eller på anden måde ikke anvendelig til "rigtig programmering". Dette er heller ikke sandt. For eksempel ser det første afsnit efter introduktionen på at finde et element i et usorteret array. Den enkleste algoritme er velkendt for alle programmører. Start markøren i begyndelsen af ​​arrayet, og gør derefter følgende i en løkke:

1. Tjek om det aktuelle element er det ønskede. Hvis det er tilfældet, returnerer vi det; Ellers
2. Kontroller, om markøren er uden for array-grænsen. Hvis ja, returner en fejl; Ellers
3. Zoom ind og fortsæt.

Overvej nu: hvor mange grænsekontrol kræver denne algoritme i gennemsnit? I værste fald, hvor arrayet ikke indeholder et element, vil hvert element på listen kræve en kontrol, og i gennemsnit vil det være noget i retning af . En smartere søgealgoritme kunne slippe af sted med kun én grænsekontrol. Fastgør det ønskede element til enden af ​​arrayet, start derefter markøren i begyndelsen af ​​arrayet og gør følgende i en løkke:

1. Tjek, om det aktuelle element er det ønskede. Hvis det er tilfældet, returnerer vi et svar, hvis markøren er inden for arrayet, eller en fejl, hvis den ikke er det. Ellers
2. Zoom ind og fortsæt.

På den ene eller anden måde er elementet garanteret at blive fundet, og grænsekontrollen udføres kun én gang, når dette sker. Dette er en dyb idé, men den er simpel nok selv for en nybegynder programmør. Jeg kan nok ikke udtale mig om arbejdets relevans for andre, men jeg var straks i stand til at anvende denne visdom på både personlig og professionel kode. TAOCP-bogen er fuld af sådanne perler (for at være retfærdig er der også en masse mærkelige ting derinde, som f.eks. boble sortering).

"Søg, søg
Så længe
Søg, søg
Jeg ville bare danse"
- Luther Vandross, "The Search" (1980)

Tastefejl #2

Den anden tastefejl er i bind 4A, Combinatorial Algorithms, Part 1. Side 60 beskriver et problem, der involverer at planlægge komikere til at optræde på forskellige kasinoer. Adskillige komikere fra det virkelige liv nævnes som eksempler, herunder Lily Tomlin, Weird Al Yankovic og Robin Williams, som stadig var i live, da bogen blev udgivet. Knuth angiver altid fulde navne i indekset, så Williams er opført på side 882 som "Williams, Robin McLorim." Men hans mellemnavn ender med "n" og ikke "m", altså McLaurin.

McLaurin var hans mors pigenavn. Hun var oldebarn af Anselm Joseph McLaurin, 34. guvernør i Mississippi. Hans regeringstid blev tilsyneladende ikke husket for noget godt. Fra bog "Mississippi: Historie":

”Den vigtigste begivenhed under McLaurin-administrationen var USA's krigserklæring mod Spanien i foråret 1898... Desværre kan krigen have givet nogle regeringsembedsmænd mulighed for at deltage i bestikkelse. McLaurin blev anklaget for forskellige tvivlsomme praksisser, herunder nepotisme og overdreven brug af benådningsbeføjelser. Under afholdsbevægelsen anklagede kritikere guvernøren for at være en drukkenbolt, hvilket han offentligt indrømmede."

Historisk fejl

Overvej traditionel multiplikationsalgoritme fra skolens læseplan. Hvor mange encifrede multiplikationer kræver det? Antag, at du formerer dig -cifret nummer på -bit . Gang først det første ciffer for hvert ciffer en efter en. Gang derefter det andet ciffer for hvert ciffer en efter en og så videre, indtil du gennemgår alle tallene . Derfor kræver traditionel multiplikation primitive multiplikationer. Især at gange to tal med rækker påkrævet enkeltcifrede multiplikationer.

Det er dårligt, men det er muligt at optimere processen ved hjælp af en metode udviklet af den sovjetiske matematiker Anatoly Alekseevich Karatsuba. Lad os lade som om и  - tocifrede decimaltal; det vil sige, at der er tal , , , sådan at и (at generalisere denne algoritme til større tal kræver en vis manipulation; selvom det ikke er for svært, for ikke at lave fejl i detaljerne, må jeg hellere holde mig til et simpelt eksempel). Derefter , , . Multiplikation af binomialer giver . I øjeblikket har vi stadig enkeltcifret multiplikation: , , , . Lad os nu addere og trække fra . Efter et par omlægninger, som jeg vil efterlade som en øvelse for læseren, viser det sig  - kun tre encifrede multiplikationer! (Der er nogle konstante koefficienter, men de kan kun beregnes ved at tilføje og forskyde cifrene).

Spørg ikke om bevis, men Karatsuba algoritme (rekursivt generaliseret fra eksemplet ovenfor) forbedrer den traditionelle multiplikationsmetode med operationer før . Bemærk venligst, at dette er en reel forbedring af algoritmen, ikke en optimering til mentale beregninger. Algoritmen er faktisk ikke egnet til hovedregning, da den kræver store overheadomkostninger til rekursive operationer. Derudover vil effekten ikke helt manifestere sig, før tallene bliver store nok (heldigvis er Karatsubas algoritme blevet erstattet af endnu hurtigere metoder: i marts 2019 blev der offentliggjort en algoritme, der kun kræver n log n multiplikationer; acceleration gælder kun for ufatteligt store tal).

Denne algoritme er beskrevet på side 295 i bind XNUMX, Semi-Numerical Algorithms. Der skriver Knuth: ”Det er mærkeligt, at denne idé først blev opdaget i 1962 år,” da en artikel, der beskrev Karatsubas algoritme, blev offentliggjort. Men! I 1995 udgav Karatsuba et papir om "Computational Complexity", som siger flere ting: 1) Omkring 1956 foreslog Kolmogorov, at multiplikation ikke kunne udføres på mindre end trin; 2) i 1960 år Karatsuba deltog i seminaret, hvor Kolmogorov præsenterede sin hypotese n². 3) "På præcis en uge" udviklede Karatsuba "del og hersk"-algoritmen; 4) i 1962 skrev og udgav Kolmogorov en artikel på vegne af Karatsuba med en beskrivelse af algoritmen. "Jeg fandt først ud af denne artikel, efter at den blev genudgivet."

Så fejlen er, at i stedet for 1962 skal specificeres 1960 år. Det er alt.

Analyse

At finde fejl krævede ikke særlige færdigheder.

1. Den første fejl var så triviel som muligt og var et relativt synligt sted (begyndelsen af ​​kapitlet). Enhver idiot ville have fundet det; Jeg viste sig bare at være den idiot.
2. At finde den anden tastefejl krævede held og flid, men ikke dygtighed. Indekset for "Williams" er på den næstsidste side af bindet, en ret fremtrædende del af bogen. Jeg bladrede lige i indekset (det er ikke så patetisk, som det lyder, for der er påskeæg gemt i Knuths indeks. For eksempel er der poster på arabisk og hebraisk, begge peger på side 66. Men den side nævner ikke begge sprog; i stedet refererer det til "sprog, der læses fra højre mod venstre"). Og det andet navn fangede min opmærksomhed. Da jeg normalt læser Wikipedia, tjekkede jeg Robin Williams og bemærkede en uoverensstemmelse.
3. Jeg ville ønske, at jeg kunne sige, at jeg lavede seriøs research for at finde en historisk fejl, men egentlig kiggede jeg bare Wikipedia-side om Karatsubas algoritme. De allerførste linjer siger: "Karatsuba-algoritmen er en hurtig multiplikationsalgoritme. Opdaget af Anatoly Karatsuba i 1960 og udgivet i 1962." Derefter var der kun tilbage at tilføje to og to.

I fremtiden vil jeg gerne finde en mere væsentlig fejl, især i Knuths kode. Jeg vil også gerne finde en fejl i første bind af Fundamental Algorithms. Måske ville jeg have fundet det, men af ​​en eller anden grund har det lokale bibliotek kun bind 2, 3 og 4A.

Økonomiske fakta:

• I alt består mit bidrag til TAOCP kun af tre karakterer: en tilføjelse s, udskiftning m på n и 2 på 0. Til $2,56 er disse nogle ret lukrative symboler; Hvis du blev betalt den slags penge, ville en artikel på 1000 ord (i gennemsnit på fire tegn) give dig ti tusinde.
• Med tre hexadecimale dollars ligger jeg, sammen med 29 andre borgere, på en 69. plads på listen over de rigeste indskydere i San Serriff Bank (pr. 1. maj 2019).

Andre diskussioner om checks fra Knuth

• Sådan får du en check fra Knuth

  Generelle anbefalinger til at finde fejl i Knuths bøger. For det meste vedrører de tekniske fejl, som jeg ikke har. Der er et forslag, som jeg tog alvorligt:

  Det er bedst at vente, indtil du har samlet et sæt fejl med at indsende. Ved at kombinere flere rigtige, men ikke særlig værdifulde fejl, øger du sandsynligheden for, at en af ​​dem rent faktisk bliver betragtet som en fejl eller et råd. Hvis du indsender fejl én ad gangen, kan hver enkelt enkelt blive afvist.

  Jeg ville ikke bare sende sludder stavefejl, men tog imod rådet og sendte først brevet, da jeg fandt en historisk fejl, der virkede alvorlig nok.

• Ashutosh Mehras checks

  Ashutosh Mehra er den tredjerigeste investor i San Serriff med en kæmpe nettoværdi på 0x$207.f0 i BoSS.

• Tjek for nogle ikke-funktionelle fejl i ægte TeX-kode
• Diverse: #1 #2 #3 #4 #5 #6

Kilde: www.habr.com