Donald Knuth se yon syantifik enfòmatik ki gen sousi anpil sou presizyon nan liv li yo ke li sijere yon dola hex ($2,56, 0x$1,00) pou nenpòt "erè" jwenn, kote yon erè defini kòm nenpòt bagay ki "teknikman, istorikman, tipografikman, oswa politikman kòrèk." Mwen te reyèlman vle jwenn yon chèk nan men Knuth, se konsa mwen deside chèche erè nan opus magnum li. "Atis nan pwogramasyon" (TAOCP). Nou te rive jwenn twa. Fidèl pawòl li, Knut voye yon chèk pou 0x $3,00.
Kòm ou ka wè, sa a se pa yon chèk reyèl. Knuth te konn voye chèk reyèl, men te sispann an 2008 akòz . Li kounye a voye "pèsonèl sètifika depo" bay (BoSS). Li di ke li dispoze voye lajan reyèl si sa nesesè, men li sanble ke li se twòp nan yon konplikasyon.
Mwen te jwenn de typo ak yon erè istorik. Mwen pral lis yo nan lòd yo diminye triviality.
Typo #1
Premye typo a se nan paj 392 twazyèm volim nan "Triyay ak rechèch", wityèm liy anba a: "Apre yon rechèch san siksè, pafwa (pafwa) li dezirab antre yon nouvo dosye nan tablo ki genyen K; metòd ki fè sa a rele algorithm rechèch ak insert. Erè a se sa pito nenpòt moman ta dwe pafwa.
Natirèlman, tankou yon erè se pa etone. Gen kèk erè nan atik sa a pou kont li (pa gen okenn rekonpans pou jwenn yo). Ki sa ki vrèman etone se ke li te pase inapèsi pou lontan. Paj 392 pa antere byen fon nan seksyon matematik la, li se premye paj la Chapit 6 "Rechèch"! Petèt youn nan seksyon ki pi li nan liv la. Nan teyori, ta dwe gen mwens typo yo, men non.
By wout la, si ou te janm panse sou li TAOCP, bay li yon eseye. Anpil moun pral di ke sa a se anyè, pa fèt pou lekti dirèk, men sa a se pa vre. Otè a gen yon pwen de vi klè ak yon style diferan. Sèl bagay ki anpeche lizibilite se konpleksite matematik la. Sepandan, gen yon solisyon senp: li jiskaske ou rive nan matematik ou pa konprann, sote li, epi ale nan pwochen seksyon ou ka konprann. Lekti nan fason sa a, mwen manke omwen 80% nan liv la, men lòt 20% nan se gwo!
Li te di tou ke TAOCP pa enpòtan, se demode oswa otreman pa aplikab nan "pwogram reyèl". Sa a se pa vre tou. Pou egzanp, premye seksyon an apre entwodiksyon an gade nan jwenn yon eleman nan yon etalaj ki pa klase. Algorithm ki pi senp la abitye ak tout pwogramè yo. Kòmanse konsèy la nan kòmansman etalaj la, apresa fè sa ki annapre yo nan yon bouk:
- Tcheke si eleman aktyèl la se youn nan vle. Si se konsa, nou retounen li; otreman
- Tcheke si konsèy la deyò fwontyè etalaj la. Si se konsa, retounen yon erè; otreman
- Zoom an epi kontinye.
Koulye a, konsidere: konbyen chèk limit algorithm sa a mande, an mwayèn? Nan ka ki pi mal la, kote etalaj la pa gen yon eleman, chak eleman nan lis la pral mande pou yon chèk, ak an mwayèn li pral yon bagay tankou . Yon algorithm rechèch pi entelijan ka jwenn lwen ak yon sèl chèk limit. Tache eleman vle a nan fen etalaj la, Lè sa a, kòmanse konsèy la nan kòmansman etalaj la epi fè sa ki annapre yo nan yon bouk:
- Tcheke si eleman aktyèl la se youn nan vle. Si se konsa, nou retounen yon repons si konsèy la nan etalaj la, oswa yon erè si li pa. Sinon
- Zoom an epi kontinye.
Yon fason oswa yon lòt, eleman an garanti yo dwe jwenn, epi tcheke limit yo fèt sèlman yon fwa lè sa rive. Sa a se yon lide pwofon, men li ase senp menm pou yon pwogramè inisyasyon. Mwen pwobableman pa ka pale sou enpòtans travay la bay lòt moun, men mwen te imedyatman kapab aplike sajès sa a nan tou de kòd pèsonèl ak pwofesyonèl. Liv TAOCP a plen ak bèl pyè koute chè (pou nou jis, gen tou anpil bagay dwòl ladan l, tankou ).
"Rechèch, rechèch
Se konsa lontan
Chèche, chèche
Mwen jis te vle danse"
- Luther Vandross, "Rechèch la" (1980)
Typo #2
Dezyèm typo a se nan Volim 4A, Algoritm Konbinatoryal, Pati 1. Paj 60 dekri yon pwoblèm ki enplike komedyen orè pou jwe nan divès kazino. Yo site plizyè komedyen reyèl kòm egzanp, tankou Lily Tomlin, Weird Al Yankovic, ak Robin Williams, ki te toujou vivan lè yo te pibliye liv la. Knuth toujou bay non konplè nan endèks la, kidonk Williams nan paj 882 lis kòm "Williams, Robin McLorim." Men, mitan non li fini ak "n" epi li pa "m", se sa ki, McLaurin.
McLaurin te non jenn fi manman l '. Li te gwo pitit fi Anselm Joseph McLaurin, 34yèm Gouvènè Mississippi. Rèy li, aparamman, pa te sonje pou anyen bon. Soti nan liv :
“Evènman ki pi enpòtan pandan administrasyon McLaurin an se te deklarasyon lagè Etazini te fè sou Espay nan sezon prentan 1898... Malerezman, lagè a ka bay kèk ofisyèl gouvènman opòtinite pou yo angaje yo nan kòripsyon. McLaurin te akize de plizyè pratik dout, ki gen ladan nepotism ak twòp itilizasyon pouvwa padon. Pandan mouvman tanperans lan, kritik yo te akize gouvènè a kòm yon tafyatè, sa li te admèt piblikman."
Erè istorik
Konsidere algorithm miltiplikasyon tradisyonèl yo soti nan kourikoulòm lekòl la. Konbyen miltiplikasyon yon sèl chif li mande? Sipoze ou miltipliye - nimewo chif sou -bit . Premye miltipliye premye chif la pou chak chif youn pa youn. Lè sa a, miltipliye dezyèm chif la pou chak chif youn pa youn ak sou sa jiskaske ou ale nan tout nimewo yo . Kidonk miltiplikasyon tradisyonèl mande miltiplikasyon primitif. An patikilye, miltipliye de nonb pa ran obligatwa miltiplikasyon yon sèl chif.
Sa a se move, men li posib pou optimize pwosesis la lè l sèvi avèk yon metòd devlope pa matematisyen Sovyetik Anatoly Alekseevich Karatsuba. Ann pran pòz sa и - nimewo desimal de chif; sa vle di, gen nimewo , , , tankou и (Jeneralize algorithm sa a nan pi gwo nimewo mande pou kèk manipilasyon; byenke li pa twò difisil, nan lòd yo pa fè erè nan detay yo, mwen pral pi bon rete sou yon egzanp senp). Lè sa a , , . Miltipliye binom bay . Nan moman sa a nou toujou genyen miltiplikasyon yon sèl chif: , , , . Koulye a, an n ajoute ak soustraksyon . Apre kèk rearanjman, ke mwen pral kite kòm yon egzèsis pou lektè a, li vire soti - sèlman twa miltiplikasyon yon sèl chif! (Gen kèk koyefisyan konstan, men yo ka sèlman kalkile lè yo ajoute ak deplase chif yo).
Pa mande prèv, men Algorithm Karatsuba (recursively jeneralize nan egzanp ki anwo a) amelyore sou metòd miltiplikasyon tradisyonèl la ak operasyon anvan . Tanpri sonje ke sa a se yon amelyorasyon reyèl nan algorithm la, pa yon optimize pou kalkil mantal. Vreman vre, algorithm la pa apwopriye pou aritmetik mantal, paske li mande gwo depans anlè pou operasyon repetitif. Anplis de sa, efè a pa pral konplètman manifeste jiskaske nimewo yo vin gwo ase (ererezman, algorithm Karatsuba a te ranplase pa metòd menm pi vit: nan mwa mas 2019, yo te pibliye yon algorithm ki mande sèlman miltiplikasyon; akselerasyon sèlman aplike nan nimewo inimajinabl gwo).
Yo dekri algorithm sa a nan paj 295 Volim XNUMX, Algoritm semi-nimerik. Gen Knuth ekri: "Li kirye ke lide sa a te dekouvri sèlman nan 1962 ane," lè yo te pibliye yon atik ki dekri algorithm Karatsuba a. Men! An 1995, Karatsuba te pibliye yon papye sou "Konpleksite enfòmatik", ki di plizyè bagay: 1) Anviwon 1956, Kolmogorov te sijere ke miltiplikasyon pa t 'kapab fèt nan mwens pase. etap; 2) nan 1960 ane Karatsuba te ale nan seminè a kote Kolmogorov te prezante ipotèz li n². 3) "Nan egzakteman yon semèn," Karatsuba devlope algorithm "divize ak konkeri"; 4) an 1962, Kolmogorov te ekri epi pibliye yon atik sou non Karatsuba ak yon deskripsyon algorithm la. "Mwen te sèlman jwenn enfòmasyon sou atik sa a apre li te pibliye ankò."
Se konsa, erè a se ke olye pou yo 1962 dwe espesifye 1960 ane. Se tout.
Analiz
Jwenn erè pa t mande konpetans espesyal.
- Premye erè a te trivial ke posib epi li te nan yon kote relativman vizib (nan kòmansman chapit la). Nenpòt moun sòt ta jwenn li; Mwen jis te tounen moun sòt sa.
- Jwenn dezyèm typo a mande chans ak dilijans, men se pa konpetans. Endèks la pou "Williams" se sou penultyèm paj volim nan, yon pati jistis enpòtan nan liv la. Mwen t ap fèk pase nan endèks la (li pa menm jan li sanble, paske gen ze Pak ki kache nan endis Knuth yo. Pa egzanp, gen antre nan arab ak ebre, tou de montre paj 66. Men, paj sa a pa mansyone. swa lang; olye li refere a "lang ki li de dwat a goch"). Epi dezyèm non an te atire atansyon m. Depi mwen konn li Wikipedya, mwen tcheke Robin Williams epi mwen remake yon diferans.
- Mwen swete mwen te kapab di mwen te fè rechèch serye pou jwenn yon erè istorik, men reyèlman mwen jis gade . Premye liy yo di: "Algorithm Karatsuba a se yon algorithm miltiplikasyon rapid. Anatoly Karatsuba te dekouvri an 1960 epi li te pibliye an 1962." Apre sa, tout sa ki te rete se te ajoute de ak de.
Nan tan kap vini an mwen ta renmen jwenn yon ensèk ki pi enpòtan, espesyalman nan kòd Knuth la. Mwen ta renmen tou jwenn yon ensèk nan premye volim Algoritm Fondamantal yo. Petèt mwen ta jwenn li, men pou kèk rezon bibliyotèk lokal la sèlman gen volim 2, 3 ak 4A.
Reyalite finansye:
- An total, kontribisyon mwen nan TAOCP konsiste de sèlman twa karaktè: yon sèl adisyon s, ranplasman m sou n и 2 sou 0. Nan $ 2,56, sa yo se kèk senbòl trè likratif; Si yo te peye w jan de lajan, yon atik de 1000 mo (an mwayèn kat caractères) ta fè ou dis grand.
- Avèk twa dola egzadesimal, mwen menm ansanm ak 29 lòt sitwayen yo mare pou 69yèm plas sou lis depo ki pi rich nan San Serriff Bank (apati 1ye me 2019).
Lòt diskisyon sou chèk soti nan Knuth
-
Rekòmandasyon jeneral pou jwenn erè nan liv Knuth yo. Sitou yo konsène erè teknik, ki mwen pa genyen. Gen yon sijesyon ke mwen te pran oserye:
Li pi bon pou tann jiskaske ou te kolekte yon seri erè pou soumèt. Lè w konbine plizyè erè reyèl, men ki pa gen anpil valè, ou ogmante chans pou youn nan yo aktyèlman ap konsidere kòm yon erè oswa yon konsèy. Si ou soumèt erè youn nan yon moman, yo ka rejte yo chak endividyèlman.
Mwen pa t 'vle voye jis typos san sans, men te pran konsèy la epi voye lèt la sèlman lè mwen te jwenn yon erè istorik ki te sanble ase grav.
-
Ashutosh Mehra se twazyèm envestisè ki pi rich nan San Serriff ak yon valè nèt 0x$207.f0 nan BoSS.
- Divè:
Sous: www.habr.com