Donald Knuth hè un scientistu di l'informatica chì si preoccupa tantu di l'accuratezza di i so libri chì suggerisce un dollaru hex ($ 2,56, 0x $ 1,00) per ogni "errore" truvatu, induve un errore hè definitu cum'è qualcosa chì hè "tecnicu, storicamente, tipograficu, o puliticamenti sbagliatu". Vuliu veramente ottene un cuntrollu da Knuth, cusì aghju decisu di circà l'errori in u so opus magnum. "L'arte di prugrammazione" (TAOCP). Avemu riesciutu à truvà trè. Fidu à a so parolla, Knut hà mandatu un cuntrollu per 0x 3,00 $.

Comu pudete vede, questu ùn hè micca un veru cuntrollu. Knuth hà usatu per mandà veri cuntrolli, ma si firmò in 2008 per via di frode rampante. Avà manda "certificati persunali di depositu" à Banca di San Serriff (BoSS). Dice chì hè dispostu à mandà soldi veri se ne necessariu, ma pare chì hè troppu fastidiu.

Aghju trovu dui typos è un errore storicu. Li listeraghju in ordine di trivialità decrescente.

Typo #1

U primu typo hè in a pagina 392 di u terzu volumu "Sorting and Search", ottava linea da u fondu: "Dopu à una ricerca senza successu, à volte (qualchì volta) hè desideratu per inserisce un novu record in a tavula chì cuntene. K; u metudu chì face questu hè chjamatu algoritmu di ricerca è inserimentu. L'errore hè chì invece qualcuno deve esse Certi voti.

Di sicuru, un tali sbagliu ùn hè micca surprisante. Ci hè ubligatoriu di esse uni pochi di typos in questu articulu solu (senza ricumpensa per truvà elli). Ciò chì hè veramente surprisante hè chì hè passatu inosservatu per tantu tempu. A pagina 392 ùn hè micca intarrata prufonda in a sezione matematica, hè a prima pagina Capitulu XNUMX "Cerca"! Possibile una di e sezioni più leghjite di u libru. In teoria, ci duverebbe esse u menu typos, ma micca.

A propositu, se avete mai pensatu à leghje TAOCP, pruvate. Parechji diceranu chì questu hè annuariu, micca pensatu per a lettura diretta, ma questu ùn hè micca veru. L'autore hà un puntu di vista chjaru è un stilu distintivu. L'unicu ciò chì impedisce a leggibilità hè a cumplessità di a matematica. Tuttavia, ci hè una suluzione sèmplice: leghjite finu à vene à a matematica chì ùn avete micca capitu, saltate, è andate à a sezione dopu chì pudete capisce. Leghjendu cusì, mi manca almenu 80% di u libru, ma l'altru 20% hè grande!

Hè ancu dettu chì TAOCP irrilevante, hè obsoleta o altrimenti ùn hè micca applicabile à a "programmazione vera". Questu hè ancu micca veru. Per esempiu, a prima rùbbrica dopu l'intruduzioni cerca di truvà un elementu in un array senza sorte. L'algoritmu più simplice hè familiar à tutti i programatori. Accuminciate u puntatore à u principiu di l'array, dopu fate u seguitu in un ciclu:

1. Verificate se l'elementu attuale hè u desideratu. Sì cusì, u turnemu; altrimenti
2. Verificate se l'indicatore hè fora di u cunfini di l'array. Sì cusì, torna un errore; altrimenti
3. Zoom in è cuntinuà.

Avà cunsiderà: quanti cuntrolli di limiti richiede stu algoritmu, in media? In u peghju casu, induve l'array ùn cuntene micca un elementu, ogni elementu in a lista necessitarà un cuntrollu, è in media serà qualcosa cum'è . Un algoritmu di ricerca più intelligente puderia scappà cù una sola verificazione di limiti. Aghjunghjite l'elementu desideratu à a fine di l'array, poi cuminciate u punteru à u principiu di l'array è fate ciò chì segue in un ciclu:

1. Verificate se l'elementu attuale hè u desideratu. Sì cusì, vultemu una risposta se l'indicatore hè in l'array, o un errore s'ellu ùn hè micca. Altrimenti
2. Zoom in è cuntinuà.

In un modu o l'altru, l'elementu hè garantitu per esse truvatu, è u cuntrollu di i limiti hè realizatu solu una volta quandu questu succede. Questa hè una idea prufonda, ma hè abbastanza simplice ancu per un programatore principiante. Probabilmente ùn possu micca parlà di a rilevanza di u travagliu per l'altri, ma aghju subitu pudendu applicà sta saviezza à u codice persunale è prufessiunale. U libru TAOCP hè pienu di tali gemme (per esse ghjustu, ci sò ancu assai cose strane, cum'è sorte di bolle).

