{"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\/cs\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Dostal jsem od Knuta \u0161ek na 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 v\u011bdec v oblasti informatiky, kter\u00fd tak pe\u010dliv\u011b db\u00e1 na spr\u00e1vnost sv\u00fdch knih, \u017ee nab\u00edz\u00ed jeden hexadecim\u00e1ln\u00ed dolar<\/b> ($2,56, 0x$1,00) za jakoukoli nalezenou \u201echybu\u201c, kde chybou se rozum\u00ed v\u0161echno, co je \u201etechnicky, historicky, typograficky nebo politicky nespr\u00e1vn\u00e9\u201c. Opravdu jsem cht\u011bl dostat \u0161ek od Knutha, proto jsem se rozhodl hledat chyby v jeho vynikaj\u00edc\u00edm d\u00edle \u201eUm\u011bn\u00ed programov\u00e1n\u00ed\u201c<\/b> (TAOCP). Poda\u0159ilo se mi naj\u00edt t\u0159i. Pr\u00e1v\u011b podle slova, Knuth poslal \u0161ek na 0x$3,00<\/b>.<\/p>\n

\"Dostal
\n
\nJak vid\u00edte, toto nen\u00ed skute\u010dn\u00fd \u0161ek. D\u0159\u00edve Knuth pos\u00edlal skute\u010dn\u00e9 \u0161eky, ale p\u0159estal v roce 2008 kv\u016fli nep\u0159etr\u017eit\u00e9mu podvodu<\/a><\/noindex>. Nyn\u00ed rozes\u00edl\u00e1 \u201eosobn\u00ed depozitn\u00ed certifik\u00e1ty\u201c v bance San Serriffe<\/a><\/noindex> (BoSS). \u0158\u00edk\u00e1, \u017ee je ochoten poslat skute\u010dn\u00e9 pen\u00edze v p\u0159\u00edpad\u011b pot\u0159eby, ale zd\u00e1 se, \u017ee je to p\u0159\u00edli\u0161 pracn\u00e9.
\n<\/a><\/noindex>
\nNa\u0161el jsem dv\u011b tiskov\u00e9 chyby a jednu historickou chybu. Vyjmenuji je podle klesaj\u00edc\u00ed triviality.<\/p>\n

Tiskov\u00e1 chyba \u010d. 1<\/h1>\n

\nPrvn\u00ed tiskov\u00e1 chyba \u2014 na str\u00e1nce 392 t\u0159et\u00edho svazku \u201eT\u0159\u00edd\u011bn\u00ed a vyhled\u00e1v\u00e1n\u00ed\u201c, osm\u00e1 \u0159\u00e1dka zespodu: \u201ePo ne\u00fasp\u011b\u0161n\u00e9m vyhled\u00e1v\u00e1n\u00ed je n\u011bkdy (sometime) \u017e\u00e1douc\u00ed zav\u00e9st do tabulky nov\u00fd z\u00e1znam, kter\u00fd obsahuje K<\/i>; metoda, kter\u00e1 to d\u011bl\u00e1, se naz\u00fdv\u00e1 algoritmus vyhled\u00e1v\u00e1n\u00ed a vkl\u00e1d\u00e1n\u00ed. Chyba spo\u010d\u00edv\u00e1 v tom, \u017ee m\u00edsto sometime<\/i><\/b> m\u011blo b\u00fdt sometimes<\/i><\/b>.<\/p>\n

Samoz\u0159ejm\u011b, v takov\u00e9 chyb\u011b nen\u00ed nic p\u0159ekvapiv\u00e9ho. Jen v tomto \u010dl\u00e1nku ur\u010dit\u011b naleznete n\u011bkolik tiskov\u00fdch chyb (\u017e\u00e1dn\u00e9 odm\u011bny za jejich nalezen\u00ed). Co je opravdu p\u0159ekvapiv\u00e9, je to, \u017ee si jich tak dlouho nikdo nev\u0161iml. Str\u00e1nka 392 nen\u00ed hluboko poh\u0159bena v odd\u00edle o matematice, je to nejprve prvn\u00ed str\u00e1nka<\/b> \u0161est\u00e9 kapitoly \u201eVyhled\u00e1v\u00e1n\u00ed\u201c! Mo\u017en\u00e1 jeden z nejv\u00edce \u010dten\u00fdch odd\u00edl\u016f knihy. M\u011blo by tam b\u00fdt nejm\u00e9n\u011b tiskov\u00fdch chyb, ale nen\u00ed.<\/p>\n

Mimochodem, pokud jste n\u011bkdy uva\u017eovali o p\u0159e\u010dten\u00ed TAOCP, zkuste to. Mnoz\u00ed \u0159eknou, \u017ee je to p\u0159\u00edru\u010dka<\/b>, kter\u00e1 nen\u00ed ur\u010dena pro p\u0159\u00edm\u00e9 \u010dten\u00ed, ale to nen\u00ed pravda. Autor m\u00e1 jasn\u00fd n\u00e1zor a jedine\u010dn\u00fd styl. Jedin\u00e1 v\u011bc, kter\u00e1 br\u00e1n\u00ed \u010ditelnosti, je slo\u017eitost matematiky. Existuje v\u0161ak jednoduch\u00e9 \u0159e\u0161en\u00ed: \u010dt\u011bte, dokud nedojdete k matematice, kterou nerozum\u00edte, p\u0159esko\u010dte ji a otev\u0159ete dal\u0161\u00ed odd\u00edl, kter\u00fd m\u016f\u017eete pochopit. \u010cten\u00edm t\u00edmto zp\u016fsobem p\u0159esko\u010d\u00edm alespo\u0148 80% knihy, ale zb\u00fdvaj\u00edc\u00edch 20% je skv\u00e9l\u00e9!<\/p>\n

Tak\u00e9 se \u0159\u00edk\u00e1, \u017ee TAOCP nerelevantn\u00ed<\/b>, zastaral\u00e1 nebo jinak nevhodn\u00e1 pro \u201eskute\u010dn\u00e9 programov\u00e1n\u00ed\u201c. To nen\u00ed pravda. Nap\u0159\u00edklad v prvn\u00ed \u010d\u00e1sti po \u00favodu se zkoum\u00e1 vyhled\u00e1v\u00e1n\u00ed prvku v neset\u0159\u00edd\u011bn\u00e9m poli. Nejjednodu\u0161\u0161\u00ed algoritmus je v\u0161em program\u00e1tor\u016fm zn\u00e1m\u00fd. Spus\u0165te ukazatel na za\u010d\u00e1tku pole a pot\u00e9 v cyklu prove\u010fte n\u00e1sleduj\u00edc\u00ed kroky:<\/p>\n

    \n
  1. Zkontrolujte, zda je aktu\u00e1ln\u00ed prvek t\u00edm po\u017eadovan\u00fdm. Pokud ano, vra\u0165te ho; jinak\n<\/li>\n
  2. zkontrolujte, zda nen\u00ed ukazatel mimo pole. Pokud ano, vra\u0165te chybu; jinak\n<\/li>\n
  3. zvy\u0161te ukazatel a pokra\u010dujte.<\/li>\n<\/ol>\n

    \nNyn\u00ed zva\u017ete: kolik kontrol hranic tento algoritmus vy\u017eaduje v pr\u016fm\u011bru? V nejhor\u0161\u00edm p\u0159\u00edpad\u011b, kdy\u017e pole neobsahuje prvek, bude ka\u017ed\u00e9mu prvku v seznamu pot\u0159eba jedna kontrola, a v pr\u016fm\u011bru to bude n\u011bco jako \"Dostal. Inteligentn\u011bj\u0161\u00ed vyhled\u00e1vac\u00ed algoritmus m\u016f\u017ee pou\u017e\u00edt pouze jednu kontrolu hranice. P\u0159ipevn\u011bte po\u017eadovan\u00fd prvek na konec pole, pot\u00e9 spus\u0165te ukazatel na za\u010d\u00e1tku pole a v cyklu prove\u010fte n\u00e1sleduj\u00edc\u00ed kroky:<\/p>\n

      \n
    1. Zkontrolujte, zda je aktu\u00e1ln\u00ed prvek t\u00edm po\u017eadovan\u00fdm. Pokud ano, vra\u0165te odpov\u011b\u010f, pokud je ukazatel uvnit\u0159 pole, nebo chybu, pokud tomu tak nen\u00ed. Jinak\n<\/li>\n
    2. zvy\u0161te ukazatel a pokra\u010dujte.<\/li>\n<\/ol>\n

      \nA\u0165 u\u017e tak \u010di onak, prvek bude zaru\u010den\u011b nalezen a kontrola hranice je provedena pouze jednou, kdy\u017e se to stane. To je hlubok\u00e1 my\u0161lenka, ale je dost jednoduch\u00e1 i pro za\u010d\u00ednaj\u00edc\u00edho program\u00e1tora. Asi nemohu mluvit o relevanci t\u00e9to pr\u00e1ce pro ostatn\u00ed, ale okam\u017eit\u011b jsem tuto moudrost uplatnil jak ve sv\u00e9m osobn\u00edm, tak v profesion\u00e1ln\u00edm k\u00f3du. Kniha TAOCP je pln\u00e1 takov\u00fdch perel (abych byl spravedliv\u00fd, obsahuje tak\u00e9 spoustu podivn\u00fdch v\u011bc\u00ed, jako je bublinkov\u00e9 t\u0159\u00edd\u011bn\u00ed<\/a><\/noindex>).<\/p>\n

      \u201eHled\u00e1n\u00ed, hled\u00e1n\u00ed
      \nTak dlouho
      \nHled\u00e1n\u00ed, hled\u00e1n\u00ed
      \nCht\u011bl jsem jen tan\u010dit\u201c<\/i>
      \n\u2014 Luther Vandross, \u201eHled\u00e1n\u00ed\u201c (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Tiskov\u00e1 chyba \u010d. 2<\/h1>\n

      \nDruh\u00fd tiskov\u00fd omyl je v Tomu 4A, \u201eKombinatorick\u00e9 algoritmy\u201c, \u010d\u00e1st 1. Na str\u00e1nce 60 je pops\u00e1n \u00fakol pl\u00e1nov\u00e1n\u00ed vystoupen\u00ed komik\u016f v r\u016fzn\u00fdch kasinech. Jako p\u0159\u00edklad je uvedeno n\u011bkolik skute\u010dn\u00fdch komik\u016f, v\u010detn\u011b Lily Tomlin, Weird Al Yankovice a Robina Williamse, kter\u00fd byl je\u0161t\u011b na\u017eivu, kdy\u017e kniha vy\u0161la. Knuth v\u017edy uv\u00e1d\u00ed v rejst\u0159\u00edku pln\u00e1 jm\u00e9na, tak\u017ee Williams je zm\u00edn\u011bn na str\u00e1nce 882 jako \u201eWilliams, Robin Mac-Lorin\u201c. Jeho druh\u00e9 jm\u00e9no kon\u010d\u00ed na \u201en\u201c, nikoli na \u201em\u201c, tedy Mac-Lorin.<\/p>\n

      Mac-Lorin je d\u00edv\u010d\u00ed jm\u00e9no jeho matky. Byla pravnu\u010dkou Anselma Josepha Mac-Lorina, 34. guvern\u00e9ra Mississippi. Jeho vl\u00e1da se z\u0159ejm\u011b nezapamatovala ni\u010d\u00edm pozitivn\u00edm. Z knihy \u201eMississippi: historie\u201c<\/a><\/noindex>:<\/p>\n

      \u201eNejd\u016fle\u017eit\u011bj\u0161\u00edm bodem b\u011bhem administrativy Mac-Lorina bylo vyhl\u00e1\u0161en\u00ed v\u00e1lky \u0160pan\u011blsku ze strany Spojen\u00fdch st\u00e1t\u016f na ja\u0159e 1898\u2026 Bohu\u017eel v\u00e1lka mohla n\u011bkter\u00fdm \u00fa\u0159edn\u00edk\u016fm poskytnout p\u0159\u00edle\u017eitosti k praktikov\u00e1n\u00ed \u00faplatk\u00e1\u0159stv\u00ed. Mac-Lorin byl obvin\u011bn z r\u016fzn\u00fdch pochybnost\u00ed, v\u010detn\u011b nepoctivosti a nadm\u011brn\u00e9ho vyu\u017e\u00edv\u00e1n\u00ed pravomoc\u00ed k omilost\u0148ov\u00e1n\u00ed. V \u00e9\u0159e hnut\u00ed za st\u0159\u00edzlivost ho kritici obvinili z opilstv\u00ed, co\u017e ve\u0159ejn\u011b p\u0159iznal.\u201c<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Historick\u00e1 chyba<\/h1>\n

      \nZva\u017eme tradi\u010dn\u00ed algoritmus n\u00e1soben\u00ed<\/b> ze \u0161koln\u00edho programu. Kolik vy\u017eaduje jednoprizmatick\u00fdch n\u00e1soben\u00ed? P\u0159edpokl\u00e1dejme, \u017ee n\u00e1sob\u00edte \"Dostal-m\u00edstn\u00e9 \u010d\u00edslo \"Dostal na \"Dostal-m\u00edstn\u00e9 \"Dostal. Nejprve n\u00e1sob\u00edte prvn\u00ed \u010d\u00edslici \"Dostal ka\u017edou \u010d\u00edslic\u00ed \"Dostal po\u0159ad\u011b. Pot\u00e9 n\u00e1sob\u00edte druhou \u010d\u00edslici \"Dostal ka\u017edou \u010d\u00edslic\u00ed \"Dostal po\u0159ad\u011b a tak d\u00e1le, dokud neprojdete v\u0161emi \u010d\u00edslicemi \"Dostal. T\u00edmto zp\u016fsobem tradi\u010dn\u00ed n\u00e1soben\u00ed vy\u017eaduje \"Dostal prim\u00e1rn\u00edch n\u00e1soben\u00ed. Zejm\u00e9na n\u00e1soben\u00ed dvou \u010d\u00edsel podle \"Dostal m\u00edstnost\u00ed vy\u017eaduje \"Dostal jednoprizmatick\u00e1 n\u00e1soben\u00ed.<\/p>\n

      To je \u0161patn\u00e9, ale proces lze optimalizovat pomoc\u00ed metody vyvinut\u00e9 sov\u011btsk\u00fdm matematikem Anatolijem Alexejevi\u010dem Karacubou. P\u0159edpokl\u00e1dejme, \u017ee \"Dostal a \"Dostal\u00a0jsou dvoucifern\u00e1 des\u00edtkov\u00e1 \u010d\u00edsla; to znamen\u00e1, \u017ee existuj\u00ed \u010d\u00edsla \"Dostal, \"Dostal, \"Dostal, \"Dostal takov\u00e1, \u017ee \"Dostal a \"Dostal (generalizace tohoto algoritmu na v\u011bt\u0161\u00ed \u010d\u00edslice vy\u017eaduje ur\u010dit\u00e9 manipulace; i kdy\u017e to nen\u00ed p\u0159\u00edli\u0161 slo\u017eit\u00e9, abych se ve detailech nespletl, rad\u011bji se budu dr\u017eet jednoduch\u00e9ho p\u0159\u00edkladu). Potom \"Dostal, \"Dostal, \"Dostal. N\u00e1soben\u00ed dvoj\u010dlen\u016f d\u00e1v\u00e1 \"Dostal. V tuto chv\u00edli m\u00e1me st\u00e1le \"Dostal jednoprizmatick\u00e9ho n\u00e1soben\u00ed: \"Dostal, \"Dostal, \"Dostal, \"Dostal. Nyn\u00ed se\u010dt\u011bme a ode\u010dt\u011bme \"Dostal. Po n\u011bkolika p\u0159eh\u00e1zen\u00edch, kter\u00e1 nech\u00e1m jako cvi\u010den\u00ed pro \u010dten\u00e1\u0159e, to vyjde \"Dostal\u00a0\u2014 celkem t\u0159i jednocifern\u00e9 n\u00e1soben\u00ed! (Existuj\u00ed ur\u010dit\u00e9 konstantn\u00ed koeficienty, ale ty lze spo\u010d\u00edtat pouze s\u010d\u00edt\u00e1n\u00edm a posunov\u00e1n\u00edm cifer).<\/p>\n

      Ne\u017e\u00e1dejte o d\u016fkaz, ale Karacub\u016fv algoritmus<\/b> (rekurzivn\u011b obecn\u011b roz\u0161\u00ed\u0159en\u00fd z v\u00fd\u0161e uveden\u00e9ho p\u0159\u00edkladu) zlep\u0161uje tradi\u010dn\u00ed metodu n\u00e1soben\u00ed ze \"Dostal operac\u00ed na \"Dostal. V\u0161imn\u011bte si, \u017ee se jedn\u00e1 o skute\u010dn\u00e9 zlep\u0161en\u00ed algoritmu, a ne optimalizaci pro v\u00fdpo\u010dty v mysli. Opravdu, algoritmus nen\u00ed vhodn\u00fd pro po\u010d\u00edt\u00e1n\u00ed v mysli, proto\u017ee vy\u017eaduje vysok\u00e9 n\u00e1klady na rekurzivn\u00ed operace. Nav\u00edc se efekt pln\u011b neprojev\u00ed, dokud \u010d\u00edsla nebudou dostate\u010dn\u011b velk\u00e1 (na\u0161t\u011bst\u00ed m\u00edsto Karacubova algoritmu p\u0159i\u0161ly je\u0161t\u011b rychlej\u0161\u00ed metody: v b\u0159eznu 2019 byl zve\u0159ejn\u011bn algoritmus, kter\u00fd vy\u017eaduje pouze n log n<\/i><\/a><\/noindex> n\u00e1soben\u00ed; urychlen\u00ed se vztahuje pouze na nesm\u00edrn\u011b velk\u00e1 \u010d\u00edsla).<\/p>\n

      Tento algoritmus je pops\u00e1n na stran\u011b 295 druh\u00e9ho svazku \u201eN\u00e1sleduj\u00edc\u00edch algoritm\u016f\u201c. Tam Knuth p\u00ed\u0161e: \u201eZaj\u00edmav\u00e9 je, \u017ee tuto my\u0161lenku objevili pouze v 1962<\/b> roce\u201c, kdy byla zve\u0159ejn\u011bna studie popisuj\u00edc\u00ed Karacub\u016fv algoritmus. Ale! V roce 1995 Karacuba zve\u0159ejnil \u010dl\u00e1nek \u201eSlo\u017eitost v\u00fdpo\u010dt\u016f\u201c, ve kter\u00e9m \u0159\u00edk\u00e1 n\u011bkolik v\u011bc\u00ed: 1) kolem roku 1956 Kolmogorov p\u0159edpokl\u00e1dal, \u017ee n\u00e1soben\u00ed nelze prov\u00e9st za m\u00e9n\u011b ne\u017e \"Dostal krok\u016f; 2) v 1960<\/b> roce se Karacuba z\u00fa\u010dastnil semin\u00e1\u0159e, kde Kolmogorov p\u0159edstavil svou hypot\u00e9zu n\u00b2. 3) \u201eP\u0159esn\u011b za t\u00fdden\u201c Karacuba vyvinul algoritmus \u201erozd\u011bl a panuj\u201c; 4) v roce 1962 Kolmogorov napsal a zve\u0159ejnil \u010dl\u00e1nek jm\u00e9nem Karacuby<\/i> s popisem algoritmu. \u201eO tomto \u010dl\u00e1nku jsem se dozv\u011bd\u011bl a\u017e pot\u00e9, co ho p\u0159etiskli.\u201c<\/p>\n

      T\u00edm p\u00e1dem chyba spo\u010d\u00edv\u00e1 v tom, \u017ee m\u00edsto 1962<\/i> byl uveden 1960<\/i> rok. To je v\u0161e.<\/p>\n

      Anal\u00fdza<\/h1>\n

      \nHled\u00e1n\u00ed chyb nevy\u017eadovalo zvl\u00e1\u0161tn\u00ed dovednosti.<\/b><\/p>\n

        \n
      1. Prvn\u00ed chyba byla tak ban\u00e1ln\u00ed, jak je to jen mo\u017en\u00e9, a nach\u00e1zela se na relativn\u011b viditeln\u00e9m m\u00edst\u011b (na za\u010d\u00e1tku kapitoly). Jak\u00fdkoli idiot by ji na\u0161el; prost\u011b jsem se ocitl t\u00edm idiotem.\n<\/li>\n
      2. Hled\u00e1n\u00ed druh\u00e9 chyby vy\u017eadovalo \u0161t\u011bst\u00ed a \u00fasil\u00ed, nikoli dovednost. Index pro \u201eWilliamse\u201c se nach\u00e1z\u00ed na p\u0159edposledn\u00ed str\u00e1nce svazku, co\u017e je pom\u011brn\u011b v\u00fdrazn\u00e1 \u010d\u00e1st knihy. Pr\u00e1v\u011b jsem proch\u00e1zel indexem (to nen\u00ed tak bolestn\u00e9, jak se zd\u00e1, proto\u017ee v indexech Knutha jsou skryt\u00e9 velikono\u010dn\u00ed vaj\u00ed\u010dka. Nap\u0159\u00edklad tam jsou z\u00e1znamy v arab\u0161tin\u011b a hebrej\u0161tin\u011b, a oba odkazuj\u00ed na str\u00e1nku 66. Ale na t\u00e9to str\u00e1nce nen\u00ed zm\u00edn\u011bn \u017e\u00e1dn\u00fd z jazyk\u016f; m\u00edsto toho se zde zmi\u0148uj\u00ed \u201ejazyky \u010dten\u00e9 zprava doleva\u201c). A m\u00e1 pozornost upoutalo druh\u00e9 jm\u00e9no. Proto\u017ee obvykle \u010dtu Wikipedii, tak jsem zkontroloval Robina Williamse a v\u0161iml jsem si nesrovnalosti.\n<\/li>\n
      3. Cht\u011bl bych \u0159\u00edci, \u017ee jsem vedl v\u00e1\u017en\u00fd v\u00fdzkum, abych na\u0161el historickou chybu, ale ve skute\u010dnosti jsem se prost\u011b pod\u00edval na str\u00e1nku Wikipedie o Karatsubov\u011b algoritmu.<\/a><\/noindex>V prvn\u00edch \u0159\u00e1dc\u00edch je naps\u00e1no: \u201eKaratsub\u016fv algoritmus je algoritmus pro rychl\u00e9 n\u00e1soben\u00ed. Objeven Anatolijem Karatsubou v roce 1960 a publikov\u00e1n v roce 1962.\u201c Po tomto zb\u00fdvalo pouze se\u010d\u00edst dvakr\u00e1t dv\u011b.<\/li>\n<\/ol>\n

        \nV budoucnu bych cht\u011bl naj\u00edt podstatn\u011bj\u0161\u00ed chybu, zejm\u00e9na v Knuthov\u011b k\u00f3du. Cht\u011bl bych tak\u00e9 naj\u00edt chybu v prvn\u00edm svazku \u201eZ\u00e1kladn\u00ed algoritmy\u201c. Mo\u017en\u00e1 bych n\u011bjakou na\u0161el, ale v m\u00edstn\u00ed knihovn\u011b z n\u011bjak\u00e9ho d\u016fvodu maj\u00ed pouze svazky 2, 3 a 4A.<\/p>\n

        Finan\u010dn\u00ed fakta:<\/b><\/p>\n