Donald Knuth ay isang computer scientist na labis na nagmamalasakit sa katumpakan ng kanyang mga aklat na iminumungkahi niya isang hex dollar ($2,56, 0x$1,00) para sa anumang "error" na natagpuan, kung saan ang isang error ay tinukoy bilang anumang bagay na "teknikal, historikal, typographically, o politically hindi tama." Gusto ko talagang makakuha ng tseke mula kay Knuth, kaya nagpasya akong maghanap ng mga pagkakamali sa kanyang magnum opus "Ang Sining ng Programming" (TAOCP). Nakahanap kami ng tatlo. Tapat sa kanyang salita, nagpadala si Knut ng tseke para sa 0x$3,00.
Tulad ng nakikita mo, hindi ito isang tunay na tseke. Dati nagpapadala si Knuth ng mga totoong tseke, ngunit huminto noong 2008 dahil sa . Nagpapadala na siya ngayon ng "mga personal na sertipiko ng deposito" sa (BoSS). Willing daw siyang magpadala ng totoong pera kung kinakailangan, pero parang masyadong hassle.
May nakita akong dalawang typo at isang historical error. Ililista ko ang mga ito sa pagkakasunud-sunod ng pagbabawas ng mga bagay na walang kabuluhan.
Typo #1
Ang unang typo ay nasa pahina 392 ng ikatlong volume ng "Pag-uuri at Paghahanap", ikawalong linya mula sa ibaba: "Pagkatapos ng isang hindi matagumpay na paghahanap, kung minsan (minsan) ito ay kanais-nais na magpasok ng isang bagong tala sa talahanayan na naglalaman ng K; ang paraan na gumagawa nito ay tinatawag na search and insert algorithm. Ang pagkakamali ay iyon sa halip minsan dapat kung minsan.
Siyempre, ang gayong pagkakamali ay hindi nakakagulat. Mayroong ilang mga typo sa artikulong ito lamang (walang gantimpala para sa paghahanap sa kanila). Ang talagang nakakagulat ay hindi ito napansin ng napakatagal. Page 392 ay hindi nakabaon ng malalim sa seksyon ng matematika, ito ay ang pinakaunang pahina Kabanata XNUMX "Paghahanap"! Posibleng isa sa mga pinakabasang seksyon ng aklat. Sa teorya, dapat mayroong pinakamakaunting typo, ngunit hindi.
Oo nga pala, kung naisipan mo na magbasa ng TAOCP, subukan mo. Marami ang magsasabi na ito ay direktoryo, hindi inilaan para sa direktang pagbabasa, ngunit hindi ito totoo. Ang may-akda ay may malinaw na pananaw at isang natatanging istilo. Ang tanging bagay na humahadlang sa pagiging madaling mabasa ay ang pagiging kumplikado ng matematika. Gayunpaman, mayroong isang simpleng solusyon: basahin hanggang sa dumating ka sa matematika na hindi mo maintindihan, laktawan ito, at pumunta sa susunod na seksyon na mauunawaan mo. Sa ganitong paraan, nakakaligtaan ko ang hindi bababa sa 80% ng aklat, ngunit ang iba pang 20% ββay mahusay!
Sinasabi rin na TAOCP walang kinalaman, ay luma na o kung hindi man ay hindi naaangkop sa "tunay na programming". Hindi rin ito totoo. Halimbawa, ang unang seksyon pagkatapos ng pagpapakilala ay tumitingin sa paghahanap ng isang elemento sa isang hindi naayos na hanay. Ang pinakasimpleng algorithm ay pamilyar sa lahat ng mga programmer. Simulan ang pointer sa simula ng array, pagkatapos ay gawin ang sumusunod sa isang loop:
- Suriin kung ang kasalukuyang elemento ay ang nais. Kung gayon, ibinabalik namin ito; kung hindi
- Suriin kung ang pointer ay nasa labas ng hangganan ng array. Kung gayon, ibalik ang isang error; kung hindi
- Mag-zoom in at magpatuloy.
Ngayon isaalang-alang: kung gaano karaming mga bound check ang kinakailangan ng algorithm na ito, sa karaniwan? Sa pinakamasamang kaso, kung saan ang array ay hindi naglalaman ng isang elemento, ang bawat elemento sa listahan ay mangangailangan ng isang tseke, at sa karaniwan ito ay magiging katulad ng . Ang isang mas matalinong algorithm sa paghahanap ay maaaring makawala sa isang bounds check lamang. Ilakip ang gustong elemento sa dulo ng array, pagkatapos ay simulan ang pointer sa simula ng array at gawin ang sumusunod sa isang loop:
- Suriin kung ang kasalukuyang elemento ay ang nais. Kung gayon, nagbabalik kami ng tugon kung nasa loob ng array ang pointer, o isang error kung wala. Kung hindi
- Mag-zoom in at magpatuloy.
Sa isang paraan o iba pa, ang elemento ay garantisadong mahahanap, at ang bounds check ay isasagawa lamang kapag nangyari ito. Ito ay isang malalim na ideya, ngunit ito ay sapat na simple kahit para sa isang baguhan na programmer. Marahil ay hindi ako makapagsalita sa kaugnayan ng gawain sa iba, ngunit agad kong nailapat ang karunungan na ito sa parehong personal at propesyonal na code. Ang aklat ng TAOCP ay puno ng gayong mga hiyas (para maging patas, marami ring kakaibang bagay doon, tulad ng ).
"Hanapin, hanapin
Napakatagal
Maghanap, maghanap
Gusto ko lang sumayaw"
β Luther Vandross, "The Search" (1980)
Typo #2
Ang pangalawang typo ay nasa Volume 4A, Combinatorial Algorithms, Part 1. Ang Pahina 60 ay naglalarawan ng problemang kinasasangkutan ng pag-iskedyul ng mga komedyante na magtanghal sa iba't ibang casino. Maraming mga komedyante sa totoong buhay ang binanggit bilang mga halimbawa, kasama sina Lily Tomlin, Weird Al Yankovic, at Robin Williams, na buhay pa noong nai-publish ang libro. Palaging nililista ni Knuth ang buong pangalan sa index, kaya nakalista si Williams sa pahina 882 bilang "Williams, Robin McLorim." Ngunit ang kanyang gitnang pangalan ay nagtatapos sa "n" at hindi "m", iyon ay, McLaurin.
McLaurin ang maiden name ng kanyang ina. Siya ang apo sa tuhod ni Anselm Joseph McLaurin, ika-34 na Gobernador ng Mississippi. Ang kanyang paghahari, tila, ay hindi naalala para sa anumang mabuti. Mula sa libro :
βAng pinakamahalagang kaganapan sa panahon ng administrasyong McLaurin ay ang deklarasyon ng digmaan ng Estados Unidos sa Espanya noong tagsibol ng 1898... Sa kasamaang palad, ang digmaan ay maaaring nagbigay ng pagkakataon sa ilang opisyal ng gobyerno na makisali sa panunuhol. Inakusahan si McLaurin ng iba't ibang mga kaduda-dudang gawain, kabilang ang nepotismo at labis na paggamit ng mga kapangyarihan ng pagpapatawad. Sa panahon ng kilusan ng pagtitimpi, inakusahan ng mga kritiko ang gobernador bilang isang lasenggo, na inamin niya sa publiko.β
Makasaysayang pagkakamali
Isaalang-alang tradisyonal na algorithm ng pagpaparami mula sa kurikulum ng paaralan. Ilang single-digit multiplications ang kailangan nito? Kunwari dumami ka -digit na numero sa -bit . I-multiply muna ang unang digit para sa bawat digit isa-isa. Pagkatapos ay i-multiply ang pangalawang digit para sa bawat digit isa-isa at iba pa hanggang sa mapuntahan mo ang lahat ng numero . Kaya kailangan ng tradisyunal na pagpaparami primitive multiplications. Sa partikular, ang pagpaparami ng dalawang numero sa pamamagitan ng kinakailangan ang mga ranggo single-digit multiplications.
Ito ay masama, ngunit posible na i-optimize ang proseso gamit ang isang pamamaraan na binuo ng Soviet mathematician na si Anatoly Alekseevich Karatsuba. Magpanggap na tayo ΠΈ - dalawang-digit na decimal na numero; ibig sabihin, may mga numero , , , ganyan ΠΈ (Ang pag-generalize ng algorithm na ito sa mas malalaking numero ay nangangailangan ng ilang pagmamanipula; kahit na hindi ito masyadong mahirap, upang hindi magkamali sa mga detalye, mas mabuting manatili ako sa isang simpleng halimbawa). Pagkatapos , , . Nagbibigay ang pagpaparami ng binomials . Sa ngayon meron pa tayo single-digit multiplication: , , , . Ngayon dagdagan at ibawas natin . Pagkatapos ng ilang muling pagsasaayos, na aking iiwan bilang isang ehersisyo para sa mambabasa, ito ay lumalabas - tatlong single-digit multiplications lang! (May ilang pare-parehong coefficient, ngunit maaari lamang silang kalkulahin sa pamamagitan ng pagdaragdag at paglilipat ng mga digit).
Huwag humingi ng patunay, ngunit Algoritmo ng Karatsuba (recursively generalized mula sa halimbawa sa itaas) nagpapabuti sa tradisyonal na paraan ng pagpaparami sa mga operasyon noon . Pakitandaan na ito ay isang tunay na pagpapabuti sa algorithm, hindi isang pag-optimize para sa mga pagkalkula ng isip. Sa katunayan, ang algorithm ay hindi angkop para sa mental na arithmetic, dahil nangangailangan ito ng malalaking gastos sa overhead para sa mga recursive na operasyon. Bilang karagdagan, ang epekto ay hindi ganap na magpapakita mismo hanggang sa ang mga numero ay maging sapat na malaki (sa kabutihang palad, ang algorithm ng Karatsuba ay napalitan ng mas mabilis na mga pamamaraan: noong Marso 2019, isang algorithm ang nai-publish na nangangailangan lamang ng pagpaparami; ang acceleration ay nalalapat lamang sa hindi maisip na malalaking numero).
Ang algorithm na ito ay inilarawan sa pahina 295 ng Volume XNUMX, Semi-Numerical Algorithms. Doon ay sumulat si Knuth: βNakaka-curious na ang ideyang ito ay natuklasan lamang sa 1962 taon,β nang ang isang artikulong naglalarawan sa algorithm ng Karatsuba ay nai-publish. Ngunit! Noong 1995, naglathala si Karatsuba ng isang papel na "Computational Complexity", na nagsasabi ng ilang bagay: 1) noong 1956, iminungkahi ni Kolmogorov na ang pagpaparami ay hindi maaaring gawin nang mas mababa sa hakbang; 2) sa 1960 taon na dumalo si Karatsuba sa seminar kung saan ipinakita ni Kolmogorov ang kanyang hypothesis nΒ². 3) "Sa eksaktong isang linggo," binuo ni Karatsuba ang "divide and conquer" algorithm; 4) noong 1962 nagsulat at naglathala ng artikulo si Kolmogorov sa ngalan ng Karatsuba na may isang paglalarawan ng algorithm. "Nalaman ko lang ang tungkol sa artikulong ito pagkatapos itong mai-publish muli."
Kaya ang error ay na sa halip na 1962 dapat tukuyin 1960 taon. Iyon lang.
Pagsusuri
Ang paghahanap ng mga error ay hindi nangangailangan ng espesyal na kasanayan.
- Ang unang pagkakamali ay walang halaga hangga't maaari at nasa isang medyo nakikitang lugar (sa simula ng kabanata). Kahit sinong tanga ay masusumpungan ito; Ako lang pala ang tanga.
- Ang paghahanap ng pangalawang typo ay nangangailangan ng suwerte at sipag, ngunit hindi kasanayan. Ang index para sa "Williams" ay nasa penultimate page ng volume, isang medyo kitang-kitang bahagi ng libro. Binabalik-balikan ko lang ang index (hindi ganoon kaawa-awa ang sinasabi nito, dahil may mga Easter egg na nakatago sa mga index ni Knuth. Halimbawa, may mga entry sa Arabic at Hebrew, parehong tumuturo sa pahina 66. Ngunit hindi binabanggit ng pahinang iyon. alinman sa mga wika; sa halip ito ay tumutukoy sa "mga wika na binabasa mula kanan pakaliwa"). At ang pangalawang pangalan ang nakakuha ng atensyon ko. Dahil karaniwan kong nagbabasa ng Wikipedia, sinuri ko si Robin Williams at napansin ko ang isang pagkakaiba.
- Gusto kong sabihin na gumawa ako ng seryosong pananaliksik upang makahanap ng isang makasaysayang pagkakamali, ngunit talagang tumingin lang ako . Ang pinakaunang mga linya ay nagsasabing: "Ang Karatsuba algorithm ay isang mabilis na multiplikasyon na algorithm. Natuklasan ni Anatoly Karatsuba noong 1960 at inilathala noong 1962." Pagkatapos nito ang natitira na lang ay magdagdag ng dalawa at dalawa.
Sa hinaharap, nais kong makahanap ng mas makabuluhang bug, lalo na sa code ni Knuth. Gusto ko ring makahanap ng bug sa unang volume ng Fundamental Algorithms. Marahil ay mahahanap ko ito, ngunit sa ilang kadahilanan ang lokal na aklatan ay mayroon lamang mga volume na 2, 3 at 4A.
Mga katotohanan sa pananalapi:
- Sa kabuuan, ang aking kontribusyon sa TAOCP ay binubuo lamang ng tatlong karakter: isang karagdagan s, kapalit m sa n ΠΈ 2 sa 0. Sa $2,56, ito ay ilang medyo kumikitang mga simbolo; Kung binayaran ka ng ganoong uri ng pera, ang isang artikulo ng 1000 salita (isang average ng apat na character) ay kikita ka ng sampung grand.
- Sa tatlong hexadecimal dollars, ako, kasama ang 29 na iba pang mamamayan, ay nakatali sa ika-69 na puwesto sa listahan ng pinakamayayamang depositor ng San Serriff Bank (mula noong Mayo 1, 2019).
Iba pang mga talakayan tungkol sa mga tseke mula kay Knuth
-
Pangkalahatang rekomendasyon para sa paghahanap ng mga error sa mga aklat ni Knuth. Kadalasan ay may kinalaman sila sa mga teknikal na pagkakamali, na wala ako. May isang mungkahi doon na sineseryoso ko:
Pinakamainam na maghintay hanggang sa makakolekta ka ng isang hanay ng mga error na isusumite. Sa pamamagitan ng pagsasama-sama ng ilang tunay ngunit hindi masyadong mahalagang mga error, pinapataas mo ang posibilidad na ang isa sa mga ito ay talagang ituring na isang pagkakamali o payo. Kung magsusumite ka ng mga error nang paisa-isa, maaaring tanggihan ang bawat isa.
Hindi ko nais na magpadala lamang ng walang kapararakan na mga typo, ngunit kinuha ang payo at ipinadala lamang ang sulat kapag nakakita ako ng isang makasaysayang pagkakamali na tila seryoso.
-
Si Ashutosh Mehra ay ang pangatlong pinakamayamang investor sa San Serriff na may napakalaking net worth na 0x$207.f0 sa BoSS.
- Miscellaneous:
Pinagmulan: www.habr.com