Donald Knuth on arvutiteadlane, kes hoolib nii väga oma raamatute täpsusest, mida ta soovitab üks hex dollar (2,56 dollarit, 0x 1,00 dollarit) leitud "vea" eest, kui viga on määratletud kui kõik, mis on "tehniliselt, ajalooliselt, tüpograafiliselt või poliitiliselt ebakorrektne". Tahtsin väga Knuthilt tšeki saada, nii et otsustasin otsida vigu tema magnum opusest "Programmeerimise kunst" (TAOCP). Meil õnnestus leida kolm. Oma sõnale truuks saatis Knut tšeki 0x3,00 dollarit.

Nagu näete, pole see tõeline kontroll. Knuth saatis varem tõelisi tšekke, kuid lõpetas selle tõttu 2008. aastal lokkav pettus. Nüüd saadab ta välja "isiklikud hoiusesertifikaadid". San Serriffi pank (Ülemus). Ta ütleb, et on vajadusel nõus päris raha saatma, kuid tundub, et sellega on liiga palju tüli.

Leidsin kaks kirjaviga ja ühe ajaloolise vea. Loetlen need triviaalsuse vähenemise järjekorras.

Kirjaviga nr 1

Esimene kirjaviga on kolmanda köite “Sorteerimine ja otsimine” lk 392, alt kaheksas rida: “Pärast ebaõnnestunud otsingut on vahel (vahel) soovitav sisestada tabelisse uus kirje, mis sisaldab K; meetodit, mis seda teeb, nimetatakse otsingu ja lisamise algoritmiks. Viga on hoopis selles millalgi peab olema mõnikord.

Muidugi pole selline viga üllatav. Ainuüksi selles artiklis on kindlasti paar kirjavigu (nende leidmise eest tasu ei maksta). Mis on tõesti üllatav, on see, et see jäi nii kauaks märkamatuks. Lehekülg 392 ei ole matemaatika sektsiooni sügavale maetud, see on küll kõige esimene leht 6. peatükk "Otsi"! Võimalik, et see on raamatu üks loetumaid osi. Teoreetiliselt peaks kirjavigu olema kõige vähem, aga ei.

Muide, kui olete kunagi mõelnud TAOCP lugemisele, proovige seda. Paljud ütlevad, et see on nii käsiraamat, pole mõeldud otseseks lugemiseks, kuid see pole tõsi. Autoril on selge vaatenurk ja omanäoline stiil. Ainus, mis loetavust takistab, on matemaatika keerukus. Siiski on lihtne lahendus: lugege, kuni jõuate matemaatikani, millest te aru ei saa, jätke see vahele ja minge järgmise osa juurde, millest saate aru. Nii lugedes tunnen raamatust vähemalt 80% puudust, aga ülejäänud 20% on suurepärane!

Räägitakse ka, et TAOCP ebaoluline, on aegunud või ei sobi muul viisil "päris programmeerimisele". Ka see ei vasta tõele. Näiteks esimene jaotis pärast sissejuhatust käsitleb elemendi leidmist sortimata massiivist. Lihtsaim algoritm on kõigile programmeerijatele tuttav. Käivitage kursor massiivi algusest, seejärel tehke tsüklina järgmist.

1. Kontrollige, kas praegune element on soovitud. Kui jah, tagastame selle; muidu
2. Kontrollige, kas kursor on väljaspool massiivi piiri. Kui jah, tagastage veateade; muidu
3. Suumi sisse ja jätka.

Mõelge nüüd: mitu piiride kontrolli see algoritm keskmiselt nõuab? Halvimal juhul, kui massiiv elementi ei sisalda, vajab iga loendi element ühte kontrolli ja keskmiselt on see midagi sellist . Nutikam otsingualgoritm pääseb vaid ühe piirikontrolliga. Kinnitage soovitud element massiivi lõppu, seejärel alustage kursorit massiivi algusest ja tehke tsüklina järgmist:

1. Kontrollige, kas praegune element on soovitud. Kui jah, tagastame vastuse, kui kursor asub massiivi sees, või vea, kui see ei ole. Muidu
2. Suumi sisse ja jätka.

Ühel või teisel viisil on elemendi leidmine garanteeritud ja piiride kontroll viiakse läbi ainult üks kord, kui see juhtub. See on sügav idee, kuid see on piisavalt lihtne isegi algaja programmeerija jaoks. Teose asjakohasusest ma ilmselt teistele rääkida ei oska, aga seda tarkust sain kohe rakendada nii isiklikus kui ka ametikoodis. TAOCP raamat on selliseid kalliskive täis (ausalt öeldes on seal ka palju kummalisi asju, nt. mulli sorteerimine).

