Donald Knuth è un accademico nel campo dell'informatica, che si preoccupa così tanto della correttezza dei suoi libri che offre un dollaro esadecimale ($2,56, 0x$1,00) per qualsiasi "errore" trovato, dove per errore si intende tutto ciò che è "tecnicamente, storicamente, tipograficamente o politicamente scorretto". Volevo davvero ricevere un assegno da Knuth, così ho deciso di cercare errori nella sua opera eccezionale "L'arte della programmazione" (TAOCP). Sono riuscito a trovarne tre. D'accordo con la parola, Knuth ha inviato un assegno per 0x$3,00.

Come puoi vedere, questo non è un vero assegno. Un tempo Knuth inviava assegni veri, ma ha smesso nel 2008 a causa di frode sfrenata. Ora invia "certificati di deposito personali" presso la banca San Seriffe (BoSS). Dice che è pronto a inviare denaro reale se necessario, ma sembra che sia troppo complicato.

Ho trovato due refusi e un errore storico. Li elencherò in ordine di complessità decrescente.

Refuso n. 1

Il primo refuso si trova a pagina 392 del terzo volume "Ordinamento e ricerca", ottava riga dal fondo: "Dopo una ricerca infruttuosa a volte (sometime) è preferibile inserire nella tabella una nuova voce che contiene K; il metodo che fa questo si chiama algoritmo di ricerca e inserimento. L'errore è che invece di sometime dovrebbe essere sometimes.

Certo, non c'è nulla di sorprendente in un errore del genere. Solo in questo articolo ci saranno sicuramente un paio di refusi (nessun premio per trovarli). Ciò che è davvero sorprendente è quanto tempo ci sia voluto per notarli. La pagina 392 non è sepolta profondamente nella sezione di matematica, è la prima pagina del sesto capitolo "Ricerca"! Forse una delle sezioni più lette del libro. Idealmente, lì ci dovrebbero essere il minor numero di refusi, ma non è così.

A proposito, se hai mai pensato di leggere TAOCP, prova. Molti diranno che è un manuale, non destinato alla lettura diretta, ma non è vero. L'autore ha una chiara visione e uno stile distintivo. L'unica cosa che ostacola la leggibilità è la complessità della matematica. Tuttavia, c'è una soluzione semplice: leggi finché non arrivi alla matematica che non comprendi, saltala e apri il prossimo capitolo che puoi comprendere. Leggendo in questo modo, salto almeno l'80% del libro, ma il restante 20% è magnifico!

Si dice anche che TAOCP sia irrilevante, obsoleta o in altro modo non applicabile alla «programmazione reale». Anche questo è falso. Ad esempio, nella prima sezione dopo l'introduzione si tratta della ricerca di un elemento in un array non ordinato. L'algoritmo più semplice è conosciuto da tutti i programmatori. Avvia il puntatore all'inizio dell'array, quindi esegui i seguenti passaggi in un ciclo:

1. Controlla se l'elemento attuale è quello desiderato. Se sì, restituiscilo; altrimenti
2. Controlla se il puntatore è fuori dai limiti dell'array. Se sì, restituisci un errore; altrimenti
3. Incrementa il puntatore e continua.

Ora consideriamo: quante verifiche dei limiti richiede in media questo algoritmo? Nel caso peggiore, quando l'array non contiene l'elemento, per ogni elemento della lista sarà necessaria una verifica, e in media sarà qualcosa del genere . Un algoritmo di ricerca più intelligente può richiedere solo una verifica dei limiti. Aggiungi l'elemento desiderato alla fine dell'array, quindi avvia il puntatore all'inizio dell'array e segui i seguenti passaggi in un ciclo:

1. Controlla se l'elemento attuale è quello desiderato. Se sì, restituisci la risposta se il puntatore è all'interno dell'array, o un errore se non lo è. Altrimenti
2. Incrementa il puntatore e continua.

