Donald Knuth estas komputikisto, kiu tiom zorgas pri la precizeco de siaj libroj, kiun li sugestas unu seksa dolaro ($2,56, 0x$1,00) por iu ajn "eraro" trovita, kie eraro estas difinita kiel io ajn kio estas "teknike, historie, tipografie aŭ politike malĝusta." Mi tre volis ricevi ĉekon de Knuth, do mi decidis serĉi erarojn en lia plej granda verko. "La Arto de Programado" (TAOCP). Ni sukcesis trovi tri. Fidela al lia vorto, Knut sendis ĉekon por 0x $3,00.

Kiel vi povas vidi, ĉi tio ne estas vera kontrolo. Knuth kutimis sendi verajn ĉekojn, sed ĉesis en 2008 pro senbrida fraŭdo. Li nun sendas "personajn atestojn pri deponejo" al Banko de San Serriff (Estro). Li diras, ke li pretas sendi realan monon se necese, sed ŝajnas, ke ĝi estas tro ĝena.

Mi trovis du tajperarojn kaj unu historian eraron. Mi listigos ilin en ordo de malkreskanta bagatelo.

Preskribo numero 1

La unua tajperaro troviĝas sur paĝo 392 de la tria volumo “Ordigo kaj Serĉo”, oka linio de la malsupro: “Post malsukcesa serĉo, foje (foje) estas dezirinde enigi novan rekordon en la tabelon enhavantan. K; la metodo kiu faras tion estas nomita la serĉo kaj enigo algoritmo. La eraro estas tio anstataŭe iam devus esti kelkfoje.

Kompreneble, tia eraro ne estas surpriza. Nepre estos kelkaj tajperaroj en ĉi tiu artikolo sole (neniu rekompenco por trovi ilin). Kio estas vere surpriza estas ke ĝi pasis nerimarkita tiel longe. Paĝo 392 ne estas enterigita profunde en la matematika sekcio, ĝi estas la unua paĝo Ĉapitro XNUMX "Serĉo"! Eble unu el la plej legataj sekcioj de la libro. En teorio, devus esti la plej malmultaj tajperaroj, sed ne.

Cetere, se vi iam pensis pri legi TAOCP, provu ĝin. Multaj diros, ke tio estas dosierujo, ne destinita por rekta legado, sed tio ne estas vera. La aŭtoro havas klaran vidpunkton kaj distingan stilon. La nura afero, kiu malhelpas legeblecon, estas la komplekseco de la matematiko. Tamen, ekzistas simpla solvo: legu ĝis vi venos al matematiko, kiun vi ne komprenas, preterlasu ĝin, kaj iru al la sekva sekcio, kiun vi povas kompreni. Tiel legante, mi sopiras almenaŭ 80% de la libro, sed la aliaj 20% estas bonega!

Estas ankaŭ dirite ke TAOCP senrilata, estas malmoderna aŭ alie ne aplikebla al "reala programado". Ĉi tio ankaŭ ne estas vera. Ekzemple, la unua sekcio post la enkonduko rigardas trovi elementon en neordigita tabelo. La plej simpla algoritmo estas konata al ĉiuj programistoj. Komencu la montrilon ĉe la komenco de la tabelo, tiam faru la jenon en buklo:

1. Kontrolu ĉu la nuna elemento estas la dezirata. Se jes, ni resendas ĝin; alie
2. Kontrolu ĉu la montrilo estas ekster la tabellimo. Se jes, resendu eraron; alie
3. Zomu kaj daŭrigu.

Nun konsideru: kiom da limkontroloj postulas ĉi tiu algoritmo, averaĝe? En la plej malbona kazo, kie la tabelo ne enhavas elementon, ĉiu elemento en la listo postulos unu kontrolon, kaj averaĝe ĝi estos io kiel . Pli inteligenta serĉalgoritmo povus sukcesi per nur unu limkontrolo. Aligu la deziratan elementon al la fino de la tabelo, tiam komencu la montrilon ĉe la komenco de la tabelo kaj faru la jenon en buklo:

1. Kontrolu ĉu la nuna elemento estas la dezirata. Se jes, ni resendas respondon se la montrilo estas ene de la tabelo, aŭ eraron se ĝi ne estas. Alie
2. Zomu kaj daŭrigu.

Unu maniero aŭ alia, la elemento estas garantiita por esti trovita, kaj la limoj-kontrolo estas farita nur unufoje kiam tio okazas. Ĉi tio estas profunda ideo, sed ĝi estas sufiĉe simpla eĉ por komencanta programisto. Mi verŝajne ne povas paroli pri la graveco de la laboro al aliaj, sed mi tuj povis apliki ĉi tiun saĝon al kaj persona kaj profesia kodo. La libro TAOCP estas plena de tiaj gemoj (juste, estas ankaŭ multaj strangaĵoj tie, kiel ekzemple bobelspeco).

