Donalda Knutha jest informatykiem, który tak bardzo dba o dokładność swoich książek, które sugeruje jeden szesnastkowy dolar (2,56 USD, 0x1,00 USD) za każdy znaleziony „błąd”, przy czym błąd definiuje się jako wszystko, co jest „niepoprawne technicznie, historycznie, typograficznie lub politycznie”. Bardzo chciałem dostać czek od Knutha, więc postanowiłem poszukać błędów w jego opus magnum „Sztuka programowania” (TAOCP). Udało nam się znaleźć trzy. Zgodnie ze swoim słowem, Knut wysłał czek na kwotę 0x3,00 USD.

Jak widać, nie jest to prawdziwy sprawdzian. Knuth wysyłał prawdziwe czeki, ale w 2008 r. przestał z tego powodu szalejące oszustwo. Teraz wysyła do nich „osobiste certyfikaty depozytowe”. Banku San Serriff (Szef). Mówi, że w razie potrzeby jest skłonny przesłać prawdziwe pieniądze, ale wydaje się, że to zbyt duży kłopot.

Znalazłem dwie literówki i jeden błąd historyczny. Wymienię je w kolejności malejącej banalności.

Literówka nr 1

Pierwsza literówka znajduje się na stronie 392 tomu trzeciego „Sortowania i wyszukiwania”, ósmy wiersz od dołu: „Po nieudanym wyszukiwaniu czasami (czasami) pożądane jest wprowadzenie nowego rekordu do tabeli zawierającej K; metoda, która to robi, nazywa się algorytmem wyszukiwania i wstawiania. Błąd polega na tym, że zamiast tego czasami powinno być czasami.

Oczywiście taki błąd nie jest zaskakujący. Tylko w tym artykule z pewnością będzie kilka literówek (za ich znalezienie nie otrzymamy nagrody). Najbardziej zaskakujące jest to, że przez tak długi czas pozostawało to niezauważone. Strona 392 nie jest głęboko zakopana w części matematycznej już pierwszą stronę Rozdział XNUMX „Szukaj”! Prawdopodobnie jedna z najczęściej czytanych części książki. Teoretycznie powinno być jak najmniej literówek, ale nie.

Swoją drogą, jeśli kiedykolwiek zastanawiałeś się nad przeczytaniem TAOCP, spróbuj. Wielu powie, że tak katalog, nie jest przeznaczony do bezpośredniego czytania, ale nie jest to prawdą. Autor ma jasny punkt widzenia i charakterystyczny styl. Jedyną rzeczą, która utrudnia czytelność jest złożoność matematyki. Istnieje jednak proste rozwiązanie: czytaj, aż dojdziesz do matematyki, której nie rozumiesz, pomiń ją i przejdź do następnej sekcji, którą jesteś w stanie zrozumieć. Czytając w ten sposób brakuje mi co najmniej 80% książki, ale pozostałe 20% jest świetne!

Mówi się również, że TAOCP nieistotny, jest przestarzały lub w inny sposób nie ma zastosowania do „prawdziwego programowania”. To również nie jest prawdą. Na przykład pierwsza sekcja po wprowadzeniu dotyczy znajdowania elementu w nieposortowanej tablicy. Najprostszy algorytm jest znany wszystkim programistom. Uruchom wskaźnik na początku tablicy, a następnie wykonaj w pętli następujące czynności:

1. Sprawdź, czy bieżący element jest pożądany. Jeśli tak, zwracamy go; W przeciwnym razie
2. Sprawdź, czy wskaźnik znajduje się poza granicą tablicy. Jeśli tak, zwróć błąd; W przeciwnym razie
3. Powiększ i kontynuuj.

Zastanów się teraz: ile sprawdzań granic wymaga średnio ten algorytm? W najgorszym przypadku, gdy tablica nie zawiera elementu, każdy element na liście będzie wymagał jednego sprawdzenia i średnio będzie to wyglądało mniej więcej tak . Inteligentniejszy algorytm wyszukiwania mógłby uniknąć tylko jednego sprawdzenia granic. Dołącz żądany element na końcu tablicy, następnie umieść wskaźnik na początku tablicy i wykonaj następujące czynności w pętli:

1. Sprawdź, czy bieżący element jest pożądany. Jeśli tak, zwracamy odpowiedź, jeśli wskaźnik znajduje się w tablicy, lub błąd, jeśli tak nie jest. W przeciwnym razie
2. Powiększ i kontynuuj.