In ogni caso, l'elemento sarà sicuramente trovato, e la verifica dei limiti viene eseguita solo una volta, quando ciò accade. È un'idea profonda, ma è abbastanza semplice anche per un programmatore principiante. Probabilmente non posso parlare della rilevanza del lavoro per gli altri, ma sono riuscito a applicare immediatamente questa saggezza sia nel codice personale che in quello professionale. Il libro TAOCP è pieno di tali gemme (per essere giusti, ci sono anche molte cose strane, come l'ordinamento a bolle).

«Cerca, cerca
Tanto tempo fa
Cerca, cerca
Volevo solo ballare»
— Luther Vandross, «Cerca» (1980)

Refuso n. 2

Il secondo refuso è nel volume 4A, "Algoritmi combinatori", parte 1. A pagina 60 viene descritta una questione riguardante la programmazione delle esibizioni dei comici in vari casinò. Come esempio vengono citati alcuni comici reali, tra cui Lily Tomlin, Weird Al Yankovic e Robin Williams, che era ancora vivo quando il libro è stato pubblicato. Knuth include sempre i nomi completi nell'indice, quindi Williams è menzionato a pagina 882 come "Williams, Robin Mac-Laurin". Ma il suo secondo nome finisce con "n" e non con "m", ovvero Mac-Laurin.

Mac-Laurin è il cognome da nubile di sua madre. Era bisnipote di Anselmo Giuseppe Mac-Laurin, 34° governatore del Mississippi. Il suo mandato, evidentemente, non è ricordato per nulla di buono. Dalla libro "Mississippi: storia":

"L'evento più importante durante l'amministrazione di Mac-Laurin fu la dichiarazione di guerra della Repubblica degli Stati Uniti contro la Spagna nella primavera del 1898... Sfortunatamente, la guerra potrebbe aver dato a alcuni funzionari statali l'opportunità di praticare corruzione. Mac-Laurin fu accusato di varie pratiche dubbie, tra cui il nepotismo e un uso eccessivo dei poteri di grazia. Durante l'epoca del movimento per la sobrietà, i critici accusarono il governatore di ubriachezza, cosa che egli ammise pubblicamente."

Errore storico

Consideriamo l'algoritmo tradizionale della moltiplicazione dalla programma scolastica. Quante operazioni di moltiplicazione a cifra singola richiede? Supponiamo che tu stia moltiplicando -un numero a in -cifre . Prima moltiplichi la prima cifra per ogni cifra a turno. Poi moltiplichi la seconda cifra per ogni cifra a turno e così via, fino a quando non hai trattato tutte le cifre . In questo modo, la moltiplicazione tradizionale richiede moltiplicazioni primitive. In particolare, moltiplicare due numeri di cifre richiede moltiplicazioni a cifra singola.

Questo è negativo, ma è possibile ottimizzare il processo con il metodo sviluppato dal matematico sovietico Anatoly Alexeyevich Karatsuba. Supponiamo che e  siano numeri decimali a due cifre; cioè ci sono numeri , , , tali che e (generalizzare questo algoritmo a numeri più grandi richiede alcune manovre; anche se non è troppo complicato, per non sbagliare nei dettagli, preferisco rimanere su un esempio semplice). Allora , , . La moltiplicazione di binomi dà . Fino a questo punto abbiamo ancora moltiplicazioni a cifra singola: , , , . Ora sommiamo e sottraiamo . Dopo diversi scambi, che lascerò come esercizio per il lettore, si ottiene  — solo tre moltiplicazioni a una cifra! (Ci sono alcuni coefficienti fissi, ma possono essere calcolati solo tramite somma e spostamento delle cifre).

Non chiedere prove, ma l'algoritmo di Karatsuba (generalizzato ricorsivamente dall'esempio sopra) migliora il metodo tradizionale di moltiplicazione da operazioni a . Si noti che questo è un reale miglioramento dell'algoritmo e non un'ottimizzazione per i calcoli mentali. Infatti, l'algoritmo non è adatto per il calcolo mentale, poiché richiede un notevole overhead per le operazioni ricorsive. Inoltre, l'effetto si manifesterà completamente solo quando i numeri diventeranno sufficientemente grandi (fortunatamente, al posto dell'algoritmo di Karatsuba sono arrivati metodi ancora più veloci: a marzo 2019 è stato pubblicato un algoritmo che richiede solo n log n moltiplicazioni; l'accelerazione è applicabile solo ai numeri inimmaginabilmente grandi).