"Serĉu, serĉu
Ĝis la revido
Serĉu, serĉu
Mi nur volis danci"
- Luther Vandross, "La Serĉo" (1980)

Preskribo numero 2

La dua tajperaro estas en Volumo 4A, Combinatorial Algorithms, Part 1. Paĝo 60 priskribas problemon pri planado de komikuloj por prezenti ĉe diversaj kazinoj. Pluraj realvivaj komikuloj estas cititaj kiel ekzemploj, inkluzive de Lily Tomlin, Weird Al Yankovic, kaj Robin Williams, kiu daŭre estis vivanta kiam la libro estis publikigita. Knuth ĉiam listigas plenajn nomojn en la indekso, do Williams estas listigita sur paĝo 882 kiel "Williams, Robin McLorim." Sed lia meza nomo finiĝas per "n" kaj ne "m", tio estas, McLaurin.

McLaurin estis la naksnomo de sia patrino. Ŝi estis la pranepo de Anselm Joseph McLaurin, 34-a Guberniestro de Misisipo. Lia regado, ŝajne, ne estis memorita pro io bona. El libro "Misisipo: Historio":

„La plej grava evento dum la registaro de McLaurin estis la militdeklaro de Usono al Hispanio en la printempo de 1898... Bedaŭrinde, la milito eble donis al kelkaj registaraj oficistoj la ŝancon okupiĝi pri subaĉeto. McLaurin estis akuzita je diversaj kritikindaj praktikoj, inkluzive de nepotismo kaj troa uzo de pardonpotencoj. Dum la modereca movado, kritikistoj akuzis la guberniestron je esti drinkulo, kion li publike konfesis."

Historia eraro

Konsideru tradicia multiplika algoritmo de la lerneja instruplano. Kiom da unucifera multiplikoj ĝi postulas? Supozu, ke vi multiĝas -cifera nombro sur -bit . Unue multipliku la unuan ciferon por ĉiu cifero unu post la alia. Poste multigu la duan ciferon por ĉiu cifero unu post alia kaj tiel plu ĝis vi trapasos ĉiujn nombrojn . Tiel tradicia multipliko postulas primitivaj multiplikoj. Precipe, multiplikante du nombrojn per rangoj bezonataj unucifera multiplikoj.

Ĉi tio estas malbona, sed eblas optimumigi la procezon per metodo evoluigita de sovetia matematikisto Anatoly Alekseevich Karatsuba. Ni ŝajnigu tion и  - duciferaj decimalaj nombroj; tio estas, estas nombroj , , , tia ke и (Ĝeneraligi ĉi tiun algoritmon al pli grandaj nombroj postulas iom da manipulado; kvankam ĝi ne estas tro malfacila, por ne erari en la detaloj, mi pli bone restus je simpla ekzemplo). Tiam , , . Multobligi binomojn donas . Nuntempe ni ankoraŭ havas unucifera multipliko: , , , . Nun ni aldonu kaj subtrahi . Post kelkaj rearanĝoj, kiujn mi lasos kiel ekzercon por la leganto, rezultas  - nur tri unuciferaj multiplikoj! (Estas kelkaj konstantaj koeficientoj, sed ili povas esti kalkulitaj nur per aldono kaj movo de la ciferoj).

Ne petu pruvon, sed Algoritmo de Karatsuba (rekursie ĝeneraligita el la supra ekzemplo) plibonigas la tradician multiplika metodo kun operacioj antaŭe . Bonvolu noti, ke ĉi tio estas vera plibonigo de la algoritmo, ne optimumigo por mensaj kalkuloj. Efektive, la algoritmo ne taŭgas por mensa aritmetiko, ĉar ĝi postulas grandajn superkostojn por rekursiemaj operacioj. Krome, la efiko ne plene manifestiĝos ĝis la nombroj fariĝos sufiĉe grandaj (feliĉe, la algoritmo de Karatsuba estis anstataŭigita per eĉ pli rapidaj metodoj: en marto 2019, algoritmo estis publikigita, kiu postulas nur n log n multiplikoj; akcelo validas nur por neimageble grandaj nombroj).