"Otsi, otsi
Nii kaua
Otsi, otsi
Ma tahtsin lihtsalt tantsida"
- Luther Vandross, "Otsing" (1980)

Kirjaviga nr 2

Teine kirjaviga on köites 4A, Kombinatoorsed algoritmid, 1. osa. Lehekülg 60 kirjeldab probleemi, mis on seotud koomikutele erinevates kasiinodes esinemise ajakava koostamisega. Näitena tuuakse mitmeid tõsielu koomikuid, sealhulgas Lily Tomlin, Weird Al Yankovic ja Robin Williams, kes oli raamatu avaldamise ajal veel elus. Knuth loetleb registris alati täisnimed, nii et Williams on leheküljel 882 loetletud kui "Williams, Robin McLorim". Kuid tema keskmine nimi lõpeb tähega "n", mitte "m", see tähendab McLaurin.

McLaurin oli tema ema neiupõlvenimi. Ta oli Mississippi 34. kuberneri Anselm Joseph McLaurini lapselapselaps. Tema valitsemisaega ei mäletatud ilmselt millegi heaga. Raamatust "Mississippi: ajalugu":

“McLaurini administratsiooni ajal oli kõige olulisem sündmus Ameerika Ühendriikide sõjakuulutamine Hispaaniale 1898. aasta kevadel... Kahjuks võis sõda mõnele valitsusametnikule anda võimaluse tegeleda altkäemaksu andmisega. McLaurinit süüdistati mitmesugustes küsitavates tavades, sealhulgas nepotismis ja armuandmisvolituste liigses kasutamises. Karskusliikumise ajal süüdistasid kriitikud kuberneri joodikus, mida ta ka avalikult tunnistas.

Ajalooline viga

Arvestama traditsiooniline korrutamisalgoritm kooli õppekavast. Mitu ühekohalist korrutamist nõuab? Oletame, et korrutate -kohaline number edasi - natuke . Kõigepealt korrutage esimene number iga numbri kohta ükshaaval. Seejärel korrutage teine ​​number iga numbri kohta ükshaaval ja nii edasi, kuni kõik numbrid läbi käid . Seega nõuab traditsiooniline korrutamine primitiivsed korrutised. Eelkõige kahe arvu korrutamine auastmed nõutavad ühekohalised korrutised.

See on halb, kuid protsessi on võimalik optimeerida, kasutades Nõukogude matemaatiku Anatoli Aleksejevitš Karatsuba välja töötatud meetodit. Teeskleme seda и  - kahekohalised kümnendarvud; see tähendab, et numbrid on olemas , , , selline, et и (selle algoritmi üldistamine suurematele arvudele nõuab mõningast manipuleerimist; kuigi see pole liiga keeruline, jään parem lihtsa näite juurde, et mitte teha vigu detailides). Siis , , . Binoomide korrutamine annab . Hetkel on meil veel ühekohaline korrutis: , , , . Nüüd liidame ja lahutame . Pärast mõningaid ümberkorraldusi, mille jätan lugejale harjutuseks, selgub  - ainult kolm ühekohalist korrutamist! (On mõned konstantsed koefitsiendid, kuid neid saab arvutada ainult numbrite liitmise ja nihutamise teel).

Ära küsi tõendeid, aga Karatsuba algoritm (ülaltoodud näite põhjal rekursiivselt üldistatud) täiustab traditsioonilist korrutamismeetodit operatsioonid enne . Pange tähele, et see on algoritmi tõeline täiustus, mitte vaimsete arvutuste optimeerimine. Tõepoolest, see algoritm ei sobi peastarvutamiseks, kuna see nõuab rekursiivsete toimingute jaoks suuri üldkulusid. Lisaks ei avaldu efekt täielikult enne, kui numbrid muutuvad piisavalt suureks (õnneks on Karatsuba algoritm asendunud veelgi kiiremate meetoditega: märtsis 2019 avaldati algoritm, mis nõuab vaid n logi n korrutised; kiirendus kehtib ainult kujuteldamatult suurte arvude puhul).