Questo algoritmo è descritto a pagina 295 del secondo volume di «Algoritmi Semiconvertibili». Lì Knuth scrive: «Curiosamente, questa idea è stata scoperta solo nel 1962 anno», quando è stato pubblicato un articolo che descrive l'algoritmo di Karatsuba. Ma! Nel 1995 Karatsuba ha pubblicato un articolo «La complessità dei calcoli», in cui dice alcune cose: 1) intorno al 1956, Kolmogorov ha ipotizzato che la moltiplicazione non possa essere effettuata in meno di passi; 2) nel 1960 anno Karatsuba era presente a un seminario in cui Kolmogorov ha esposto la sua ipotesi n². 3) «Esattamente una settimana» Karatsuba ha sviluppato l'algoritmo «divide et impera»; 4) nel 1962 Kolmogorov ha scritto e pubblicato un articolo a nome di Karatsuba con la descrizione dell'algoritmo. «Ho saputo di questo articolo solo dopo che è stato ripubblicato».

Quindi, l'errore è che invece di 1962 dovrebbe essere indicato 1960 l'anno. Questo è tutto.

Analisi

La ricerca degli errori non richiedeva particolare abilità.

1. Il primo errore era così banale che era possibile e si trovava in una posizione relativamente evidente (all'inizio del capitolo). Qualsiasi idiota l'avrebbe trovato; semplicemente io sono stato quell'idiota.
2. La ricerca del secondo refuso richiedeva fortuna e impegno, ma non abilità. L'indice per "Williams" si trova sulla penultima pagina del volume, una parte piuttosto evidente del libro. Stavo proprio sfogliando l'indice (non è così male come sembra, perché negli indici di Knuth ci sono uova di pasqua nascoste. Ad esempio, ci sono voci in arabo ed ebraico, e entrambe indicano pagina 66. Ma in quella pagina non viene menzionata nessuna delle lingue; viene invece menzionata "languaggi che si leggono da destra a sinistra"). E la mia attenzione è stata attratta dal secondo nome. Poiché leggo spesso Wikipedia, ho controllato Robin Williams e ho notato una discrepanza.
3. Vorrei poter dire che ho condotto una seria ricerca per trovare un errore storico, ma in realtà ho semplicemente guardato la pagina di Wikipedia sull'algoritmo di Karatsuba. Nelle prime righe si legge: "L'algoritmo di Karatsuba è un algoritmo di moltiplicazione rapida. Scoperto da Anatolij Karatsuba nel 1960 e pubblicato nel 1962". Dopo di che, rimaneva solo da sommare due più due.

In futuro vorrei trovare un errore più sostanziale, specialmente nel codice di Knuth. Vorrei anche trovare un bug nel primo volume "Algoritmi fondamentali". Forse l'avrei trovato, ma nella biblioteca locale, per qualche motivo, ci sono solo i volumi 2, 3 e 4A.

Fatti finanziari:

• In totale, il mio contributo a TAOCP consiste solo in tre simboli: un'aggiunta s, una sostituzione m in n e 2 in 0. Al prezzo di $2,56, sono simboli piuttosto redditizi; se ti pagando tali somme, un articolo di 1000 parole (in media, circa quattro simboli) ti darebbe dieci pezzi.
• Con tre dollari e sedici centesimi, insieme ad altri 29 cittadini, condivido il 69° posto nella lista dei più ricchi investitori della banca San Seriff (a partire dal 1 maggio 2019).

Altre discussioni sui controlli di Knuth

• Come ottenere un controllo da Knuth

  Raccomandazioni generali per la ricerca di errori nei libri di Knuth. Riguardano principalmente errori tecnici, che non ho. C'è una frase che ho preso sul serio:

  È meglio aspettare di raccogliere un insieme di errori da inviare. Combinando alcuni errori reali, ma non molto significativi, aumenterai la possibilità che uno di essi venga effettivamente considerato un errore o un consiglio. Se invii errori uno per uno, ognuno può essere rifiutato singolarmente.

  Non volevo inviare semplici errori insignificanti, ma ho seguito il consiglio e ho inviato la lettera solo quando ho trovato un errore storico che mi è sembrato abbastanza serio.

• Asciutto Ashot Mushra

  Ashot Mushra è il terzo investitore più ricco di San-Serriff con un patrimonio colossale di 0x$207,f0 in BoSS.

• Ricevuta per alcuni errori non funzionali nel codice reale di TeX
• Varie: #1 #2 #3 #4 #5 #6

Fonte: habr.com