"Cerca, cerca
Tantu tempu
Cerca, cerca
Vuliu solu ballà "
- Luther Vandross, "A ricerca" (1980)

Typo #2

U sicondu typo hè in u Volume 4A, Algoritmi Combinatori, Part 1. A pagina 60 descrive un prublema chì implica a pianificazione di comici per fà in diversi casinò. Diversi comici di a vita reale sò citati cum'è esempi, cumprese Lily Tomlin, Weird Al Yankovic, è Robin Williams, chì era sempre vivu quandu u libru hè statu publicatu. Knuth sempre liste i nomi completi in l'indici, cusì Williams hè listatu in a pagina 882 cum'è "Williams, Robin McLorim". Ma u so nome mediu finisci cù "n" è micca "m", vale à dì, McLaurin.

McLaurin era u nomu di a so mamma. Era a bisnipote di Anselm Joseph McLaurin, 34th guvernatore di Mississippi. U so regnu, apparentemente, ùn era micca ricurdatu per nunda di bonu. Da u libru "Mississippi: Storia":

"L'avvenimentu più impurtante durante l'amministrazione McLaurin era a dichjarazione di guerra di i Stati Uniti à a Spagna in a primavera di u 1898... Sfurtunatamente, a guerra pò avè furnitu à certi ufficiali di u guvernu l'uppurtunità di participà à corruzzione. McLaurin hè statu accusatu di diverse pratiche discutibile, cumpresu u nepotismu è l'usu eccessivu di i puteri di pardonu. Au cours du mouvement de tempérance, les critiques ont accusé le gouverneur d'être un ivrogne, ce qu'il a reconnu publiquement.

Sbagliu storicu

Cunsigliate Algoritmu di multiplicazione tradiziunale da u curriculum di a scola. Quante multiplicazioni à una sola cifra ci vole ? Supponete chì vi multiplicate - numeru di cifru nantu - bit . Prima multiplicate u primu cifru per ogni cifru unu à unu. Allora multiplicate a seconda cifra per ogni cifru unu per unu è cusì finu à passà per tutti i numeri . Cusì a multiplicazione tradiziunale richiede multiplicazioni primitive. In particulare, multiplicà dui numeri per i ranghi necessarii multiplicazioni à una sola cifra.