Tak czy inaczej, element zostanie znaleziony, a sprawdzenie granic zostanie przeprowadzone tylko raz, gdy tak się stanie. To głęboki pomysł, ale jest wystarczająco prosty nawet dla początkującego programisty. Prawdopodobnie nie mogę mówić o znaczeniu tej pracy dla innych, ale od razu mogłem zastosować tę mądrość zarówno w kodeksie osobistym, jak i zawodowym. Książka TAOCP jest pełna takich perełek (szczerze mówiąc, jest tam też sporo dziwnych rzeczy, jak np. sortowanie bąbelkowe).

"Szukaj Szukaj
Tak długo
Szukaj Szukaj
Chciałem tylko zatańczyć”
— Luther Vandross, „Poszukiwania” (1980)

Literówka nr 2

Druga literówka znajduje się w tomie 4A, Algorytmy kombinatoryczne, część 1. Strona 60 opisuje problem związany z planowaniem występów komików w różnych kasynach. Jako przykłady przytacza się kilku prawdziwych komików, w tym Lily Tomlin, Weird Al Yankovic i Robin Williams, który jeszcze żył, gdy książka została opublikowana. Knuth zawsze wymienia w indeksie pełne nazwiska, więc Williams jest wymieniony na stronie 882 jako „Williams, Robin McLorim”. Ale jego drugie imię kończy się na „n”, a nie „m”, czyli McLaurin.

McLaurin to nazwisko panieńskie jego matki. Była prawnuczką Anselma Josepha McLaurina, 34. gubernatora stanu Mississippi. Jego panowanie najwyraźniej nie zostało zapamiętane z niczego dobrego. Z książki „Mississippi: Historia”:

„Najważniejszym wydarzeniem za rządów McLaurina było wypowiedzenie wojny Hiszpanii przez Stany Zjednoczone wiosną 1898 roku… Niestety wojna mogła zapewnić niektórym urzędnikom rządowym możliwość zaangażowania się w przekupstwo. McLaurin został oskarżony o różne wątpliwe praktyki, w tym o nepotyzm i nadmierne korzystanie z prawa ułaskawienia. W okresie ruchu wstrzemięźliwości krytycy zarzucali gubernatorowi, że jest pijakiem, do czego ten publicznie się przyznał.

Historyczny błąd

Rozważać tradycyjny algorytm mnożenia ze szkolnego programu nauczania. Ile jednocyfrowych mnożeń wymaga? Załóżmy, że pomnożysz -cyfrowy numer na -fragment . Najpierw pomnóż pierwszą cyfrę dla każdej cyfry jeden po drugim. Następnie pomnóż drugą cyfrę dla każdej cyfry jeden po drugim i tak dalej, aż przejrzysz wszystkie liczby . Zatem tradycyjne mnożenie wymaga prymitywne mnożenie. W szczególności mnożenie dwóch liczb przez wymagane stopnie mnożenia jednocyfrowe.

To źle, ale można zoptymalizować proces, stosując metodę opracowaną przez radzieckiego matematyka Anatolija Aleksiejewicza Karatsubę. Udawajmy, że и  - dwucyfrowe liczby dziesiętne; to znaczy, że są liczby , , , takie, że и (uogólnienie tego algorytmu na większe liczby wymaga pewnej manipulacji; choć nie jest to zbyt trudne, żeby nie popełnić błędów w szczegółach, lepiej będę trzymać się prostego przykładu). Następnie , , . Mnożenie dwumianów daje . W tej chwili nadal tak mamy mnożenie jednocyfrowe: , , , . Teraz dodajemy i odejmujemy . Po kilku przegrupowaniach, które pozostawię jako ćwiczenie dla czytelnika, okazuje się  - tylko trzy jednocyfrowe mnożenia! (Istnieją pewne współczynniki stałe, ale można je obliczyć jedynie poprzez dodanie i przesunięcie cyfr).

Nie proś o dowód, ale Algorytm Karatsuby (rekursywnie uogólnione z powyższego przykładu) ulepsza tradycyjną metodę mnożenia za pomocą operacje wcześniej . Należy pamiętać, że jest to rzeczywiste ulepszenie algorytmu, a nie optymalizacja pod kątem obliczeń mentalnych. Rzeczywiście, algorytm nie nadaje się do arytmetyki mentalnej, ponieważ wymaga dużych kosztów ogólnych operacji rekurencyjnych. Ponadto efekt nie ujawni się w pełni, dopóki liczby nie staną się wystarczająco duże (na szczęście algorytm Karatsuby został zastąpiony jeszcze szybszymi metodami: w marcu 2019 roku opublikowano algorytm, który wymaga jedynie n dziennik n mnożenia; przyspieszenie dotyczy tylko niewyobrażalnie dużych liczb).

