Donald Knut è un informatico che tiene così tanto all'accuratezza dei suoi libri che suggerisce un dollaro esadecimale ($2,56, 0x$1,00) per qualsiasi "errore" trovato, dove un errore è definito come qualcosa che è "tecnicamente, storicamente, tipograficamente o politicamente scorretto". Volevo davvero ricevere un assegno da Knuth, quindi ho deciso di cercare eventuali errori nella sua opera magnum "L'arte della programmazione" (TAOCP). Siamo riusciti a trovarne tre. Fedele alla sua parola, Knut inviò un assegno per 0x$ 3,00.

Come puoi vedere, questo non è un vero assegno. Knuth inviava assegni reali, ma ha smesso nel 2008 a causa di frode dilagante. Ora invia "certificati di deposito personali" a Banca di San Serriff (Capo). Dice che è disposto a inviare soldi veri se necessario, ma sembra che sia una seccatura troppo.

Ho trovato due errori di battitura e un errore storico. Li elencherò in ordine di banalità decrescente.

Errore di battitura n. 1

Il primo errore di battitura è a pagina 392 del terzo volume “Ordinamento e ricerca”, ottava riga dal basso: “Dopo una ricerca infruttuosa, a volte (a volte) è opportuno inserire un nuovo record nella tabella contenente K; il metodo che fa questo è chiamato algoritmo di ricerca e inserimento. L'errore invece è quello a volte deve essere a volte.

Naturalmente, un simile errore non è sorprendente. Ci saranno sicuramente alcuni errori di battitura solo in questo articolo (nessuna ricompensa per trovarli). La cosa davvero sorprendente è che sia passato inosservato per così tanto tempo. La pagina 392 non è sepolta in profondità nella sezione di matematica, lo è la primissima pagina Capitolo 6 "Cerca"! Forse una delle sezioni più lette del libro. In teoria dovrebbero esserci meno errori di battitura, ma no.

A proposito, se hai mai pensato di leggere TAOCP, provalo. Molti diranno che è così elenco, non destinato alla lettura diretta, ma questo non è vero. L'autore ha un punto di vista chiaro e uno stile distintivo. L'unica cosa che ostacola la leggibilità è la complessità della matematica. Tuttavia, esiste una soluzione semplice: leggi fino ad arrivare alla matematica che non capisci, saltala e vai alla sezione successiva che puoi capire. Leggendo in questo modo mi manca almeno l'80% del libro, ma il restante 20% è fantastico!

Si dice anche che TAOCP irrilevante, è obsoleto o comunque non applicabile alla "programmazione reale". Anche questo non è vero. Ad esempio, la prima sezione dopo l'introduzione esamina la ricerca di un elemento in un array non ordinato. L'algoritmo più semplice è familiare a tutti i programmatori. Avvia il puntatore all'inizio dell'array, quindi esegui quanto segue in un ciclo:

1. Controlla se l'elemento corrente è quello desiderato. Se è così, lo restituiamo; Altrimenti
2. Controlla se il puntatore è all'esterno del limite dell'array. In tal caso, restituisce un errore; Altrimenti
3. Ingrandisci e continua.

Consideriamo ora: quanti controlli dei limiti richiede, in media, questo algoritmo? Nel peggiore dei casi, dove l'array non contiene un elemento, ogni elemento nell'elenco richiederà un controllo e in media sarà qualcosa come . Un algoritmo di ricerca più intelligente potrebbe farla franca con un solo controllo dei limiti. Collega l'elemento desiderato alla fine dell'array, quindi avvia il puntatore all'inizio dell'array ed esegui quanto segue in un ciclo:

1. Controlla se l'elemento corrente è quello desiderato. In tal caso, restituiamo una risposta se il puntatore è all'interno dell'array o un errore se non lo è. Altrimenti
2. Ingrandisci e continua.

In un modo o nell'altro, è garantito che l'elemento venga trovato e il controllo dei limiti viene eseguito solo una volta quando ciò accade. Questa è 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 stato immediatamente in grado di applicare questa saggezza sia al codice personale che a quello professionale. Il libro TAOCP è pieno di queste perle (a dire il vero, ci sono anche un sacco di cose strane, come ad esempio ordinamento delle bolle).