Questu hè male, ma hè pussibule ottimisà u prucessu cù un metudu sviluppatu da u matematicu sovieticu Anatoly Alekseevich Karatsuba. Fingemu chì и  - numeri decimali di dui cifre; vale à dì, ci sò numeri , , , cusì chì и (Generalizà stu algoritmu à numeri più grande esige una certa manipulazione; ancu s'ellu ùn hè micca troppu difficiule, per ùn sbaglià micca in i ditaglii, aghju megliu stà à un esempiu simplice). Allora , , . A multiplicità di binomi dà . À u mumentu avemu sempre multiplicazione à una sola cifra: , , , . Avà aghjunghje è sottrae . Dopu qualchì riarrangiamentu, chì lasciaraghju cum'è un esercitu per u lettore, risulta  - solu trè multiplicazioni à una sola cifra! (Ci sò qualchi coefficienti custanti, ma ponu esse calculati solu aghjustendu è trasfurmà i numeri).

Ùn dumandate micca a prova, ma Algoritmu Karatsuba (recursively generalized da l 'esempiu sopra) migliurà nantu à u metudu di multiplicazione tradiziunale cù operazioni prima . Per piacè nutate chì questu hè un veru migliuramentu di l'algoritmu, micca una ottimisazione per i calculi mentali. Infatti, l'algoritmu ùn hè micca adattatu per l'aritmetica mentale, postu chì esige grandi costi per l'operazioni recursive. Inoltre, l'effettu ùn si manifestarà micca cumplettamente finu à chì i numeri diventanu abbastanza grande (per furtuna, l'algoritmu di Karatsuba hè statu rimpiazzatu da metudi ancu più veloci: in marzu 2019, un algoritmu hè statu publicatu chì richiede solu n log n multiplicazioni; l'accelerazione s'applica solu à numeri inimaginabilmente grandi).

Stu algoritmu hè discrittu in a pagina 295 di u Volume XNUMX, Algoritmi Semi-Numerichi. Quì Knuth scrive: "Hè curiosu chì sta idea hè stata scuperta solu in 1962 annu," quandu un articulu chì descrive l'algoritmu di Karatsuba hè statu publicatu. Ma! In u 1995, Karatsuba pubblicò un documentu "Computicality Complexity", chì dice parechje cose: 1) intornu à u 1956, Kolmogorov suggerì chì a multiplicazione ùn pò esse fatta in menu di menu. passi; 2) in 1960 annu Karatsuba hà assistitu à u seminariu induve Kolmogorov prisintò a so ipotesi n². 3) "In esattamente una settimana", Karatsuba hà sviluppatu l'algoritmu "divide è cunquistà"; 4) in u 1962 Kolmogorov hà scrittu è publicatu un articulu in nome di Karatsuba cù una descrizzione di l'algoritmu. "Aghju scupertu solu questu articulu dopu chì hè statu ripubblicatu".

Allora l'errore hè chì invece di 1962 deve esse specificatu 1960 annu. Eccu tuttu.

Analisi

Truvà l'errori ùn hà micca bisognu di cumpetenza speciale.

1. U primu errore era u più triviale pussibule è era in un locu relativamente visibile (u principiu di u capitulu). Qualchese idiota l'avaria trovu ; Sò solu diventatu quellu idiota.
2. Truvà u sicondu typo hà bisognu di furtuna è diligenza, ma micca di cumpetenza. L'indici per "Williams" hè nantu à a penultima pagina di u voluminu, una parte abbastanza prominente di u libru. Eru solu flipping through the index (ùn hè micca cusì pateticu cum'è si sona, perchè ci sò ova di Pasqua oculate in l'indici di Knuth. Per esempiu, ci sò entrate in arabu è ebraicu, tramindui chì indicanu a pagina 66. Ma quella pagina ùn dice micca. sia lingue; invece si riferisce à "lingue chì si leghjenu da a diritta à a manca"). È u sicondu nome hà pigliatu a mo attenzione. Siccomu di solitu leghje Wikipedia, aghju verificatu Robin Williams è nutatu una discrepanza.
3. Mi piacerebbe pudè dì chì aghju fattu una ricerca seria per truvà un errore storicu, ma veramente aghju vistu solu Pagina di Wikipedia nantu à l'algoritmu di Karatsuba. E prime linee dicenu: "L'algoritmu Karatsuba hè un algoritmu di multiplicazione veloce. Scupertu da Anatoly Karatsuba in u 1960 è publicatu in u 1962 ". Dopu tuttu ciò chì restava era di aghjunghje dui è dui.

In u futuru mi piacerebbe truvà un bug più significativu, in particulare in u codice di Knuth. Mi piacerebbe ancu truvà un bug in u primu voluminu di Algoritmi Fundamentali. Forse l'avaria trovu, ma per una certa ragione a biblioteca lucale hà solu i volumi 2, 3 è 4A.

Fatti finanziarii:

• In totale, a mo cuntribuzione à TAOCP hè custituita da solu trè caratteri: una aghjunta s, rimpiazzamentu m nantu n и 2 nantu 0. À $ 2,56, questi sò qualchi simboli abbastanza lucrativi; Sì avete pagatu stu tipu di soldi, un articulu di 1000 parolle (una media di quattru caratteri) vi guadagnà dece grandi.
• Cù trè dollari esadecimali, I, inseme à 29 altri citadini, sò attaccati à u 69u postu nantu à a lista di i più ricchi dipositori di u San Serriff Bank (da u 1 di maghju 2019).

Altre discussioni nantu à i cuntrolli da Knuth

• Cumu uttene un cuntrollu da Knuth

  Raccomandazioni generali per truvà errori in i libri di Knuth. A maiò parte si cuncernanu errori tecnichi, chì ùn aghju micca. Ci hè un suggerimentu quì chì aghju pigliatu in seriu:

  Hè megliu d'aspittà finu à chì avete cullatu un inseme di errori per mandà. Cumminendu parechji errori reali, ma micca assai preziosi, aumentate a probabilità chì unu di elli sia veramente cunsideratu cum'è un sbagliu o un cunsigliu. Se inviate l'errori unu à u tempu, ognunu pò esse rifiutatu individualmente.

  Ùn vulia micca mandà solu typos senza sensu, ma hà pigliatu u cunsigliu è mandatu a lettera solu quandu aghju trovu un errore storicu chì pareva abbastanza seriu.

• I cuntrolli di Ashutosh Mehra

  Ashutosh Mehra hè u terzu investitore più riccu in San Serriff cun un valore nettu enorme di 0x $ 207.f0 in BoSS.

• Verificate per alcuni bugs non funziunali in u veru codice TeX
• Miscellaneous: #1 #2 #3 #4 #5 #6

Source: www.habr.com