Donald Knuth je informatičar koji toliko brine o točnosti svojih knjiga da predlaže jedan heksadecimalni dolar (2,56 USD, 0x 1,00 USD) za svaku pronađenu "pogrešku", pri čemu je pogreška definirana kao sve što je "tehnički, povijesno, tipografski ili politički netočno." Stvarno sam želio dobiti ček od Knutha, pa sam odlučio potražiti pogreške u njegovom magnum opusu "Umijeće programiranja" (TAOCP). Uspjeli smo pronaći tri. Vjeran svojoj riječi, Knut je poslao ček za 0x 3,00 USD.
Kao što vidite, ovo nije pravi ček. Knuth je slao prave čekove, ali je prestao 2008. zbog . On sada šalje "osobne potvrde o depozitu" na (Šef). Kaže da je spreman poslati pravi novac ako bude potrebno, ali čini se da je to prevelika gnjavaža.
Našao sam dvije tipfelere i jednu povijesnu grešku. Navest ću ih redoslijedom sve manje trivijalnosti.
Tipkarska pogreška #1
Prva tiskarska pogreška nalazi se na stranici 392 trećeg sveska “Razvrstavanje i pretraživanje”, osmi red od dna: “Nakon neuspješnog pretraživanja, ponekad (ponekad) je poželjno unijeti novi zapis u tablicu koja sadrži K; metoda koja to čini naziva se algoritam pretraživanja i umetanja. Pogreška je u tome što umjesto jednom mora biti ponekad.
Naravno, takva pogreška ne čudi. Samo u ovom članku sigurno će biti nekoliko tipfelera (nema nagrade za njihovo pronalaženje). Ono što je stvarno iznenađujuće je da je tako dugo prošlo nezapaženo. Stranica 392 nije zakopana duboko u matematički dio, jest već prva stranica Poglavlje 6 "Traži"! Vjerojatno jedan od najčitanijih dijelova knjige. U teoriji bi trebalo biti najmanje tipfelera, ali ne.
Usput, ako ste ikada razmišljali o čitanju TAOCP-a, pokušajte. Mnogi će reći da je to imenik, nije namijenjen izravnom čitanju, ali to nije točno. Autor ima jasno stajalište i osebujan stil. Jedina stvar koja otežava čitljivost je složenost matematike. Međutim, postoji jednostavno rješenje: čitajte dok ne dođete do matematike koju ne razumijete, preskočite je i prijeđite na sljedeći odjeljak koji razumijete. Čitajući na ovaj način, propustim barem 80% knjige, ali ostalih 20% je super!
Također je rečeno da TAOCP nebitno, je zastario ili na drugi način nije primjenjiv na "pravo programiranje". Ovo također nije istina. Na primjer, prvi odjeljak nakon uvoda bavi se pronalaženjem elementa u nesortiranom nizu. Najjednostavniji algoritam je poznat svim programerima. Pokrenite pokazivač na početku niza, a zatim učinite sljedeće u petlji:
- Provjerite je li trenutni element željeni. Ako je tako, vraćamo ga; inače
- Provjerite nalazi li se pokazivač izvan granice polja. Ako je tako, vrati pogrešku; inače
- Povećaj i nastavi.
Sada razmislite: koliko provjera granica u prosjeku zahtijeva ovaj algoritam? U najgorem slučaju, gdje niz ne sadrži element, svaki element na popisu će zahtijevati jednu provjeru, au prosjeku će to biti nešto poput 
. Pametniji algoritam pretraživanja mogao bi se izvući sa samo jednom provjerom granica. Pričvrstite željeni element na kraj niza, zatim pokrenite pokazivač na početku niza i učinite sljedeće u petlji:
- Provjerite je li trenutni element željeni. Ako je tako, vraćamo odgovor ako je pokazivač unutar polja ili grešku ako nije. Inače
- Povećaj i nastavi.
Na ovaj ili onaj način, element je zajamčeno pronađen, a provjera granica se izvodi samo jednom kada se to dogodi. Ovo je duboka ideja, ali je dovoljno jednostavna čak i za programera početnika. Vjerojatno ne mogu govoriti o relevantnosti rada za druge, ali odmah sam mogao primijeniti ovu mudrost i na osobni i na profesionalni kodeks. Knjiga TAOCP puna je takvih dragulja (da budemo pošteni, tu ima i mnogo čudnih stvari, kao npr. ).
„Traži, traži
Tako dugo
Traži, traži
Samo sam htjela plesati"
— Luther Vandross, "Potraga" (1980.)
Tipkarska pogreška #2
Druga tipfelerska pogreška nalazi se u svesku 4A, Kombinatorni algoritmi, 1. dio. Stranica 60 opisuje problem koji uključuje zakazivanje nastupa komičara u raznim kasinima. Nekoliko komičara iz stvarnog života navodi se kao primjer, uključujući Lily Tomlin, Weird Ala Yankovica i Robina Williamsa, koji je još bio živ kad je knjiga objavljena. Knuth uvijek navodi puna imena u indeksu, tako da je Williams naveden na stranici 882 kao "Williams, Robin McLorim." Ali njegovo srednje ime završava na "n", a ne na "m", odnosno McLaurin.
McLaurin je bilo djevojačko prezime njegove majke. Bila je praunuka Anselma Josepha McLaurina, 34. guvernera Mississippija. Njegova vladavina, očito, nije zapamćena ni po čemu dobrom. Iz knjige :
“Najvažniji događaj tijekom McLaurinove administracije bila je objava rata Sjedinjenih Država Španjolskoj u proljeće 1898. godine... Nažalost, rat je nekim vladinim dužnosnicima možda pružio priliku da se uključe u podmićivanje. McLaurin je optužen za razne upitne prakse, uključujući nepotizam i prekomjerno korištenje ovlasti za pomilovanje. Tijekom pokreta za umjerenost kritičari su guvernera optuživali da je pijanica, što je on javno priznao.”
Povijesna greška
Uzeti u obzir tradicionalni algoritam množenja iz školskog programa. Koliko jednoznamenkastih množenja zahtijeva? Pretpostavimo da množite 
- znamenkasti broj 
na 
-bit 
. Prvo pomnožite prvu znamenku 
za svaku znamenku 
jedan po jedan. Zatim pomnožite drugu znamenku 
za svaku znamenku 
jedan po jedan i tako dok ne prođete kroz sve brojeve 
. Stoga tradicionalno množenje zahtijeva 
primitivna množenja. Konkretno, množenje dva broja sa 
potrebni činovi 
jednoznamenkastim množenjima.
To je loše, ali moguće je optimizirati proces pomoću metode koju je razvio sovjetski matematičar Anatolij Aleksejevič Karacuba. Hajdemo to pretvarati 
и 
- dvoznamenkasti decimalni brojevi; odnosno postoje brojevi 
, 
, 
, 
takav da 
и 
(generalizacija ovog algoritma na veće brojeve zahtijeva neke manipulacije; iako nije previše teško, kako ne bi pogriješili u detaljima, bolje ću se držati jednostavnog primjera). Zatim 
, 
, 
. Množenje binoma daje 
. U ovom trenutku još uvijek imamo 
jednoznamenkasto množenje: 
, 
, 
, 
. Sada zbrajajmo i oduzimamo 
. Nakon nekoliko preslagivanja, koja ću ostaviti kao vježbu čitatelju, ispada 
- samo tri jednoznamenkasta množenja! (Postoje neki konstantni koeficijenti, ali oni se mogu izračunati samo zbrajanjem i pomicanjem znamenki).
Ne tražite dokaze, ali Karatsuba algoritam (rekurzivno generalizirano iz gornjeg primjera) poboljšava tradicionalnu metodu množenja s 
operacije prije 
. Imajte na umu da je ovo stvarno poboljšanje algoritma, a ne optimizacija za mentalne izračune. Doista, algoritam nije prikladan za mentalnu aritmetiku, budući da zahtijeva velike režijske troškove za rekurzivne operacije. Osim toga, učinak se neće u potpunosti očitovati sve dok brojevi ne postanu dovoljno veliki (srećom, Karatsubin algoritam zamijenjen je još bržim metodama: u ožujku 2019. objavljen je algoritam koji zahtijeva samo množenja; akceleracija se odnosi samo na nezamislivo velike brojeve).
Ovaj algoritam je opisan na stranici 295 sveska XNUMX, Polunumerički algoritmi. Ondje Knuth piše: “Zanimljivo je da je ova ideja otkrivena tek u 1962 godine”, kada je objavljen članak koji opisuje Karatsubin algoritam. Ali! Godine 1995. Karatsuba je objavio rad "Computational Complexity", koji kaže nekoliko stvari: 1) oko 1956. Kolmogorov je predložio da se množenje ne može izvesti u manje od 
koraci; 2) u 1960 godine Karatsuba je prisustvovao seminaru na kojem je Kolmogorov predstavio svoju hipotezu n². 3) “U točno tjedan dana,” Karatsuba je razvio algoritam “podijeli pa vladaj”; 4) 1962. Kolmogorov je napisao i objavio članak u ime Karatsube s opisom algoritma. “Saznao sam za ovaj članak tek nakon što je ponovno objavljen.”
Dakle, pogreška je u tome što umjesto 1962 mora biti navedeno 1960 godina. To je sve.
Analiza
Pronalaženje pogrešaka nije zahtijevalo posebnu vještinu.
- Prva pogreška je bila što trivijalnija i nalazila se na relativno vidljivom mjestu (početak poglavlja). Svaki idiot bi to pronašao; Upravo sam ispao taj idiot.
- Pronalaženje druge tiskarske pogreške zahtijevalo je sreću i marljivost, ali ne i vještinu. Indeks za "Williamsa" nalazi se na pretposljednjoj stranici sveska, prilično istaknutom dijelu knjige. Upravo sam prelistavao indeks (nije tako patetično kao što zvuči, jer postoje uskršnja jaja skrivena u Knuthovim indeksima. Na primjer, postoje unosi na arapskom i hebrejskom, oba pokazuju na stranicu 66. Ali ta stranica ne spominje oba jezika; umjesto toga se odnosi na "jezike koji se čitaju s desna na lijevo"). I drugo ime mi je privuklo pozornost. Budući da obično čitam Wikipediju, provjerio sam Robina Williamsa i primijetio odstupanje.
- Volio bih da mogu reći da sam ozbiljno istraživao kako bih pronašao povijesnu pogrešku, ali zapravo sam samo pogledao . Već prvi redovi kažu: “Karatsuba algoritam je brzi algoritam množenja. Otkrio ga je Anatolij Karacuba 1960. i objavio 1962. Nakon toga ostalo je samo zbrojiti dva i dva.
U budućnosti bih želio pronaći značajniju grešku, posebno u Knuthovom kodu. Također bih želio pronaći grešku u prvom svesku Temeljnih algoritama. Možda bih ga našao, ali iz nekog razloga lokalna knjižnica ima samo sveske 2, 3 i 4A.
Financijske činjenice:
- Ukupno, moj doprinos TAOCP-u sastoji se od samo tri znaka: jedan dodatak s, zamjena m na n и 2 na 0. Po cijeni od 2,56 USD, ovo su neki prilično unosni simboli; Kad biste bili toliko plaćeni, članak od 1000 riječi (u prosjeku četiri znaka) zaradio bi vam deset tisuća.
- S tri heksadecimalna dolara ja sam, zajedno s još 29 građana, izjednačen na 69. mjestu na listi najbogatijih štediša San Serriff banke (od 1. svibnja 2019.).
Ostale rasprave o čekovima od Knutha
Opće preporuke za pronalaženje pogrešaka u Knuthovim knjigama. Uglavnom se radi o tehničkim greškama, kojih ja nemam. Tu postoji jedan prijedlog koji sam ozbiljno shvatio:
Najbolje je pričekati dok ne prikupite skup pogrešaka za slanje. Kombiniranjem nekoliko stvarnih, ali ne baš vrijednih pogrešaka, povećavate vjerojatnost da će se jedna od njih doista smatrati pogreškom ili savjetom. Ako šaljete pogreške jednu po jednu, svaka pojedinačno može biti odbijena.
Nisam htio poslati samo besmislene tipfelere, već sam poslušao savjet i poslao pismo tek kad sam pronašao povijesnu grešku koja se činila dovoljno ozbiljnom.
Ashutosh Mehra je treći najbogatiji investitor u San Serriffu s ogromnim bogatstvom od 0x$207.f0 u BoSS-u.
- Miscelanea:
Izvor: www.habr.com
