Donald Knuth — en forskare inom datavetenskap som bryr sig så mycket om korrektheten i sina böcker att han erbjuder en hex dollar ($2,56, 0x$1,00) för varje "fel" som hittas, där ett fel betraktas som allt som är "tekniskt, historiskt, typografiskt eller politiskt felaktigt". Jag ville verkligen få en check från Knuth, så jag bestämde mig för att leta efter fel i hans framstående verk "Programmeringens konst" (TAOCP). Jag lyckades hitta tre. Trots allt, Knuth skickade en check på 0x$3,00.

Som ni ser, är detta ingen riktig check. Tidigare skickade Knuth verkliga checkar, men han slutade med det år 2008 på grund av oupphörligt bedrägeri. Nu skickar han ut "personliga insättningscertifikat" från banken San Seriff (BoSS). Han säger att han är beredd att skicka verkliga pengar om det behövs, men det verkar vara för besvärligt.

Jag hittade två typografiska fel och ett historiskt fel. Jag listar dem i ordning av minskande trivialitet.

Typografiskt fel #1

Det första typografiska felet — på sidan 392 av den tredje volymen "Sortering och sökning", den åttonde raden från botten: "Efter en misslyckad sökning är det ibland (sometime) önskvärt att infoga en ny post i tabellen, som innehåller K; metoden som gör detta kallas för sök- och infogningsalgoritmen. Felet är att istället för sometime bör vara sometimes.

Självklart är det inget förvånande med ett sådant fel. Det finns säkert flera skrivfel i denna artikel (inga belöningar för att hitta dem). Det som verkligen är förvånande är att det har tagit så lång tid att upptäckas. Sida 392 är inte djupt begravd i matematikkapitlet, det är den allra första sidan i det sjätte kapitlet "Sökning"! Kanske en av de mest lästa delarna av boken. Teoretiskt sett borde det finnas minst fel där, men nej.

Förresten, om du någonsin har övervägt att läsa TAOCP, gör det. Många säger att det är en referensbok, inte avsedd för direkt läsning, men det är inte sant. Författaren har en tydlig åsikt och en unik stil. Det enda som hindrar läsbarheten är komplexiteten i matematik. Men det finns en enkel lösning: läs tills du når matematiken som du inte förstår, hoppa över den och gå till nästa avsnitt som du kan förstå. Genom att läsa på det sättet hoppar jag över minst 80% av boken, men de resterande 20% är fantastiska!

Det sägs också att TAOCP är irrelevant, föråldrad eller på annat sätt oanvändbar för "verklig programmering". Det är också falskt. Till exempel, i första avsnittet efter introduktionen diskuteras sökningen av ett element i en osorterad array. Den enklaste algoritmen är bekant för alla programmerare. Starta pekaren i början av arrayen och utför sedan följande steg i en loop:

1. Kontrollera om det nuvarande elementet är det önskade. Om så är fallet, returnera det; annars
2. Kontrollera om pekaren är utanför arrayen. Om så är fallet, returnera ett fel; annars
3. Öka pekaren och fortsätt.

Nu, låt oss överväga: hur många gränskontroller kräver denna algoritm, i genomsnitt? I värsta fall, när arrayen inte innehåller elementet, krävs en kontroll för varje element i listan, och i genomsnitt kommer det att se ut som . En smartare sökalgoritm kan klara sig med bara en gränskontroll. Fäst det önskade elementet i slutet av arrayen, starta sedan pekaren i början av arrayen och utför följande steg i en loop:

1. Kontrollera om det nuvarande elementet är det önskade. Om så är fallet, returnera svaret om pekaren är inom arrayens gränser, eller ett fel om den inte är det. Annars
2. Öka pekaren och fortsätt.

Så eller så, kommer elementet att hittas, och gränskontrollen utförs endast en gång när det inträffar. Det är en djup idé, men den är tillräckligt enkel även för en nybörjarprogrammerare. Kanske kan jag inte tala om relevansen av arbetet för andra, men jag lyckades omedelbart använda denna visdom i både personlig och professionell kod. Boken TAOCP är full av sådana pärlor (för att vara rättvis, där finns också mycket konstiga saker, som bubbel-sortering).