"Cerca
Così lungo
Cerca
Volevo solo ballare"
— Luther Vandross, "La ricerca" (1980)

Errore di battitura n. 2

Il secondo errore di battitura si trova nel volume 4A, Algoritmi combinatori, parte 1. La pagina 60 descrive un problema che coinvolge la programmazione di comici per esibirsi in vari casinò. Diversi comici della vita reale vengono citati come esempi, tra cui Lily Tomlin, Weird Al Yankovic e Robin Williams, che era ancora vivo quando il libro fu pubblicato. Knuth elenca sempre i nomi completi nell'indice, quindi Williams è elencato a pagina 882 come "Williams, Robin McLorim". Ma il suo secondo nome termina con la “n” e non con la “m”, ovvero McLaurin.

McLaurin era il nome da nubile di sua madre. Era la pronipote di Anselm Joseph McLaurin, 34esimo governatore del Mississippi. Il suo regno, a quanto pare, non fu ricordato per niente di buono. Dal libro "Mississippi: Storia":

“L'evento più importante durante l'amministrazione McLaurin fu la dichiarazione di guerra degli Stati Uniti alla Spagna nella primavera del 1898... Sfortunatamente, la guerra potrebbe aver fornito ad alcuni funzionari governativi l'opportunità di impegnarsi nella corruzione. McLaurin è stato accusato di varie pratiche discutibili, tra cui il nepotismo e l'uso eccessivo dei poteri di grazia. Durante il movimento per la temperanza, i critici accusarono il governatore di essere un ubriacone, cosa che egli ammise pubblicamente”.

Errore storico

Prendere in considerazione algoritmo di moltiplicazione tradizionale dal curriculum scolastico. Quante moltiplicazioni a una cifra sono necessarie? Supponiamo di moltiplicare -digita il numero su -morso . Per prima cosa moltiplica la prima cifra per ogni cifra uno per uno. Quindi moltiplica la seconda cifra per ogni cifra uno per uno e così via fino ad arrivare a tutti i numeri . Quindi richiede la moltiplicazione tradizionale moltiplicazioni primitive. In particolare, moltiplicando due numeri per gradi richiesti moltiplicazioni a una cifra.

Ciò è negativo, ma è possibile ottimizzare il processo utilizzando un metodo sviluppato dal matematico sovietico Anatoly Alekseevich Karatsuba. Facciamo finta che и  - numeri decimali a due cifre; cioè, ci sono numeri , , , tale che и (generalizzare questo algoritmo a numeri più grandi richiede una certa manipolazione; sebbene non sia troppo difficile, per non commettere errori nei dettagli, sarà meglio attenermi a un semplice esempio). Poi , , . Moltiplicando i binomi si ottiene . Al momento ne abbiamo ancora moltiplicazione a una cifra: , , , . Ora aggiungiamo e sottraiamo . Dopo alcuni riarrangiamenti, che lascerò come esercizio per il lettore, viene fuori  - solo tre moltiplicazioni a una cifra! (Esistono alcuni coefficienti costanti, ma possono essere calcolati solo sommando e spostando le cifre).

Non chiedere prove, ma Algoritmo di Karatsuba (generalizzato ricorsivamente dall'esempio sopra) migliora il metodo di moltiplicazione tradizionale con operazioni prima . Tieni presente che questo è un reale miglioramento dell'algoritmo, non un'ottimizzazione per i calcoli mentali. In effetti, l’algoritmo non è adatto all’aritmetica mentale, poiché richiede grandi costi generali per le operazioni ricorsive. Inoltre, l’effetto non si manifesterà pienamente finché i numeri non diventeranno sufficientemente grandi (fortunatamente l’algoritmo di Karatsuba è stato sostituito da metodi ancora più veloci: a marzo 2019 è stato pubblicato un algoritmo che richiede solo n registro n moltiplicazioni; l’accelerazione si applica solo a numeri inimmaginabilmente grandi).

Questo algoritmo è descritto a pagina 295 del volume XNUMX, Algoritmi seminumerici. Knuth scrive: “È curioso che questa idea sia stata scoperta solo in 1962 anno”, quando fu pubblicato un articolo che descriveva l’algoritmo di Karatsuba. Ma! Nel 1995, Karatsuba pubblicò un articolo "Computational Complexity", che dice diverse cose: 1) intorno al 1956, Kolmogorov suggerì che la moltiplicazione non può essere eseguita in meno di passaggi; 2) dentro 1960 L'anno successivo Karatsuba partecipò al seminario in cui Kolmogorov presentò la sua ipotesi n². 3) “In una settimana esatta”, Karatsuba ha sviluppato l’algoritmo “divide et impera”; 4) nel 1962 Kolmogorov scrisse e pubblicò un articolo per conto di Karatsuba con una descrizione dell'algoritmo. "Ho scoperto questo articolo solo dopo che è stato ripubblicato."