Ĉi tiu algoritmo estas priskribita sur paĝo 295 de Volumo XNUMX, Semi-Numerical Algorithms. Tie Knuth skribas: “Estas kurioze, ke ĉi tiu ideo estis malkovrita nur en 1962 jaro", kiam artikolo priskribanta la algoritmon de Karatsuba estis publikigita. Sed! En 1995, Karatsuba publikigis artikolon "Komputika komplekseco", kiu diras plurajn aferojn: 1) ĉirkaŭ 1956, Kolmogorov sugestis ke multipliko ne povas esti farita en malpli ol paŝoj; 2) en 1960 jaro Karatsuba ĉeestis la seminarion kie Kolmogorov prezentis sian hipotezon n². 3) "En ekzakte unu semajno," Karatsuba evoluigis la "dividu kaj konkeri" algoritmon; 4) en 1962 Kolmogorov verkis kaj publikigis artikolon nome de Karatsuba kun priskribo de la algoritmo. "Mi eksciis pri ĉi tiu artikolo nur post kiam ĝi estis reeldonita."

Do la eraro estas ke anstataŭ 1962 devas esti specifita 1960 jaro. Tio estas ĉio.

Анализ

Trovi erarojn ne postulis specialan kapablon.

1. La unua eraro estis kiel eble plej bagatela kaj estis en relative videbla loko (la komenco de la ĉapitro). Ĉiu idioto estus ĝin trovinta; Mi ĵus montriĝis esti tiu idioto.
2. Trovi la duan tajperaron postulis bonŝancon kaj diligentecon, sed ne lertecon. La indekso por "Williams" estas sur la antaŭlasta paĝo de la volumo, sufiĉe elstara parto de la libro. Mi ĵus foliumis la indekson (ĝi ne estas tiel kompatinda kiel ĝi sonas, ĉar estas paskaj ovoj kaŝitaj en la indeksoj de Knuth. Ekzemple, estas enskriboj en la araba kaj la hebrea, ambaŭ montrante paĝon 66. Sed tiu paĝo ne mencias. ambaŭ lingvoj; anstataŭe ĝi rilatas al "lingvoj, kiujn oni legas de dekstre al maldekstre"). Kaj la dua nomo kaptis mian atenton. Ĉar mi kutime legas Vikipedion, mi kontrolis Robin Williams kaj rimarkis malkongruon.
3. Mi ŝatus diri, ke mi serioze esploris por trovi historian eraron, sed vere mi nur rigardis Vikipedia paĝo pri la algoritmo de Karatsuba. La unuaj linioj diras: "La algoritmo de Karatsuba estas algoritmo de rapida multipliko. Malkovrite fare de Anatoly Karatsuba en 1960 kaj publikigita en 1962." Post tio restis nur aldoni du kaj du.

Estonte mi ŝatus trovi pli signifan cimon, precipe en la kodo de Knuth. Mi ŝatus ankaŭ trovi eraron en la unua volumo de Fundamentaj Algoritmoj. Eble mi estus trovinta ĝin, sed ial la loka biblioteko havas nur volumojn 2, 3 kaj 4A.

Financaj faktoj:

• Entute mia kontribuo al TAOCP konsistas el nur tri signoj: unu aldono s, anstataŭaĵo m sur n и 2 sur 0. Je $ 2,56, ĉi tiuj estas sufiĉe enspezigaj simboloj; Se oni pagus al vi tian monon, artikolo de 1000 vortoj (averaĝe kvar signoj) gajnus al vi dek milojn.
• Kun tri deksesuma dolaro, mi, kune kun 29 aliaj civitanoj, estas ligita al la 69-a loko en la listo de la plej riĉaj deponantoj de la San Serriff Bank (de la 1-a de majo 2019).

Aliaj diskutoj pri ĉekoj de Knuth

• Kiel ricevi ĉekon de Knuth

  Ĝeneralaj rekomendoj por trovi erarojn en la libroj de Knuth. Plejparte ili koncernas teknikajn erarojn, kiujn mi ne havas. Estas unu sugesto tie, kiun mi prenis serioze:

  Plej bone estas atendi ĝis vi kolektis aron da eraroj por sendi. Kombinante plurajn realajn sed ne tre valorajn erarojn, vi pliigas la verŝajnecon, ke unu el ili efektive estos rigardata kiel eraro aŭ konsilo. Se vi sendas erarojn unuope, ĉiu individue povas esti malakceptita.

  Mi ne volis sendi nur sensencaĵojn tajperarojn, sed prenis la konsilon kaj sendis la leteron nur kiam mi trovis historian eraron, kiu ŝajnis sufiĉe grava.

• La ĉekoj de Ashutosh Mehra

  Ashutosh Mehra estas la tria plej riĉa investanto en San Serriff kun enorma neta valoro de 0x$207.f0 en BoSS.

• Kontrolu iujn nefunkciajn cimojn en reala TeX-kodo
• Miscellaneous: #1 #2 #3 #4 #5 #6

fonto: www.habr.com