"Sök, sök
Så länge
Sök, sök
Jag ville bara dansa"
- Luther Vandross, "Sök" (1980)

Stavfel #2

Den andra tryckfelet finns i volym 4A, "Kombinatoriska algoritmer", del 1. På sidan 60 beskrivs en uppgift som handlar om planering av komikers uppträdanden på olika kasinon. Som exempel nämns flera verkliga komiker, inklusive Lily Tomlin, 'Weird Al' Yankovic och Robin Williams, som fortfarande levde när boken gavs ut. Knuth skriver alltid ut fullständiga namn i sitt register, så Williams nämns på sidan 882 som "Williams, Robin McLaurin". Men hans andra namn slutar på "n", inte "m", det vill säga McLaurin.

McLaurin är hans mors flicknamn. Hon var barnbarnsbarn till Anselm Joseph McLaurin, den 34:e guvernören i Mississippi. Hans mandat verkar inte ha blivit ihågkommet för något bra. Från boken "Mississippi: historia":

"Den viktigaste händelsen under McLaurins administration var att Förenta staterna förklarade krig mot Spanien våren 1898... Tyvärr kan kriget ha gett vissa offentliga tjänstemän möjlighet att utöva mutor. McLaurin anklagades för olika tvivelaktiga aktiviteter, inklusive nepotism och ett överdrivet användande av benådningsmakten. Under nykterhetsrörelsen anklagade kritiker guvernören för alkoholism, något han offentligt erkände."

Historiskt fel

Låt oss titta på traditionell multiplikationsalgoritm från skolprogrammet. Hur många enhetsoperationer för multiplikation kräver den? Anta att du multiplicerar -siffrigt tal till -siffrigt . Först multiplicerar du den första siffra med varje siffra i tur och ordning. Sedan multiplicerar du den andra siffran med varje siffra i tur och ordning och så vidare, tills du har gått igenom alla siffror . Därmed kräver traditionell multiplikation primitiva multiplikationer. Specifikt kräver multiplikationen av två tal med siffror enheter av multiplikation. Detta är dåligt, men man kan optimera processen med hjälp av en metod utvecklad av den sovjetiska matematikern Anatolij Alexejevitj Karatsuba. Anta att

-är tvåsiffriga decimaler; det vill säga det finns tal och  sådana att , , , ([generalizeringen av denna algoritm till större siffror kräver vissa manipulationer; även om det inte är alltför komplicerat, för att inte göra misstag i detaljerna, föredrar jag att hålla mig till ett enkelt exempel). Då och . Multiplikation av två termer ger , , . Just nu har vi fortfarande enhetsmultiplikation: . Nu lägger vi ihop och subtraherar , , , . . Efter flera omflyttningar, som jag lämnar som en övning för läsaren, får vi  — totalt tre enskilda multiplikationer! (Det finns vissa fasta koefficienter, men de kan bara beräknas genom addition och skiftning av siffror).

Be inte om bevis, men Karatsubas algoritm (rekursivt generaliserad från det ovanstående exemplet) förbättrar den traditionella multiplikationsmetoden med operationer till . Observera att detta är en verklig förbättring av algoritmen, inte en optimering för mentala beräkningar. Faktum är att algoritmen inte lämpar sig för mentala beräkningar, eftersom den kräver stora overheadkostnader för rekursiva operationer. Dessutom kommer effekten inte att manifestera sig helt förrän siffrorna blir tillräckligt stora (lyckligtvis, istället för Karatsubas algoritm kom ännu snabbare metoder: i mars 2019 publicerades en algoritm som endast kräver n log n multiplikationer; accelerationen är tillämplig endast på ofattbart stora tal).

Denna algoritm beskrivs på sidan 295 i den andra volymen av "Beräkningsalgoritmer". Där skriver Knuth: "Det är intressant att denna idé först upptäcktes år 1962 ", när artikeln som beskriver Karatsubas algoritm publicerades. Men! År 1995 publicerade Karatsuba artikeln "Beräkningskomplexitet", där han nämner flera saker: 1) omkring 1956 antydde Kolmogorov att multiplikation inte kan utföras på mindre än steg; 2) år 1960 deltog Karatsuba i ett seminarium där Kolmogorov presenterade sin hypotes n². 3) "Exakt en vecka" senare utvecklade Karatsuba algoritmen "dela och härska"; 4) 1962 skrev och publicerade Kolmogorov en artikel å Karatsubas vägnar som beskriver algoritmen. "Jag fick veta om denna artikel först efter att den trycktes om".

