Donald Knuth — un esperto nel campo dell'informatica, così attento alla correttezza dei suoi libri che offre un dollaro esadecimale ($2,56, 0x$1,00) per ogni "errore" trovato, dove un errore è considerato tutto ciò che è "tecnicamente, storicamente, tipograficamente o politicamente scorretto". Volevo davvero ricevere un assegno da Knuth, quindi ho deciso di cercare errori nella sua opera straordinaria "L'arte della programmazione" (TAOCP). Sono riuscito a trovare tre. A proposito, Knuth mi ha inviato un assegno di 0x$3,00.
Come vedete, non si tratta di un vero assegno. In passato Knuth inviava assegni reali, ma ha smesso nel 2008 a causa di . Ora invia "certificati di deposito personali" nella (BoSS). Dichiara di essere pronto ad inviare denaro reale se necessario, ma sembra che sia troppo complicato.
Ho trovato due refusi e un errore storico. Elencherò in ordine decrescente di banalità.
Refuso n. 1
Il primo refuso — a pagina 392 del terzo volume "Ordinamento e ricerca", ottava riga dal fondo: "Dopo una ricerca non riuscita, a volte (sometime) è consigliabile inserire nella tabella un nuovo record contenente K; il metodo che fa questo si chiama algoritmo di ricerca e inserimento. L'errore è che invece di qualche volta deve essere a volte.
Naturalmente, non c'è nulla di sorprendente in un simile errore. Solo in questo articolo ci saranno sicuramente alcuni refusi (nessun premio per trovarli). Ciò che è davvero sorprendente è che non siano stati notati per così tanto tempo. La pagina 392 non è sepolta profondamente nella sezione di matematica, è la prima pagina del sesto capitolo "Ricerca"! Potrebbe essere una delle sezioni più lette del libro. In teoria, dovrebbe avere il minor numero di refusi, ma non è così.
A proposito, se mai hai pensato di leggere TAOCP, prova. Molti diranno che è un manuale, non destinato alla lettura diretta, ma non è vero. L'autore ha un punto di vista chiaro e uno stile unico. L'unica cosa che ostacola la leggibilità è la complessità della matematica. Tuttavia, c'è una soluzione semplice: leggi finché non arrivi alla matematica che non capisci, saltala e passa alla sezione successiva che puoi comprendere. Leggendo in questo modo, salto almeno l'80% del libro, ma il restante 20% è magnifico!
Si dice anche che TAOCP non sia rilevante, obsoleta o in altro modo non applicabile alla «programmazione reale». Questo non è vero. Ad esempio, nella prima sezione dopo l'introduzione viene trattata la ricerca di un elemento in un array non ordinato. L'algoritmo più semplice è noto a tutti i programmatori. Posiziona il puntatore all'inizio dell'array, quindi esegui le seguenti operazioni in ciclo:
- Controlla se l'elemento corrente è quello desiderato. Se sì, restituiscilo; altrimenti
- Controlla se il puntatore è oltre la fine dell'array. Se sì, restituisci un errore; altrimenti
- Incrementa il puntatore e continua.
Ora consideriamo: quante verifiche dei limiti richiede mediamente questo algoritmo? Nel caso peggiore, quando l'array non contiene l'elemento, è necessaria una verifica per ogni elemento della lista, e mediamente sarà qualcosa del genere 
. Un algoritmo di ricerca più intelligente potrebbe richiedere solo un controllo dei limiti. Collega l'elemento desiderato alla fine dell'array, quindi posiziona il puntatore all'inizio dell'array e esegui le seguenti operazioni in ciclo:
- Controlla se l'elemento attuale è quello desiderato. Se sì, restituiamo la risposta se il puntatore è all'interno dell'array, oppure un errore se non lo è. Altrimenti
- Incrementa il puntatore e continua.
In ogni caso, l'elemento sarà sicuramente trovato e il controllo dei limiti viene effettuato solo una volta che ciò accade. È un'idea profonda, ma è abbastanza semplice anche per un programmatore alle prime armi. Probabilmente non posso parlare della rilevanza del lavoro per gli altri, ma sono riuscito a applicare immediatamente questa saggezza sia nel mio codice personale che professionale. Il libro TAOCP è pieno di tali gemme (per essere giusti, ci sono anche molte cose strane, come ).
«Cerca, cerca
Così a lungo
Cerca, cerca
Volevo solo ballare»
— Luther Vandross, «Cerca» (1980)
Errore #2
Il secondo errore si trova nel volume 4A, "Algoritmi combinatori", parte 1. A pagina 60 viene descritta una questione relativa alla programmazione delle esibizioni di comici in vari casinò. Vengono citati alcuni comici reali, tra cui Lily Tomlin, Weird Al Yankovic e Robin Williams, il quale era ancora in vita quando il libro è stato pubblicato. Knuth fornisce sempre i nomi completi nell'indice, quindi Williams viene menzionato a pagina 882 come "Williams, Robin Mac-Laurin". Ma il suo secondo nome finisce con 'n' e non con 'm', cioè Mac-Laurin.
Mac-Laurin è il cognome da nubile di sua madre. Era pronipote di Anselm Joseph Mac-Laurin, 34° governatore del Mississippi. Il suo mandato, evidentemente, non è ricordato per nulla di buono. Da "Mississippi: storia" :
«L'evento più significativo durante l'amministrazione di Mac-Laurin è stata la dichiarazione di guerra da parte degli Stati Uniti contro la Spagna nella primavera del 1898... Purtroppo, la guerra ha forse dato ad alcuni funzionari pubblici l'opportunità di esercitare corruzione. Mac-Laurin è stato accusato di varie pratiche discutibili, tra cui nepotismo e uso eccessivo dei poteri di grazia. In un'epoca di movimento per la sobrietà, i critici hanno accusato il governatore di alcolismo, cosa che egli ha pubblicamente riconosciuto».
Errore storico
Consideriamo l'algoritmo tradizionale di moltiplicazione che si insegna a scuola. Quante operazioni di moltiplicazione a una cifra richiede? Supponiamo che tu stia moltiplicando 
-cifra 
con 
-cifre 
. Per prima cosa, moltiplichi la prima cifra 
per ogni cifra 
a turno. Poi moltiplichi la seconda cifra 
per ogni cifra 
a turno e così via, finché non hai passato tutte le cifre 
. In questo modo, la moltiplicazione tradizionale richiede 
moltiplicazioni primitive. In particolare, la moltiplicazione di due numeri di 
cifre richiede 
moltiplicazioni a una cifra.
È una cosa negativa, ma il processo può essere ottimizzato grazie a un metodo sviluppato dal matematico sovietico Anatolij Alekseevič Karačub. Supponiamo che 
e 
ci siano numeri decimali a due cifre; ovvero ci sono numeri 
, 
, 
, 
tali che 
e 
(l'estensione di questo algoritmo a numeri più grandi richiede alcune manipolazioni; anche se non è troppo complicato, per evitare di sbagliare nei dettagli, preferisco rimanere su un esempio semplice). Allora 
, 
, 
. La moltiplicazione di binomi dà 
. Al momento abbiamo ancora 
moltiplicazioni a una cifra: 
, 
, 
, 
. Ora sommiamo e sottraiamo 
. Dopo alcune permutazioni, che lascerò come esercizio per il lettore, otteniamo 
— solo tre moltiplicazioni a una cifra! (Ci sono alcuni coefficienti costanti, ma si possono calcolare solo tramite addizione e spostamento di posizioni).
Non chiedete prove, ma l'algoritmo di Karačub (che è stato generalizzato ricorsivamente dall'esempio sopra) migliora il metodo tradizionale di moltiplicazione da 
operazioni a 
. Si prega di notare che questo è un reale miglioramento dell'algoritmo e non un'ottimizzazione per il calcolo mentale. Infatti, l'algoritmo non è adatto per il calcolo mentale, poiché richiede un notevole sovraccarico per le operazioni ricorsive. Inoltre, l'effetto non si manifesterà completamente finché i numeri non diventeranno abbastanza grandi (per fortuna, invece dell'algoritmo di Karatsuba sono arrivati metodi ancora più veloci: nel marzo 2019 è stato pubblicato un algoritmo che richiede solo moltiplicazioni; l'accelerazione si applica solo a numeri inimmaginabilmente grandi).
Questo algoritmo è descritto a pagina 295 del secondo volume di «Algoritmi numerici». Lì Knuth scrive: «È curioso che questa idea sia stata scoperta solo nel 1962 anno», quando è stato pubblicato un articolo che descriveva l'algoritmo di Karatsuba. Ma! Nel 1995, Karatsuba pubblicò un articolo intitolato «La complessità dei calcoli», in cui afferma diverse cose: 1) intorno al 1956, Kolmogorov ipotizzò che la moltiplicazione non può essere eseguita in meno di 
passi; 2) in 1960 Nel 1963, Karatsuba ha partecipato a un seminario in cui Kolmogorov ha presentato la sua ipotesi n². 3) «Proprio una settimana» Karatsuba ha sviluppato l'algoritmo «dividi e conquista»; 4) Nel 1962 Kolmogorov ha scritto e pubblicato un articolo a nome di Karatsuba che descriveva l'algoritmo. «Sono venuto a conoscenza di questo articolo solo dopo che è stato ripubblicato».
Pertanto, l'errore consiste nel fatto che invece di 1962 deve essere indicato 1960 l'anno. Ecco tutto.
Analisi
La ricerca di errori non richiedeva particolari abilità.
- Il primo errore era così banale che era quasi impossibile non notarlo, e si trovava in un luogo relativamente evidente (all'inizio del capitolo). Qualsiasi idiota l'avrebbe trovato; semplicemente, io ero quell'idiota.
- Trovare il secondo refuso richiedeva fortuna e impegno, ma non abilità. L'indice per "Williams" si trova penultima pagina del volume, una parte piuttosto evidente del libro. Stavo proprio sfogliando l'indice (non è così terribile come sembra, perché negli indici di Knuth si possono trovare uova di Pasqua. Ad esempio, ci sono voci in arabo e ebraico, entrambe che rimandano alla pagina 66. Ma in questa pagina non si menciona nessuna delle lingue; al contrario, si fa riferimento a "lingue che si leggono da destra a sinistra"). E la mia attenzione è stata attratta dal secondo nome. Poiché di solito leggo Wikipedia, ho verificato Robin Williams e ho notato una discrepanza.
- Vorrei poter dire di aver condotto una ricerca seria per trovare l'errore storico, ma in realtà ho semplicemente dato un'occhiata . Nelle prime righe si legge: "L'algoritmo di Karatsuba è un algoritmo di moltiplicazione veloce. 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 individuare un bug nel primo volume di "Algoritmi fondamenti". 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 di tre simboli: un'aggiunta s, una sostituzione m con n e 2 con 0. A un prezzo di $2,56, si tratta di simboli piuttosto redditizi; se ti pagassero così tanto, un articolo di 1000 parole (in media, quattro simboli) ti porterebbe dieci pezzi.
- Con tre dollari esadecimali, 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
Raccomandazioni generali per trovare errori nei libri di Knuth. Riguardano principalmente errori tecnici, di cui non ho conoscenza. C'è una frase che ho preso sul serio:
È meglio aspettare di raccogliere un insieme di errori da inviare. Unendo diversi errori reali ma non molto significativi, aumenterai le probabilità che uno di essi venga effettivamente considerato un errore o un consiglio. Inviare errori uno alla volta potrebbe portare al loro rifiuto.
Non volevo inviare solo stupide refusi, quindi ho seguito il consiglio e ho inviato una segnalazione solo quando ho trovato un errore storico che mi sembrava abbastanza serio.
Ashutosh Mehra è il terzo investitore più ricco di San Serif con un patrimonio colossale di 0x$207,f0 in BoSS.
- Varie:
Fonte: habr.com
