Donald Knuth — naukowiec w dziedzinie informatyki, który tak bardzo dba o poprawność swoich książek, że oferuje jeden szesnastkowy dolar ($2,56, 0x$1,00) za każdą znalezioną „pomylkę”, gdzie pomyłką jest wszystko, co „technicznie, historycznie, typograficznie lub politycznie jest niepoprawne”. Bardzo chciałem dostać czek od Knuta, więc postanowiłem poszukać błędów w jego znakomitym dziele „Sztuka programowania” (TAOCP). Udało mi się znaleźć trzy. Na pewno, Knuth wysłał czek na 0x$3,00.
Jak widać, to nie jest prawdziwy czek. Kiedyś Knuth wysyłał prawdziwe czeki, ale zaprzestał tego w 2008 roku z powodu . Teraz rozsyła „osobiste certyfikaty depozytowe” w (BoSS). Mówi, że jest gotów wysłać prawdziwe pieniądze w razie potrzeby, ale wydaje się, że to zbyt kłopotliwe.
Znalazłem dwa błędy drukarskie i jeden błąd historyczny. Wymienię je w kolejności malejącej trywialności.
Błąd drukarski nr 1
Pierwszy błąd drukarski — na stronie 392 trzeciego tomu „Sortowanie i wyszukiwanie”, ósmy wiersz od dołu: „Po nieudanej próbie wyszukiwania czasami (sometime) wskazane jest wprowadzenie do tabeli nowego wpisu, zawierającego K; metoda, która to robi, nazywa się algorytmem wyszukiwania i umieszczania. Błąd polega na tym, że zamiast sometime powinno być sometimes.
Oczywiście, w takim błędzie nie ma nic dziwnego. Tylko w tym artykule na pewno znajdzie się kilka błędów drukarskich (żadnych nagród za ich odnalezienie). Co mnie naprawdę zaskakuje, to to, że tak długo ich nie zauważono. Strona 392 nie jest głęboko zakopana w dziale matematyki, to najpierwsza strona szóstego rozdziału „Wyszukiwanie”! Może to jedna z najczęściej czytanych sekcji książki. Zasadniczo powinno być tam najmniej błędów drukarskich, ale nie.
Swoją drogą, jeśli kiedykolwiek myślałeś o przeczytaniu TAOCP, spróbuj. Wiele osób powie, że to podręcznik, nie przeznaczony do bezpośredniego czytania, ale to nieprawda. Autor ma wyraźny punkt widzenia i charakterystyczny styl. Jedyną rzeczą, która przeszkadza w czytelności, jest złożoność matematyki. Jednak jest proste rozwiązanie: czytaj, aż dojdziesz do matematyki, której nie rozumiesz, pomiń ją i przejdź do następnej sekcji, którą możesz zrozumieć. Czytając w ten sposób, pomijam co najmniej 80% książki, ale pozostałe 20% jest wspaniałe!
Mówi się też, że TAOCP jest nieistotna, przestarzała lub w inny sposób nieprzydatna do „prawdziwego programowania”. To również nieprawda. Na przykład, w pierwszej sekcji po wprowadzeniu omawiany jest proces wyszukiwania elementu w niesortowanej tablicy. Najprostszy algorytm jest znany każdemu programiście. Uruchom wskaźnik na początku tablicy, a następnie wykonaj następujące kroki w pętli:
- Sprawdź, czy bieżący element jest tym, którego szukasz. Jeśli tak, zwróć go; w przeciwnym razie
- Sprawdź, czy wskaźnik nie znajduje się poza granicami tablicy. Jeśli tak, zwróć błąd; w przeciwnym razie
- Zwiększ wskaźnik i kontynuuj.
Teraz rozważmy: ile sprawdzeń granic wymaga ten algorytm w średnim przypadku? W najgorszym przypadku, gdy tablica nie zawiera elementu, dla każdego elementu na liście wymagana będzie jedno sprawdzenie, a średnio będzie to coś w rodzaju 
. Mądrzejszy algorytm wyszukiwania może wymagać tylko jednego sprawdzenia granic. Dołączysz poszukiwany element na końcu tablicy, a następnie uruchomisz wskaźnik na początku tablicy i wykonasz następujące kroki w pętli:
- Sprawdź, czy bieżący element jest tym, którego szukasz. Jeśli tak, zwróć odpowiedź, jeśli wskaźnik znajduje się w granicach tablicy, lub błąd, jeśli tak nie jest. W przeciwnym razie
- Zwiększ wskaźnik i kontynuuj.
W ten lub inny sposób element z pewnością zostanie znaleziony, a sprawdzenie granic wykonuje się tylko raz, gdy to nastąpi. To głęboki pomysł, ale wystarczająco prosty nawet dla początkującego programisty. Prawdopodobnie nie mogę mówić o aktualności pracy dla innych, ale od razu udało mi się zastosować tę mądrość zarówno w kodzie osobistym, jak i zawodowym. Książka TAOCP jest pełna takich perełek (dla sprawiedliwości, jest tam też wiele dziwnych rzeczy, takich jak ).
„Wyszukiwanie, wyszukiwanie
Tak długo
Wyszukiwanie, wyszukiwanie
Chciałem tylko tańczyć”
— Luther Vandross, „Wyszukiwanie” (1980)
Błąd nr 2
Druga pomyłka występuje w tomie 4A, „Algorytmy kombinatoryczne”, część 1. Na stronie 60 opisana jest kwestia planowania występów komików w różnych kasynach. Jako przykład przytoczono kilku prawdziwych komików, w tym Lily Tomlin, Weird Al Yankovic i Robina Williamsa, który jeszcze żył, gdy książka się ukazała. Knuth zawsze podaje w indeksie pełne imiona, dlatego Williamsa wspomniano na stronie 882 jako „Williams, Robin McLaurin”. Jednak jego drugie imię kończy się na „n”, a nie na „m”, to znaczy McLaurin.
McLaurin to panieńskie nazwisko jego matki. Była prawnuczką Anselma Josepha McLaurina, 34. gubernatora Mississippi. Jego rządy nie zapisały się w pamięci niczym dobrym. Z książki :
„Najważniejszym wydarzeniem w czasie administracji McLaurina było ogłoszenie przez Stany Zjednoczone wojny Hiszpanii wiosną 1898 roku… Niestety, wojna mogła dać niektórym urzędnikom państwowym okazję do korupcji. McLaurina oskarżono o różne wątpliwe praktyki, w tym nepotyzm oraz nadmierne korzystanie z uprawnień do ułaskawienia. W epoce ruchu na rzecz trzeźwości krytycy oskarżyli gubernatora o pijaństwo, co on publicznie przyznał”.
Błąd historyczny
Rozważmy tradycyjny algorytm mnożenia z programów szkolnych. Ile wymaga jedno-cyfrowych operacji mnożenia? Załóżmy, że mnożysz 
-cyfrową liczbę 
na 
-cyfrowym 
. Najpierw mnożysz pierwszą cyfrę 
przez każdą cyfrę 
po kolei. Następnie mnożysz drugą cyfrę 
przez każdą cyfrę 
po kolei i tak dalej, aż przejdziesz przez wszystkie cyfry 
. W ten sposób tradycyjne mnożenie wymaga 
prymitywnych mnożeń. W szczególności mnożenie dwóch liczb po 
cyfrach wymaga 
jedno-cyfrowych mnożeń.
To niewiele, ale można zoptymalizować proces za pomocą metody opracowanej przez radzieckiego matematyka Anatolego Aleksiejewicza Karacubę. Załóżmy, że 
i 
- to dwucyfrowe liczby dziesiętne; to znaczy istnieją liczby 
, 
, 
, 
takie, że 
i 
(uogólnienie tego algorytmu na większe cyfry wymaga pewnych manipulacji; chociaż to nie jest zbyt skomplikowane, to wolę trzymać się prostego przykładu, aby nie popełnić błędu w szczegółach). Wtedy 
, 
, 
. Mnożenie dwumianów daje 
. Jak na razie mamy wciąż 
jedno-cyfrowych mnożeń: 
, 
, 
, 
. Teraz dodajmy i odejmijmy 
Po kilku przestawieniach, które pozostawię jako ćwiczenie dla czytelnika, uzyskuje się 
— zaledwie trzy jednocyfrowe mnożenia! (Są pewne stałe współczynniki, ale można je obliczyć tylko przez dodawanie i przesuwanie cyfr).
Nie proś o dowód, ale algorytm Karatsuby (rekursywnie uogólniony z podanego powyżej przykładu) poprawia tradycyjną metodę mnożenia z 
operacji do 
. Zwróć uwagę, że to rzeczywiste ulepszenie algorytmu, a nie optymalizacja do obliczeń w myśli. Rzeczywiście, algorytm nie nadaje się do liczenia w myśli, ponieważ wymaga dużych nakładów na operacje rekurencyjne. Ponadto efekt nie ujawni się w pełni, dopóki liczby nie staną się wystarczająco duże (na szczęście, zamiast algorytmu Karatsuby pojawiły się jeszcze szybsze metody: w marcu 2019 roku opublikowano algorytm, który wymaga zaledwie mnożeń; przyspieszenie ma zastosowanie tylko do niewyobrażalnie dużych liczb).
Ten algorytm opisany jest na stronie 295 drugiego tomu «Algorytmy numeryczne». Tam Knuth pisze: «Ciekawostką jest, że tę ideę odkryto dopiero w 1962 roku», kiedy opublikowano artykuł opisujący algorytm Karatsuby. Ale! W 1995 roku Karatsuba opublikował artykuł „Złożoność obliczeń”, w którym mówi kilka rzeczy: 1) około 1956 roku Kolmogorow zasugerował, że mnożenie nie może być wykonane w mniej niż 
kroków; 2) w 1960 roku Karatsuba był obecny na seminarium, gdzie Kolmogorow przedstawił swoją hipotezę n². 3) „Zaledwie tydzień później” Karatsuba opracował algorytm „dziel i rządź”; 4) w 1962 roku Kolmogorow napisał i opublikował artykuł w imieniu Karatsuby z opisem algorytmu. „Dowiedziałem się o tym artykule dopiero po jego przedrukowaniu”.
W ten sposób błąd polega na tym, że zamiast 1962 powinien być podany 1960 rok. I to wszystko.
Analiza
Wyszukiwanie błędów nie wymagało szczególnych umiejętności.
- Pierwszy błąd był tak banalny, jak to możliwe, i znajdował się w stosunkowo widocznym miejscu (początek rozdziału). Każdy idiota by go znalazł; po prostu to ja byłem tym idiotą.
- Poszukiwanie drugiego błędu typograficznego wymagało szczęścia i wysiłku, ale nie umiejętności. Indeks dla „Williamsa” znajduje się na przedostatniej stronie tomu, dość zauważalnej części książki. Właśnie przeglądałem indeks (to nie jest tak bolesne, jak się wydaje, ponieważ w indeksach Knutha kryją się wielkanocne jajka. Na przykład, są tam wpisy w języku arabskim i hebrajskim, które wskazują na stronę 66. Jednak na tej stronie nie wspomniano o żadnym z tych języków; zamiast tego wspomniano o „językach, które czyta się od prawej do lewej”). I moją uwagę zwróciło drugie imię. Ponieważ zwykle czytam Wikipedię, sprawdziłem Robina Williamsa i zauważyłem niezgodność.
- Chciałbym powiedzieć, że przeprowadziłem poważne badania, aby znaleźć historyczny błąd, ale w rzeczywistości po prostu spojrzałem . W pierwszych linijkach napisano: „Algorytm Karatsuby to algorytm szybkiego mnożenia. Odkryty przez Anatole'a Karatsubę w 1960 roku i opublikowany w 1962 roku”. Po tym wystarczyło tylko dodać dwa do dwóch.
W przyszłości chciałbym znaleźć bardziej znaczący błąd, zwłaszcza w kodzie Knutha. Chciałbym również znaleźć błąd w pierwszym tomie „Fundamentalnych algorytmów”. Może bym go znalazł, ale w lokalnej bibliotece z jakiegoś powodu dostępne są tylko tomy 2, 3 i 4A.
Fakty finansowe:
- W sumie mój wkład w TAOCP składa się z zaledwie trzech symboli: jednej dodanej s, zamiana m na n i 2 na 0. Przy cenie 2,56 USD to całkiem dochodowe symbole; gdyby płacono ci takie pieniądze, artykuł liczący 1000 słów (średnio cztery symbole) przyniósłby ci dziesięć stów.
- Z trzema szesnastkowymi dolarami dzielę 69. miejsce na liście najbogatszych inwestorów banku San-Seryff (stan na 1 maja 2019 roku) z 29 innymi obywatelami.
Inne dyskusje na temat czeków od Knutha
Ogólne wskazówki dotyczące wyszukiwania błędów w książkach Knutha. Głównie dotyczą technicznych błędów, których nie posiadam. Jest jedno zdanie, które wzięłem na poważnie:
Lepiej poczekać, aż zbierzesz zestaw błędów do wysłania. Łącząc kilka prawdziwych, ale niezbyt cennych błędów, zwiększysz prawdopodobieństwo, że jeden z nich zostanie naprawdę uznany za błąd lub sugestię. Jeśli wyślesz błędy pojedynczo, mogą one zostać odrzucone osobno.
Nie chciałem wysyłać po prostu głupich literówek, więc posłuchałem rady i wysłałem wiadomość dopiero gdy znalazłem błąd historyczny, który wydawał się wystarczająco poważny.
Ashutosh Mehra to trzeci najbogatszy inwestor w San-Serif z ogromnym majątkiem 0x$207,f0 w BoSS.
- Różne:
Źródło: habr.com
