{"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\/da\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Jeg modtog en check fra Knut p\u00e5 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 en forsker inden for datalogi, der bekymrer sig s\u00e5 meget om n\u00f8jagtigheden af sine b\u00f8ger, at han tilbyder en hexadecimal dollar<\/b> ($2,56, 0x$1,00) for enhver fundet \"fejl\", hvor en fejl defineres som alt, hvad der er \"teknisk, historisk, typografisk eller politisk forkert\". Jeg \u00f8nskede virkelig at modtage en check fra Knuth, s\u00e5 jeg besluttede at lede efter fejl i hans fremragende v\u00e6rk \"Kunstens Programmering\"<\/b> (TAOCP). Jeg lykkedes med at finde tre. Trods ordet, Knuth sendte en check p\u00e5 0x$3,00<\/b>.<\/p>\n

\"Jeg
\n
\nSom du kan se, er dette ikke en rigtig check. Tidligere sendte Knuth rigtige checks, men stoppede i 2008 p\u00e5 grund af ubarmhjertig svindel<\/a><\/noindex>. Nu sender han \"personlige indbetalingscertifikater\" fra San Serriff-banken<\/a><\/noindex> (BoSS). Han siger, at han er villig til at sende rigtige penge, hvis n\u00f8dvendigt, men det ser ud til at v\u00e6re for besv\u00e6rligt.
\n<\/a><\/noindex>
\nJeg fandt to trykfejl og en historisk fejl. Jeg vil n\u00e6vne dem i r\u00e6kkef\u00f8lge efter faldende trivialisering.<\/p>\n

Trykfejl nr. 1<\/h1>\n

\nDen f\u00f8rste trykfejl findes p\u00e5 side 392 af tredje bind \"Sortering og s\u00f8gning\", ottende linje fra bunden: \"Efter et mislykket s\u00f8gning er det nogle gange (sometime) \u00f8nskeligt at indtaste en ny post i tabellen, der indeholder K<\/i>; metoden, der g\u00f8r dette, kaldes s\u00f8ge- og inds\u00e6tningsalgoritmen. Fejlen er, at i stedet for sometime<\/i><\/b> skal v\u00e6re sometimes<\/i><\/b>.<\/p>\n

Selvf\u00f8lgelig er der ikke noget overraskende ved en s\u00e5dan fejl. I denne artikel er der uden tvivl flere trykfejl (ingen bel\u00f8nninger for at finde dem). Det, der faktisk er overraskende, er, at de er blevet overset s\u00e5 l\u00e6nge. Side 392 er ikke begravet dybt i matematikafsnittet, det er den allerf\u00f8rste side<\/b> af det sjette kapitel \"S\u00f8gning\"! M\u00e5ske en af de mest l\u00e6ste sektioner i bogen. Id\u00e9en er, at der burde v\u00e6re f\u00e6rre trykfejl der, men nej.<\/p>\n

Forresten, hvis du nogensinde har overvejet at l\u00e6se TAOCP, s\u00e5 pr\u00f8v. Mange vil sige, at det er en opslagsbog<\/b>, der ikke er beregnet til direkte l\u00e6sning, men det er ikke sandt. Forfatteren har en klar synsvinkel og en s\u00e6rpr\u00e6get stil. Det eneste, der hindrer l\u00e6sbarheden, er kompleksiteten af matematikken. Men der er en simpel l\u00f8sning: L\u00e6s, indtil du n\u00e5r til den matematik, du ikke forst\u00e5r, spring over den, og \u00e5bn n\u00e6ste afdeling, som du kan forst\u00e5. P\u00e5 den m\u00e5de springer jeg over mindst 80 % af bogen, men de resterende 20 % er fremragende!<\/p>\n

Det siges ogs\u00e5, at TAOCP er irrelevant<\/b>, for\u00e6ldet eller p\u00e5 anden m\u00e5de uanvendelig til \u00abrigtig programmering\u00bb. Dette er ogs\u00e5 usandt. For eksempel behandles s\u00f8gning efter et element i et usorteret array i f\u00f8rste sektion efter introduktionen. Den simpleste algoritme er kendt af alle programm\u00f8rer. Start pegeren i begyndelsen af arrayet, og udf\u00f8r derefter f\u00f8lgende trin i en l\u00f8kke:<\/p>\n

    \n
  1. Tjek om det nuv\u00e6rende element er det \u00f8nskede. Hvis ja, return\u00e9r det; ellers\n<\/li>\n
  2. Tjek om pegeren er uden for arrayet. Hvis ja, return\u00e9r en fejl; ellers\n<\/li>\n
  3. \u00d8g pegeren og forts\u00e6t.<\/li>\n<\/ol>\n

    \nLad os nu overveje: hvor mange gr\u00e6nsekontroller kr\u00e6ver denne algoritme i gennemsnit? I v\u00e6rste fald, n\u00e5r arrayet ikke indeholder elementet, kr\u00e6ves der en kontrol for hvert element i listen, og i gennemsnit vil det v\u00e6re noget i stil med \"Jeg. En klogere s\u00f8gealgoritme kan klare sig med kun \u00e9n gr\u00e6nsekontrol. F\u00f8j det \u00f8nskede element til slutningen af arrayet, start derefter pegeren i begyndelsen af arrayet og udf\u00f8r f\u00f8lgende trin i en l\u00f8kke:<\/p>\n

      \n
    1. Tjek om det nuv\u00e6rende element er det \u00f8nskede. Hvis ja, return\u00e9r svaret, hvis pegeren er inden for arrayet, eller en fejl, hvis ikke. Ellers\n<\/li>\n
    2. \u00d8g pegeren og forts\u00e6t.<\/li>\n<\/ol>\n

      \nUanset hvad, vil elementet blive fundet, og gr\u00e6nsekontrollen udf\u00f8res kun \u00e9n gang, n\u00e5r det sker. Dette er en dyb id\u00e9, men den er enkel nok selv for en nybegyndende programm\u00f8r. Jeg kan nok ikke tale om relevansen af arbejdet for andre, men jeg kunne straks anvende denne visdom i b\u00e5de mit personlige og professionelle kode. Bogen TAOCP er fuld af s\u00e5danne perler (for retf\u00e6rdighedens skyld, der er ogs\u00e5 mange underlige ting, s\u00e5som bubblesort<\/a><\/noindex>).<\/p>\n

      \u00abS\u00f8gningen, s\u00f8gningen
      \nS\u00e5 l\u00e6nge
      \nS\u00f8gningen, s\u00f8gningen
      \nJeg ville bare danse\u00bb<\/i>
      \n\u2014 Luther Vandross, \u00abS\u00f8gning\u00bb (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Trykfejl nr. 2<\/h1>\n

      \nDen anden trykfejl er i bind 4A, \"Kombinatoriske algoritmer\", del 1. P\u00e5 side 60 beskrives en opgave med at planl\u00e6gge optr\u00e6dener for komikere i forskellige kasinoer. Som eksempel n\u00e6vnes flere virkelige komikere, herunder Lily Tomlin, Weird Al Yankovic og Robin Williams, som stadig var i live, da bogen blev udgivet. Knuth angiver altid de fulde navne i indekset, s\u00e5 Williams n\u00e6vnes p\u00e5 side 882 som \"Williams, Robin McLaurin\". Men hans mellemnavn slutter med \"n\" og ikke \"m\", det vil sige McLaurin.<\/p>\n

      McLaurin er hans moders efternavn. Hun var oldebarn af Anselm Joseph McLaurin, den 34. guvern\u00f8r i Mississippi. Hans embedsperiode huskes \u00e5benbart ikke for noget godt. Fra bogen \"Mississippi: en historie\"<\/a><\/noindex>:<\/p>\n

      \"Det vigtigste begivenhed under McLaurins administration var, at De Forenede Stater erkl\u00e6rede krig mod Spanien i for\u00e5ret 1898... Desv\u00e6rre gav krigen muligvis nogle offentlige embedsm\u00e6nd mulighed for at praktisere bestikkelse. McLaurin blev beskyldt for forskellige tvivlsomme praksisser, herunder nepotisme og overdreven brug af ben\u00e5dning. I en tid med afholdenhedsbev\u00e6gelsen blev guvern\u00f8ren kritiseret for sin alkoholisme, som han offentligt tilstod.\"<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Historisk fejl<\/h1>\n

      \nLad os overveje den traditionelle multiplikationsalgoritme<\/b> fra skolepensum. Hvor mange en-cifrede multiplikationer kr\u00e6ver den? Antag, at du multiplicerer \"Jeg-cifret tal \"Jeg og f\u00e5 en fungerende kommando. \"Jeg-cifret \"Jeg. F\u00f8rst multiplicerer du det f\u00f8rste ciffer \"Jeg med hvert ciffer \"Jeg en ad gangen. Dern\u00e6st multiplicerer du det andet ciffer \"Jeg med hvert ciffer \"Jeg en ad gangen og s\u00e5 videre, indtil du har passeret alle cifre \"Jeg. S\u00e5ledes kr\u00e6ver traditionel multiplikation \"Jeg primitive multiplikationer. Is\u00e6r kr\u00e6ver multiplikationen af to tal med \"Jeg cifre \"Jeg en-cifrede multiplikationer.<\/p>\n

      Det er ikke godt, men processen kan optimeres ved hj\u00e6lp af en metode udviklet af den sovjetiske matematiker Anatolij Alexejevitsj Karatsuba. Antag, at \"Jeg og \"Jeg\u00a0- to-cifrede decimaler; det vil sige, at der findes tal \"Jeg, \"Jeg, \"Jeg, \"Jeg s\u00e5ledes at \"Jeg og \"Jeg (generaliseringen af denne algoritme til st\u00f8rre cifre kr\u00e6ver visse manipulationer; selvom det ikke er s\u00e5 sv\u00e6rt, vil jeg hellere holde mig til et simpelt eksempel for ikke at lave fejl i detaljerne). S\u00e5 \"Jeg, \"Jeg, \"Jeg. Multiplikation af to led giver \"Jeg. Indtil nu har vi stadig \"Jeg en-cifrede multiplikationer: \"Jeg, \"Jeg, \"Jeg, \"Jeg. Lad os nu l\u00e6gge sammen og tr\u00e6kke fra \"Jeg. Efter flere omarrangementer, som jeg vil lade v\u00e6re som en opgave for l\u00e6seren, f\u00e5r man \"Jeg\u00a0\u2014 i alt tre ensteges multiplikationer! (Der er nogle permanente koefficienter, men de kan kun beregnes ved addition og bit-shifting).<\/p>\n

      Bed ikke om bevis, men Karatsuba-algoritmen<\/b> (rekursivt generaliseret fra det ovenfor n\u00e6vnte eksempel) forbedrer den traditionelle multiplikationsmetode fra \"Jeg operationer til \"Jeg. Bem\u00e6rk, at dette er en reel forbedring af algoritmen og ikke en optimering til mentale beregninger. Faktisk er algoritmen ikke velegnet til hovedregning, da den kr\u00e6ver store omkostninger til rekursive operationer. Desuden vil effekten ikke fuldt ud vise sig, f\u00f8r tallene bliver store nok (heldigvis kom der endnu hurtigere metoder efter Karatsuba-algoritmen: i marts 2019 blev der offentliggjort en algoritme, der kun kr\u00e6ver n log n<\/i><\/a><\/noindex> multiplikationer; accelerationen g\u00e6lder kun for ubegribeligt store tal).<\/p>\n

      Denne algoritme er beskrevet p\u00e5 side 295 i den anden bind af 'De beregnede algoritmer'. Der skriver Knuth: 'Det er interessant, at denne id\u00e9 kun blev opdaget i 1962<\/b> \u00e5ret', da der blev offentliggjort en artikel, der beskrev Karatsuba-algoritmen. Men! I 1995 offentliggjorde Karatsuba en artikel 'Computationskompleksitet', hvor han n\u00e6vner flere ting: 1) Omkring 1956 antog Kolmogorov, at multiplikation ikke kan udf\u00f8res med mindre end \"Jeg trin; 2) i 1960<\/b> \u00e5ret deltog Karatsuba i et seminar, hvor Kolmogorov fremlagde sin hypotese n\u00b2. 3) 'Bare en uge' senere udviklede Karatsuba 'divide and conquer'-algoritmen; 4) i 1962 skrev og offentliggjorde Kolmogorov en artikel p\u00e5 vegne af Karatsuba<\/i> med beskrivelsen af algoritmen. 'Jeg h\u00f8rte f\u00f8rst om denne artikel, efter at den blev genoptrykt.'<\/p>\n

      S\u00e5ledes ligger fejlen i, at i stedet for 1962<\/i> skal der angives 1960<\/i> \u00e5ret. Det er det hele.<\/p>\n

      Analyse<\/h1>\n

      \nFejls\u00f8gningen kr\u00e6vede ikke stor dygtighed.<\/b><\/p>\n

        \n
      1. Den f\u00f8rste fejl var s\u00e5 banal, som det overhovedet kan v\u00e6re, og l\u00e5 et relativt synligt sted (starten af kapitlet). Enhver idiot ville have fundet den; det var bare mig, der var den idiot.\n<\/li>\n
      2. At finde den anden fejl kr\u00e6vede held og flid, men ikke n\u00f8dvendigvis dygtighed. Indekset for 'Williams' findes p\u00e5 n\u00e6stsidste side af bindet, en ganske v\u00e6sentlig del af bogen. Jeg var lige i gang med at bladre i indekslisten (det er ikke s\u00e5 slemt, som det lyder, fordi Knuths indekser gemmer p\u00e5 p\u00e5ske\u00e6g. For eksempel er der poster p\u00e5 arabisk og hebraisk, og begge henviser til side 66. Men p\u00e5 denne side omtales ingen af \u200b\u200bde sprog; i stedet n\u00e6vnes 'sprog, der l\u00e6ses fra h\u00f8jre mod venstre'). Og mit opm\u00e6rksomhed blev fanget af det andet navn. Da jeg normalt l\u00e6ser Wikipedia, tjekkede jeg Robin Williams og opdagede en uoverensstemmelse.\n<\/li>\n
      3. Jeg ville \u00f8nske, jeg kunne sige, at jeg havde udf\u00f8rt en seri\u00f8s unders\u00f8gelse for at finde den historiske fejl, men jeg kiggede faktisk bare p\u00e5 Wikipedia-siden om Karatsuba-algoritmen<\/a><\/noindex>. I de f\u00f8rste s\u00e6tninger st\u00e5r der: 'Karatsuba-algoritmen er en algoritme til hurtig multiplikation. Opdaget af Anatoly Karatsuba i 1960 og offentliggjort i 1962'. Efter dette var det kun at l\u00e6gge to og to sammen.<\/li>\n<\/ol>\n

        \nI fremtiden ville jeg gerne finde en mere v\u00e6sentlig fejl, is\u00e6r i Knuths kode. Jeg ville ogs\u00e5 gerne finde en fejl i f\u00f8rste bind af 'Fundamentale algoritmer'. M\u00e5ske ville jeg finde en, men i det lokale bibliotek findes der af en eller anden grund kun bind 2, 3 og 4A.<\/p>\n

        Finansielle fakta:<\/b><\/p>\n