Quindi l'errore è che invece di 1962 deve essere specificato 1960 anno. È tutto.

analisi

Trovare gli errori non richiedeva abilità speciali.

1. Il primo errore era il più banale possibile e si trovava in un punto relativamente visibile (l'inizio del capitolo). Qualsiasi idiota l'avrebbe trovato; Mi sono semplicemente rivelato un idiota.
2. Trovare il secondo errore di battitura ha richiesto fortuna e diligenza, ma non abilità. L'indice di "Williams" si trova nella penultima pagina del volume, una parte abbastanza importante del libro. Stavo semplicemente sfogliando l'indice (non è così patetico come sembra, perché ci sono uova di Pasqua nascoste negli indici di Knuth. Ad esempio, ci sono voci in arabo ed ebraico, entrambe che puntano alla pagina 66. Ma quella pagina non menziona entrambe le lingue; si riferisce invece a “lingue che si leggono da destra a sinistra”). E il secondo nome ha attirato la mia attenzione. Dato che di solito leggo Wikipedia, ho controllato Robin Williams e ho notato una discrepanza.
3. Vorrei poter dire di aver fatto delle ricerche serie per trovare un errore storico, ma in realtà ho solo guardato Pagina di Wikipedia sull'algoritmo di Karatsuba. Le primissime righe dicono: “L'algoritmo Karatsuba è un algoritmo di moltiplicazione veloce. Scoperto da Anatoly Karatsuba nel 1960 e pubblicato nel 1962." Dopodiché non restava che sommare due più due.

In futuro mi piacerebbe trovare un bug più significativo, soprattutto nel codice di Knuth. Vorrei anche trovare un bug nel primo volume di Algoritmi Fondamentali. Forse l'avrei trovato, ma per qualche motivo la biblioteca locale ha solo i volumi 2, 3 e 4A.

Fatti finanziari:

• In totale, il mio contributo a TAOCP consiste di soli tre caratteri: un'aggiunta s, sostituzione m su n и 2 su 0. A $ 2,56, questi sono simboli piuttosto redditizi; Se fossi pagato così tanto, un articolo di 1000 parole (una media di quattro caratteri) ti farebbe guadagnare diecimila dollari.
• Con tre dollari esadecimali, insieme ad altri 29 cittadini, siamo al 69° posto nella lista dei depositanti più ricchi della San Serriff Bank (al 1 maggio 2019).

Altre discussioni sugli assegni di Knuth

• Come ottenere un assegno da Knuth

  Raccomandazioni generali per trovare errori nei libri di Knuth. Per lo più riguardano errori tecnici, di cui non ho. C'è un suggerimento che ho preso sul serio:

  È meglio attendere finché non avrai raccolto una serie di errori da inviare. Combinando diversi errori reali ma di scarso valore, aumenti la probabilità che uno di essi venga effettivamente considerato un errore o un consiglio. Se invii gli errori uno alla volta, ognuno di essi individualmente potrebbe essere rifiutato.

  Non volevo inviare solo errori di battitura senza senso, ma ho seguito il consiglio e ho inviato la lettera solo quando ho riscontrato un errore storico che sembrava abbastanza grave.

• Gli assegni di Ashutosh Mehra

  Ashutosh Mehra è il terzo investitore più ricco di San Serriff con un enorme patrimonio netto di 0x$207.f0 in BoSS.

• Verifica la presenza di alcuni bug non funzionali nel codice TeX reale
• Varie: #1 #2 #3 #4 #5 #6

Fonte: habr.com