Algorytm ten opisano na stronie 295 tomu XNUMX, Algorytmy półnumeryczne. Tam Knuth pisze: „Ciekawe, że pomysł ten odkryto dopiero w 1962 roku”, kiedy ukazał się artykuł opisujący algorytm Karatsuby. Ale! W 1995 roku Karatsuba opublikował artykuł „Computational Complexity”, w którym stwierdzono kilka rzeczy: 1) około 1956 roku Kołmogorow zasugerował, że mnożenia nie można wykonać w czasie krótszym niż kroki; 2) w 1960 roku Karatsuba uczestniczył w seminarium, na którym Kołmogorow przedstawił swoją hipotezę n². 3) „Dokładnie w tydzień” Karatsuba opracował algorytm „dziel i rządź”; 4) w 1962 roku Kołmogorow napisał i opublikował artykuł w imieniu Karatsuby z opisem algorytmu. „Dowiedziałem się o tym artykule dopiero po jego ponownej publikacji.”

Więc błąd polega na tym, że zamiast 1962 należy określić 1960 rok. To wszystko.

Analiza

Znalezienie błędów nie wymagało specjalnych umiejętności.

1. Pierwszy błąd był możliwie trywialny i znajdował się w stosunkowo widocznym miejscu (początek rozdziału). Każdy idiota by to znalazł; Właśnie okazałem się tym idiotą.
2. Znalezienie drugiej literówki wymagało szczęścia i pracowitości, ale nie umiejętności. Indeks „Williamsa” znajduje się na przedostatniej stronie tomu, w dość widocznej części książki. Właśnie przeglądałem indeks (nie jest to aż tak żałosne, jak mogłoby się wydawać, bo w indeksach Knutha ukryte są pisanki. Są na przykład wpisy w języku arabskim i hebrajskim, oba odsyłające do strony 66. Ale na tej stronie nie ma wzmianki o któregokolwiek z języków; zamiast tego odnosi się do „języków czytanych od prawej do lewej”). I drugie imię przykuło moją uwagę. Ponieważ zazwyczaj czytam Wikipedię, sprawdziłem Robina Williamsa i zauważyłem rozbieżność.
3. Chciałbym móc powiedzieć, że przeprowadziłem poważne badania, aby znaleźć błąd historyczny, ale tak naprawdę tylko szukałem Strona Wikipedii o algorytmie Karatsuby. Już pierwsze linijki mówią: „Algorytm Karatsuba to algorytm szybkiego mnożenia. Odkryta przez Anatolija Karatsubę w 1960 r. i opublikowana w 1962 r.”. Potem pozostało już tylko dodać dwa do dwóch.

W przyszłości chciałbym znaleźć bardziej znaczący błąd, szczególnie w kodzie Knutha. Chciałbym także znaleźć błąd w pierwszym tomie Algorytmów podstawowych. Może bym ją znalazł, ale z jakiegoś powodu w lokalnej bibliotece znajdują się tylko tomy 2, 3 i 4A.

Fakty finansowe:

• W sumie mój wkład w TAOCP składa się tylko z trzech znaków: jednego dodatku s, wymiana m na n и 2 na 0. Przy cenie 2,56 dolara są to całkiem lukratywne symbole; Gdyby zarabiano taką sumę, za artykuł składający się z 1000 słów (średnio czterech znaków) można by zarobić dziesięć tysięcy.
• Z trzema dolarami szesnastkowymi plasuję się wraz z 29 innymi obywatelami na 69. miejscu na liście najbogatszych deponentów Banku San Serriff (stan na 1 maja 2019 r.).

Inne dyskusje na temat czeków od Knutha

• Jak zdobyć czek od Knutha

  Ogólne zalecenia dotyczące wyszukiwania błędów w książkach Knutha. Dotyczą głównie błędów technicznych, których u mnie nie ma. Jest tam jedna sugestia, którą potraktowałem poważnie:

  Z przesłaniem najlepiej poczekać, aż zbierzesz zestaw błędów. Łącząc kilka realnych, ale niezbyt wartościowych błędów, zwiększasz prawdopodobieństwo, że któryś z nich faktycznie zostanie potraktowany jako błąd lub porada. Jeśli będziesz zgłaszać błędy pojedynczo, każdy z osobna może zostać odrzucony.

  Nie chciałem wysyłać bezsensownych literówek, ale posłuchałem rady i wysłałem list dopiero wtedy, gdy znalazłem błąd historyczny, który wydawał się wystarczająco poważny.

• Czeki Ashutosha Mehry

  Ashutosh Mehra jest trzecim najbogatszym inwestorem w San Serriff z imponującym majątkiem netto wynoszącym 0x207,f0 w BoSS.

• Sprawdź, czy w prawdziwym kodzie TeX-owym nie występują błędy niefunkcjonalne
• Różne: #1 #2 #3 #4 #5 #6

Źródło: www.habr.com