{"id":34164,"date":"2019-10-31T21:56:44","date_gmt":"2019-10-31T18:56:44","guid":{"rendered":"https:\/\/prohoster.info\/blog\/ya-poluchil-ot-knuta-chek-na-0x-3-00\/"},"modified":"2019-10-31T21:56:44","modified_gmt":"2019-10-31T18:56:44","slug":"ya-poluchil-ot-knuta-chek-na-0x-3-00","status":"publish","type":"post","link":"https:\/\/prohoster.info\/pl\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Otrzyma\u0142em od Knuta czek na 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 naukowiec w dziedzinie informatyki, kt\u00f3ry tak bardzo dba o poprawno\u015b\u0107 swoich ksi\u0105\u017cek, \u017ce oferuje jeden szesnastkowy dolar<\/b> ($2,56, 0x$1,00) za ka\u017cd\u0105 znalezion\u0105 \u201epomylk\u0119\u201d, gdzie pomy\u0142k\u0105 jest wszystko, co \u201etechnicznie, historycznie, typograficznie lub politycznie jest niepoprawne\u201d. Bardzo chcia\u0142em dosta\u0107 czek od Knuta, wi\u0119c postanowi\u0142em poszuka\u0107 b\u0142\u0119d\u00f3w w jego znakomitym dziele \u201eSztuka programowania\u201d<\/b> (TAOCP). Uda\u0142o mi si\u0119 znale\u017a\u0107 trzy. Na pewno, Knuth wys\u0142a\u0142 czek na 0x$3,00<\/b>.<\/p>\n

\"Otrzyma\u0142em
\n
\nJak wida\u0107, to nie jest prawdziwy czek. Kiedy\u015b Knuth wysy\u0142a\u0142 prawdziwe czeki, ale zaprzesta\u0142 tego w 2008 roku z powodu niepohamowanego oszustwa<\/a><\/noindex>. Teraz rozsy\u0142a \u201eosobiste certyfikaty depozytowe\u201d w banku San-Serif<\/a><\/noindex> (BoSS). M\u00f3wi, \u017ce jest got\u00f3w wys\u0142a\u0107 prawdziwe pieni\u0105dze w razie potrzeby, ale wydaje si\u0119, \u017ce to zbyt k\u0142opotliwe.
\n<\/a><\/noindex>
\nZnalaz\u0142em dwa b\u0142\u0119dy drukarskie i jeden b\u0142\u0105d historyczny. Wymieni\u0119 je w kolejno\u015bci malej\u0105cej trywialno\u015bci.<\/p>\n

B\u0142\u0105d drukarski nr 1<\/h1>\n

\nPierwszy b\u0142\u0105d drukarski \u2014 na stronie 392 trzeciego tomu \u201eSortowanie i wyszukiwanie\u201d, \u00f3smy wiersz od do\u0142u: \u201ePo nieudanej pr\u00f3bie wyszukiwania czasami (sometime) wskazane jest wprowadzenie do tabeli nowego wpisu, zawieraj\u0105cego K<\/i>; metoda, kt\u00f3ra to robi, nazywa si\u0119 algorytmem wyszukiwania i umieszczania. B\u0142\u0105d polega na tym, \u017ce zamiast sometime<\/i><\/b> powinno by\u0107 sometimes<\/i><\/b>.<\/p>\n

Oczywi\u015bcie, w takim b\u0142\u0119dzie nie ma nic dziwnego. Tylko w tym artykule na pewno znajdzie si\u0119 kilka b\u0142\u0119d\u00f3w drukarskich (\u017cadnych nagr\u00f3d za ich odnalezienie). Co mnie naprawd\u0119 zaskakuje, to to, \u017ce tak d\u0142ugo ich nie zauwa\u017cono. Strona 392 nie jest g\u0142\u0119boko zakopana w dziale matematyki, to najpierwsza strona<\/b> sz\u00f3stego rozdzia\u0142u \u201eWyszukiwanie\u201d! Mo\u017ce to jedna z najcz\u0119\u015bciej czytanych sekcji ksi\u0105\u017cki. Zasadniczo powinno by\u0107 tam najmniej b\u0142\u0119d\u00f3w drukarskich, ale nie.<\/p>\n

Swoj\u0105 drog\u0105, je\u015bli kiedykolwiek my\u015bla\u0142e\u015b o przeczytaniu TAOCP, spr\u00f3buj. Wiele os\u00f3b powie, \u017ce to podr\u0119cznik<\/b>, nie przeznaczony do bezpo\u015bredniego czytania, ale to nieprawda. Autor ma wyra\u017any punkt widzenia i charakterystyczny styl. Jedyn\u0105 rzecz\u0105, kt\u00f3ra przeszkadza w czytelno\u015bci, jest z\u0142o\u017cono\u015b\u0107 matematyki. Jednak jest proste rozwi\u0105zanie: czytaj, a\u017c dojdziesz do matematyki, kt\u00f3rej nie rozumiesz, pomi\u0144 j\u0105 i przejd\u017a do nast\u0119pnej sekcji, kt\u00f3r\u0105 mo\u017cesz zrozumie\u0107. Czytaj\u0105c w ten spos\u00f3b, pomijam co najmniej 80% ksi\u0105\u017cki, ale pozosta\u0142e 20% jest wspania\u0142e!<\/p>\n

M\u00f3wi si\u0119 te\u017c, \u017ce TAOCP jest nieistotna<\/b>, przestarza\u0142a lub w inny spos\u00f3b nieprzydatna do \u201eprawdziwego programowania\u201d. To r\u00f3wnie\u017c nieprawda. Na przyk\u0142ad, w pierwszej sekcji po wprowadzeniu omawiany jest proces wyszukiwania elementu w niesortowanej tablicy. Najprostszy algorytm jest znany ka\u017cdemu programi\u015bcie. Uruchom wska\u017anik na pocz\u0105tku tablicy, a nast\u0119pnie wykonaj nast\u0119puj\u0105ce kroki w p\u0119tli:<\/p>\n

    \n
  1. Sprawd\u017a, czy bie\u017c\u0105cy element jest tym, kt\u00f3rego szukasz. Je\u015bli tak, zwr\u00f3\u0107 go; w przeciwnym razie\n<\/li>\n
  2. Sprawd\u017a, czy wska\u017anik nie znajduje si\u0119 poza granicami tablicy. Je\u015bli tak, zwr\u00f3\u0107 b\u0142\u0105d; w przeciwnym razie\n<\/li>\n
  3. Zwi\u0119ksz wska\u017anik i kontynuuj.<\/li>\n<\/ol>\n

    \nTeraz rozwa\u017cmy: ile sprawdze\u0144 granic wymaga ten algorytm w \u015brednim przypadku? W najgorszym przypadku, gdy tablica nie zawiera elementu, dla ka\u017cdego elementu na li\u015bcie wymagana b\u0119dzie jedno sprawdzenie, a \u015brednio b\u0119dzie to co\u015b w rodzaju \"Otrzyma\u0142em. M\u0105drzejszy algorytm wyszukiwania mo\u017ce wymaga\u0107 tylko jednego sprawdzenia granic. Do\u0142\u0105czysz poszukiwany element na ko\u0144cu tablicy, a nast\u0119pnie uruchomisz wska\u017anik na pocz\u0105tku tablicy i wykonasz nast\u0119puj\u0105ce kroki w p\u0119tli:<\/p>\n

      \n
    1. Sprawd\u017a, czy bie\u017c\u0105cy element jest tym, kt\u00f3rego szukasz. Je\u015bli tak, zwr\u00f3\u0107 odpowied\u017a, je\u015bli wska\u017anik znajduje si\u0119 w granicach tablicy, lub b\u0142\u0105d, je\u015bli tak nie jest. W przeciwnym razie\n<\/li>\n
    2. Zwi\u0119ksz wska\u017anik i kontynuuj.<\/li>\n<\/ol>\n

      \nW ten lub inny spos\u00f3b element z pewno\u015bci\u0105 zostanie znaleziony, a sprawdzenie granic wykonuje si\u0119 tylko raz, gdy to nast\u0105pi. To g\u0142\u0119boki pomys\u0142, ale wystarczaj\u0105co prosty nawet dla pocz\u0105tkuj\u0105cego programisty. Prawdopodobnie nie mog\u0119 m\u00f3wi\u0107 o aktualno\u015bci pracy dla innych, ale od razu uda\u0142o mi si\u0119 zastosowa\u0107 t\u0119 m\u0105dro\u015b\u0107 zar\u00f3wno w kodzie osobistym, jak i zawodowym. Ksi\u0105\u017cka TAOCP jest pe\u0142na takich pere\u0142ek (dla sprawiedliwo\u015bci, jest tam te\u017c wiele dziwnych rzeczy, takich jak sortowanie b\u0105belkowe<\/a><\/noindex>).<\/p>\n

      \u201eWyszukiwanie, wyszukiwanie
      \nTak d\u0142ugo
      \nWyszukiwanie, wyszukiwanie
      \nChcia\u0142em tylko ta\u0144czy\u0107\u201d<\/i>
      \n\u2014 Luther Vandross, \u201eWyszukiwanie\u201d (1980)<\/p><\/blockquote>\n

      <\/p>\n

      B\u0142\u0105d nr 2<\/h1>\n

      \nDruga pomy\u0142ka wyst\u0119puje w tomie 4A, \u201eAlgorytmy kombinatoryczne\u201d, cz\u0119\u015b\u0107 1. Na stronie 60 opisana jest kwestia planowania wyst\u0119p\u00f3w komik\u00f3w w r\u00f3\u017cnych kasynach. Jako przyk\u0142ad przytoczono kilku prawdziwych komik\u00f3w, w tym Lily Tomlin, Weird Al Yankovic i Robina Williamsa, kt\u00f3ry jeszcze \u017cy\u0142, gdy ksi\u0105\u017cka si\u0119 ukaza\u0142a. Knuth zawsze podaje w indeksie pe\u0142ne imiona, dlatego Williamsa wspomniano na stronie 882 jako \u201eWilliams, Robin McLaurin\u201d. Jednak jego drugie imi\u0119 ko\u0144czy si\u0119 na \u201en\u201d, a nie na \u201em\u201d, to znaczy McLaurin.<\/p>\n

      McLaurin to panie\u0144skie nazwisko jego matki. By\u0142a prawnuczk\u0105 Anselma Josepha McLaurina, 34. gubernatora Mississippi. Jego rz\u0105dy nie zapisa\u0142y si\u0119 w pami\u0119ci niczym dobrym. Z ksi\u0105\u017cki \u201eMississippi: historia\u201d<\/a><\/noindex>:<\/p>\n

      \u201eNajwa\u017cniejszym wydarzeniem w czasie administracji McLaurina by\u0142o og\u0142oszenie przez Stany Zjednoczone wojny Hiszpanii wiosn\u0105 1898 roku\u2026 Niestety, wojna mog\u0142a da\u0107 niekt\u00f3rym urz\u0119dnikom pa\u0144stwowym okazj\u0119 do korupcji. McLaurina oskar\u017cono o r\u00f3\u017cne w\u0105tpliwe praktyki, w tym nepotyzm oraz nadmierne korzystanie z uprawnie\u0144 do u\u0142askawienia. W epoce ruchu na rzecz trze\u017awo\u015bci krytycy oskar\u017cyli gubernatora o pija\u0144stwo, co on publicznie przyzna\u0142\u201d.<\/i><\/p><\/blockquote>\n

      <\/p>\n

      B\u0142\u0105d historyczny<\/h1>\n

      \nRozwa\u017cmy tradycyjny algorytm mno\u017cenia<\/b> z program\u00f3w szkolnych. Ile wymaga jedno-cyfrowych operacji mno\u017cenia? Za\u0142\u00f3\u017cmy, \u017ce mno\u017cysz \"Otrzyma\u0142em-cyfrow\u0105 liczb\u0119 \"Otrzyma\u0142em na \"Otrzyma\u0142em-cyfrowym \"Otrzyma\u0142em. Najpierw mno\u017cysz pierwsz\u0105 cyfr\u0119 \"Otrzyma\u0142em przez ka\u017cd\u0105 cyfr\u0119 \"Otrzyma\u0142em po kolei. Nast\u0119pnie mno\u017cysz drug\u0105 cyfr\u0119 \"Otrzyma\u0142em przez ka\u017cd\u0105 cyfr\u0119 \"Otrzyma\u0142em po kolei i tak dalej, a\u017c przejdziesz przez wszystkie cyfry \"Otrzyma\u0142em. W ten spos\u00f3b tradycyjne mno\u017cenie wymaga \"Otrzyma\u0142em prymitywnych mno\u017ce\u0144. W szczeg\u00f3lno\u015bci mno\u017cenie dw\u00f3ch liczb po \"Otrzyma\u0142em cyfrach wymaga \"Otrzyma\u0142em jedno-cyfrowych mno\u017ce\u0144.<\/p>\n

      To niewiele, ale mo\u017cna zoptymalizowa\u0107 proces za pomoc\u0105 metody opracowanej przez radzieckiego matematyka Anatolego Aleksiejewicza Karacub\u0119. Za\u0142\u00f3\u017cmy, \u017ce \"Otrzyma\u0142em i \"Otrzyma\u0142em\u00a0- to dwucyfrowe liczby dziesi\u0119tne; to znaczy istniej\u0105 liczby \"Otrzyma\u0142em, \"Otrzyma\u0142em, \"Otrzyma\u0142em, \"Otrzyma\u0142em takie, \u017ce \"Otrzyma\u0142em i \"Otrzyma\u0142em (uog\u00f3lnienie tego algorytmu na wi\u0119ksze cyfry wymaga pewnych manipulacji; chocia\u017c to nie jest zbyt skomplikowane, to wol\u0119 trzyma\u0107 si\u0119 prostego przyk\u0142adu, aby nie pope\u0142ni\u0107 b\u0142\u0119du w szczeg\u00f3\u0142ach). Wtedy \"Otrzyma\u0142em, \"Otrzyma\u0142em, \"Otrzyma\u0142em. Mno\u017cenie dwumian\u00f3w daje \"Otrzyma\u0142em. Jak na razie mamy wci\u0105\u017c \"Otrzyma\u0142em jedno-cyfrowych mno\u017ce\u0144: \"Otrzyma\u0142em, \"Otrzyma\u0142em, \"Otrzyma\u0142em, \"Otrzyma\u0142em. Teraz dodajmy i odejmijmy \"Otrzyma\u0142emPo kilku przestawieniach, kt\u00f3re pozostawi\u0119 jako \u0107wiczenie dla czytelnika, uzyskuje si\u0119 \"Otrzyma\u0142em\u00a0\u2014 zaledwie trzy jednocyfrowe mno\u017cenia! (S\u0105 pewne sta\u0142e wsp\u00f3\u0142czynniki, ale mo\u017cna je obliczy\u0107 tylko przez dodawanie i przesuwanie cyfr).<\/p>\n

      Nie pro\u015b o dow\u00f3d, ale algorytm Karatsuby<\/b> (rekursywnie uog\u00f3lniony z podanego powy\u017cej przyk\u0142adu) poprawia tradycyjn\u0105 metod\u0119 mno\u017cenia z \"Otrzyma\u0142em operacji do \"Otrzyma\u0142em. Zwr\u00f3\u0107 uwag\u0119, \u017ce to rzeczywiste ulepszenie algorytmu, a nie optymalizacja do oblicze\u0144 w my\u015bli. Rzeczywi\u015bcie, algorytm nie nadaje si\u0119 do liczenia w my\u015bli, poniewa\u017c wymaga du\u017cych nak\u0142ad\u00f3w na operacje rekurencyjne. Ponadto efekt nie ujawni si\u0119 w pe\u0142ni, dop\u00f3ki liczby nie stan\u0105 si\u0119 wystarczaj\u0105co du\u017ce (na szcz\u0119\u015bcie, zamiast algorytmu Karatsuby pojawi\u0142y si\u0119 jeszcze szybsze metody: w marcu 2019 roku opublikowano algorytm, kt\u00f3ry wymaga zaledwie n log n<\/i><\/a><\/noindex> mno\u017ce\u0144; przyspieszenie ma zastosowanie tylko do niewyobra\u017calnie du\u017cych liczb).<\/p>\n

      Ten algorytm opisany jest na stronie 295 drugiego tomu \u00abAlgorytmy numeryczne\u00bb. Tam Knuth pisze: \u00abCiekawostk\u0105 jest, \u017ce t\u0119 ide\u0119 odkryto dopiero w 1962<\/b> roku\u00bb, kiedy opublikowano artyku\u0142 opisuj\u0105cy algorytm Karatsuby. Ale! W 1995 roku Karatsuba opublikowa\u0142 artyku\u0142 \u201eZ\u0142o\u017cono\u015b\u0107 oblicze\u0144\u201d, w kt\u00f3rym m\u00f3wi kilka rzeczy: 1) oko\u0142o 1956 roku Kolmogorow zasugerowa\u0142, \u017ce mno\u017cenie nie mo\u017ce by\u0107 wykonane w mniej ni\u017c \"Otrzyma\u0142em krok\u00f3w; 2) w 1960<\/b> roku Karatsuba by\u0142 obecny na seminarium, gdzie Kolmogorow przedstawi\u0142 swoj\u0105 hipotez\u0119 n\u00b2. 3) \u201eZaledwie tydzie\u0144 p\u00f3\u017aniej\u201d Karatsuba opracowa\u0142 algorytm \u201edziel i rz\u0105d\u017a\u201d; 4) w 1962 roku Kolmogorow napisa\u0142 i opublikowa\u0142 artyku\u0142 w imieniu Karatsuby<\/i> z opisem algorytmu. \u201eDowiedzia\u0142em si\u0119 o tym artykule dopiero po jego przedrukowaniu\u201d.<\/p>\n

      W ten spos\u00f3b b\u0142\u0105d polega na tym, \u017ce zamiast 1962<\/i> powinien by\u0107 podany 1960<\/i> rok. I to wszystko.<\/p>\n

      Analiza<\/h1>\n

      \nWyszukiwanie b\u0142\u0119d\u00f3w nie wymaga\u0142o szczeg\u00f3lnych umiej\u0119tno\u015bci.<\/b><\/p>\n

        \n
      1. Pierwszy b\u0142\u0105d by\u0142 tak banalny, jak to mo\u017cliwe, i znajdowa\u0142 si\u0119 w stosunkowo widocznym miejscu (pocz\u0105tek rozdzia\u0142u). Ka\u017cdy idiota by go znalaz\u0142; po prostu to ja by\u0142em tym idiot\u0105.\n<\/li>\n
      2. Poszukiwanie drugiego b\u0142\u0119du typograficznego wymaga\u0142o szcz\u0119\u015bcia i wysi\u0142ku, ale nie umiej\u0119tno\u015bci. Indeks dla \u201eWilliamsa\u201d znajduje si\u0119 na przedostatniej stronie tomu, do\u015b\u0107 zauwa\u017calnej cz\u0119\u015bci ksi\u0105\u017cki. W\u0142a\u015bnie przegl\u0105da\u0142em indeks (to nie jest tak bolesne, jak si\u0119 wydaje, poniewa\u017c w indeksach Knutha kryj\u0105 si\u0119 wielkanocne jajka. Na przyk\u0142ad, s\u0105 tam wpisy w j\u0119zyku arabskim i hebrajskim, kt\u00f3re wskazuj\u0105 na stron\u0119 66. Jednak na tej stronie nie wspomniano o \u017cadnym z tych j\u0119zyk\u00f3w; zamiast tego wspomniano o \u201ej\u0119zykach, kt\u00f3re czyta si\u0119 od prawej do lewej\u201d). I moj\u0105 uwag\u0119 zwr\u00f3ci\u0142o drugie imi\u0119. Poniewa\u017c zwykle czytam Wikipedi\u0119, sprawdzi\u0142em Robina Williamsa i zauwa\u017cy\u0142em niezgodno\u015b\u0107.\n<\/li>\n
      3. Chcia\u0142bym powiedzie\u0107, \u017ce przeprowadzi\u0142em powa\u017cne badania, aby znale\u017a\u0107 historyczny b\u0142\u0105d, ale w rzeczywisto\u015bci po prostu spojrza\u0142em na stron\u0119 Wikipedii na temat algorytmu Karatsuby<\/a><\/noindex>. W pierwszych linijkach napisano: \u201eAlgorytm Karatsuby to algorytm szybkiego mno\u017cenia. Odkryty przez Anatole'a Karatsub\u0119 w 1960 roku i opublikowany w 1962 roku\u201d. Po tym wystarczy\u0142o tylko doda\u0107 dwa do dw\u00f3ch.<\/li>\n<\/ol>\n

        \nW przysz\u0142o\u015bci chcia\u0142bym znale\u017a\u0107 bardziej znacz\u0105cy b\u0142\u0105d, zw\u0142aszcza w kodzie Knutha. Chcia\u0142bym r\u00f3wnie\u017c znale\u017a\u0107 b\u0142\u0105d w pierwszym tomie \u201eFundamentalnych algorytm\u00f3w\u201d. Mo\u017ce bym go znalaz\u0142, ale w lokalnej bibliotece z jakiego\u015b powodu dost\u0119pne s\u0105 tylko tomy 2, 3 i 4A.<\/p>\n

        Fakty finansowe:<\/b><\/p>\n