Seda algoritmi on kirjeldatud 295. köite poolnumbrilised algoritmid leheküljel XNUMX. Seal kirjutab Knuth: "On uudishimulik, et see idee avastati alles aastal 1962 aastal”, kui avaldati Karatsuba algoritmi kirjeldav artikkel. Aga! 1995. aastal avaldas Karatsuba artikli "Arvutuslik keerukus", milles öeldakse mitu asja: 1) 1956. aasta paiku soovitas Kolmogorov, et korrutamist ei saa teha vähem kui sammud; 2) sisse 1960 aastal osales Karatsuba seminaril, kus Kolmogorov esitas oma hüpoteesi n². 3) "Täpselt ühe nädalaga" töötas Karatsuba välja "jaga ja valluta" algoritmi; 4) 1962. aastal kirjutas ja avaldas Kolmogorov artikli Karatsuba nimel koos algoritmi kirjeldusega. "Sain sellest artiklist teada alles pärast selle uuesti avaldamist."

Nii et viga on selles, et selle asemel 1962 tuleb täpsustada 1960 aastal. See on kõik.

Analüüs

Vigade leidmine ei nõudnud erilist oskust.

1. Esimene viga oli võimalikult triviaalne ja oli suhteliselt nähtavas kohas (peatüki algus). Iga idioot oleks selle leidnud; Ma lihtsalt osutusin selleks idioodiks.
2. Teise kirjavea leidmine nõudis õnne ja hoolsust, kuid mitte oskust. "Williamsi" register on köite eelviimasel leheküljel, mis on raamatu üsna silmapaistev osa. Lappasin just registrit (see pole nii haletsusväärne, kui see kõlab, sest Knuthi registrites on peidus lihavõttemunad. Näiteks on araabia ja heebreakeelseid sissekandeid, mõlemad osutavad leheküljele 66. Aga sellel lehel ei mainita kumbki keel; selle asemel viitab see "keeltele, mida loetakse paremalt vasakule"). Ja teine ​​nimi köitis mu tähelepanu. Kuna ma tavaliselt loen Wikipediat, kontrollisin Robin Williamsit ja märkasin lahknevust.
3. Soovin öelda, et tegin ajaloolise vea leidmiseks tõsist uurimistööd, kuid tegelikult ma lihtsalt vaatasin Wikipedia leht Karatsuba algoritmi kohta. Esimesed read ütlevad: „Karatsuba algoritm on kiire korrutamisalgoritm. Anatoli Karatsuba avastas 1960. aastal ja avaldas 1962. aastal. Pärast seda ei jäänud muud üle kui kaks ja kaks liita.

Tulevikus tahaksin leida olulisema vea, eriti Knuthi koodis. Samuti tahaksin leida vea põhialgoritmide esimesest köitest. Võib-olla oleksin selle leidnud, aga millegipärast on kohalikus raamatukogus ainult 2., 3. ja 4A köide.

Finantsfaktid:

• Kokku koosneb minu panus TAOCP-sse vaid kolmest tähemärgist: ühest täiendusest s, asendamine m edasi n и 2 edasi 0. 2,56 dollariga on need üsna tulusad sümbolid; Kui teile makstaks sellist raha, teeniks 1000-sõnaline artikkel (keskmiselt neli tähemärki) kümme tuhat.
• Kolme kuueteistkümnenddollariga jagan mina koos 29 teise kodanikuga San Serriffi panga rikkaimate hoiustajate edetabelis 69. kohal (seisuga 1. mai 2019).

Muud arutelud Knuthi tšekkide kohta

• Kuidas saada Knuthilt tšekki

  Üldised soovitused vigade leidmiseks Knuthi raamatutest. Enamasti puudutavad need tehnilisi vigu, mida mul ei ole. Seal on üks ettepanek, mida ma tõsiselt võtsin:

  Parim on oodata, kuni olete esitamiseks vead kogunud. Kombineerides mitu tõelist, kuid mitte väga väärtuslikku viga, suurendate tõenäosust, et ühte neist peetakse tegelikult veaks või nõuandeks. Kui esitate vead ükshaaval, võidakse igaüks eraldi tagasi lükata.

  Ma ei tahtnud saata lihtsalt jaburaid kirjavigu, vaid võtsin nõu kuulda ja saatsin kirja alles siis, kui leidsin ajaloolise vea, mis tundus piisavalt tõsine.

• Ashutosh Mehra tšekid

  Ashutosh Mehra on San Serriffi rikkuselt kolmas investor, kelle BoSS-i netoväärtus on 0x207,f0 dollarit.

• Kontrollige tegelikus TeX-koodis mõningaid mittefunktsionaalseid vigu
• Muu: #1 #2 #3 #4 #5 #6

Allikas: www.habr.com