Således ligger felet i att istället för 1962 bör det anges 1960 år. Det är allt.

Analys

Felletande krävde inte särskild skicklighet.

1. Det första felet var så banalt som möjligt och befann sig på ett relativt synligt ställe (i början av kapitlet). Vilken idiot som helst skulle ha funnit det; jag råkade bara vara den idioten.
2. Att hitta det andra typoskrivet krävde tur och flit, men inte mycket skicklighet. Indexet för "Williams" finns på näst sista sidan av volymen, en ganska framträdande del av boken. Jag bläddrade just igenom indexet (det är inte så synd om det som det verkar, eftersom Knuths index döljer påskägg. Till exempel finns det poster på arabiska och hebreiska, och båda pekar på sida 66. Men på denna sida nämns inget av språken; istället nämns "språk som läses från höger till vänster"). Och min uppmärksamhet drogs till det andra namnet. Eftersom jag brukar läsa Wikipedia, kollade jag Robin Williams och märkte en avvikelse.
3. Jag önskar jag kunde säga att jag gjorde en seriös forskning för att hitta det historiska felet, men i själva verket tittade jag bara på Wikipedia-sidan om Karatsubas algoritm. I första raden står det: "Karatsubas algoritm är en algoritm för snabb multiplikation. Upptäckte av Anatolij Karatsuba 1960 och publicerades 1962." Efter detta var det bara att lägga ihop två gånger två.

I framtiden skulle jag vilja hitta ett mer betydande fel, särskilt i Knuths kod. Jag skulle också vilja hitta en bugg i första volymen av "Fundamentala algoritmer". Kanske skulle jag hitta en, men på det lokala biblioteket finns det av någon anledning bara volymerna 2, 3 och 4A.

Finansiella fakta:

• Totalt består mitt bidrag till TAOCP av endast tre tecken: en tillägg s, en ersättning m till n och 2 till 0. För $2,56 är det ganska lönsamma tecken; om du fick betalt så här skulle en artikel på 1000 ord (i genomsnitt fyra tecken) ge dig tio stycken.
• Med tre hexadecimala dollar delar jag, tillsammans med 29 andra medborgare, 69:e plats på listan över de rikaste insättarna i San-Seriff-banken (per den 1 maj 2019).

Andra diskussioner om Knuths checkar

• Hur man får en check från Knuth

  Allmänna rekommendationer för att hitta fel i Knuths böcker. Handlar huvudsakligen om tekniska fel, som jag inte har. Det finns ett påstående som jag tog på allvar:

  Bättre att vänta tills du har samlat ett felset att skicka. Genom att sammanfoga några verkliga men inte särskilt värdefulla fel, ökar du chansen att en av dem verkligen uppfattas som ett fel eller råd. Om man skickar fel ett i taget kan varje av dem avvisas.

  Jag ville inte bara skicka meningslösa skrivfel, utan följde rådet och skickade brevet först när jag hade funnit ett historiskt fel som verkade tillräckligt allvarligt.

• Kvitton från Ashutosh Mehra

  Ashutosh Mehra är den tredje rikaste investeraren i San-Serriff med ett enormt förmögenhet på 0x$207,f0 i BoSS.

• Kvitto för vissa icke-funktionella fel i den verkliga koden TeX
• Olika: #1 #2 #3 #4 #5 #6

Källa: habr.com