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

Donald Knuth<\/b>\u00a0\u2014 en forskare inom datavetenskap som bryr sig s\u00e5 mycket om korrektheten i sina b\u00f6cker att han erbjuder en hex dollar<\/b> ($2,56, 0x$1,00) f\u00f6r varje \"fel\" som hittas, d\u00e4r ett fel betraktas som allt som \u00e4r \"tekniskt, historiskt, typografiskt eller politiskt felaktigt\". Jag ville verkligen f\u00e5 en check fr\u00e5n Knuth, s\u00e5 jag best\u00e4mde mig f\u00f6r att leta efter fel i hans framst\u00e5ende verk \"Programmeringens konst\"<\/b> (TAOCP). Jag lyckades hitta tre. Trots allt, Knuth skickade en check p\u00e5 0x$3,00<\/b>.<\/p>\n

\"Jag
\n
\nSom ni ser, \u00e4r detta ingen riktig check. Tidigare skickade Knuth verkliga checkar, men han slutade med det \u00e5r 2008 p\u00e5 grund av oupph\u00f6rligt bedr\u00e4geri<\/a><\/noindex>. Nu skickar han ut \"personliga ins\u00e4ttningscertifikat\" fr\u00e5n banken San Seriff<\/a><\/noindex> (BoSS). Han s\u00e4ger att han \u00e4r beredd att skicka verkliga pengar om det beh\u00f6vs, men det verkar vara f\u00f6r besv\u00e4rligt.
\n<\/a><\/noindex>
\nJag hittade tv\u00e5 typografiska fel och ett historiskt fel. Jag listar dem i ordning av minskande trivialitet.<\/p>\n

Typografiskt fel #1<\/h1>\n

\nDet f\u00f6rsta typografiska felet \u2014 p\u00e5 sidan 392 av den tredje volymen \"Sortering och s\u00f6kning\", den \u00e5ttonde raden fr\u00e5n botten: \"Efter en misslyckad s\u00f6kning \u00e4r det ibland (sometime) \u00f6nskv\u00e4rt att infoga en ny post i tabellen, som inneh\u00e5ller K<\/i>; metoden som g\u00f6r detta kallas f\u00f6r s\u00f6k- och infogningsalgoritmen. Felet \u00e4r att ist\u00e4llet f\u00f6r sometime<\/i><\/b> b\u00f6r vara sometimes<\/i><\/b>.<\/p>\n

Sj\u00e4lvklart \u00e4r det inget f\u00f6rv\u00e5nande med ett s\u00e5dant fel. Det finns s\u00e4kert flera skrivfel i denna artikel (inga bel\u00f6ningar f\u00f6r att hitta dem). Det som verkligen \u00e4r f\u00f6rv\u00e5nande \u00e4r att det har tagit s\u00e5 l\u00e5ng tid att uppt\u00e4ckas. Sida 392 \u00e4r inte djupt begravd i matematikkapitlet, det \u00e4r den allra f\u00f6rsta sidan<\/b> i det sj\u00e4tte kapitlet \"S\u00f6kning\"! Kanske en av de mest l\u00e4sta delarna av boken. Teoretiskt sett borde det finnas minst fel d\u00e4r, men nej.<\/p>\n

F\u00f6rresten, om du n\u00e5gonsin har \u00f6verv\u00e4gt att l\u00e4sa TAOCP, g\u00f6r det. M\u00e5nga s\u00e4ger att det \u00e4r en referensbok<\/b>, inte avsedd f\u00f6r direkt l\u00e4sning, men det \u00e4r inte sant. F\u00f6rfattaren har en tydlig \u00e5sikt och en unik stil. Det enda som hindrar l\u00e4sbarheten \u00e4r komplexiteten i matematik. Men det finns en enkel l\u00f6sning: l\u00e4s tills du n\u00e5r matematiken som du inte f\u00f6rst\u00e5r, hoppa \u00f6ver den och g\u00e5 till n\u00e4sta avsnitt som du kan f\u00f6rst\u00e5. Genom att l\u00e4sa p\u00e5 det s\u00e4ttet hoppar jag \u00f6ver minst 80% av boken, men de resterande 20% \u00e4r fantastiska!<\/p>\n

Det s\u00e4gs ocks\u00e5 att TAOCP \u00e4r irrelevant<\/b>, f\u00f6r\u00e5ldrad eller p\u00e5 annat s\u00e4tt oanv\u00e4ndbar f\u00f6r \"verklig programmering\". Det \u00e4r ocks\u00e5 falskt. Till exempel, i f\u00f6rsta avsnittet efter introduktionen diskuteras s\u00f6kningen av ett element i en osorterad array. Den enklaste algoritmen \u00e4r bekant f\u00f6r alla programmerare. Starta pekaren i b\u00f6rjan av arrayen och utf\u00f6r sedan f\u00f6ljande steg i en loop:<\/p>\n

    \n
  1. Kontrollera om det nuvarande elementet \u00e4r det \u00f6nskade. Om s\u00e5 \u00e4r fallet, returnera det; annars\n<\/li>\n
  2. Kontrollera om pekaren \u00e4r utanf\u00f6r arrayen. Om s\u00e5 \u00e4r fallet, returnera ett fel; annars\n<\/li>\n
  3. \u00d6ka pekaren och forts\u00e4tt.<\/li>\n<\/ol>\n

    \nNu, l\u00e5t oss \u00f6verv\u00e4ga: hur m\u00e5nga gr\u00e4nskontroller kr\u00e4ver denna algoritm, i genomsnitt? I v\u00e4rsta fall, n\u00e4r arrayen inte inneh\u00e5ller elementet, kr\u00e4vs en kontroll f\u00f6r varje element i listan, och i genomsnitt kommer det att se ut som \"Jag. En smartare s\u00f6kalgoritm kan klara sig med bara en gr\u00e4nskontroll. F\u00e4st det \u00f6nskade elementet i slutet av arrayen, starta sedan pekaren i b\u00f6rjan av arrayen och utf\u00f6r f\u00f6ljande steg i en loop:<\/p>\n

      \n
    1. Kontrollera om det nuvarande elementet \u00e4r det \u00f6nskade. Om s\u00e5 \u00e4r fallet, returnera svaret om pekaren \u00e4r inom arrayens gr\u00e4nser, eller ett fel om den inte \u00e4r det. Annars\n<\/li>\n
    2. \u00d6ka pekaren och forts\u00e4tt.<\/li>\n<\/ol>\n

      \nS\u00e5 eller s\u00e5, kommer elementet att hittas, och gr\u00e4nskontrollen utf\u00f6rs endast en g\u00e5ng n\u00e4r det intr\u00e4ffar. Det \u00e4r en djup id\u00e9, men den \u00e4r tillr\u00e4ckligt enkel \u00e4ven f\u00f6r en nyb\u00f6rjarprogrammerare. Kanske kan jag inte tala om relevansen av arbetet f\u00f6r andra, men jag lyckades omedelbart anv\u00e4nda denna visdom i b\u00e5de personlig och professionell kod. Boken TAOCP \u00e4r full av s\u00e5dana p\u00e4rlor (f\u00f6r att vara r\u00e4ttvis, d\u00e4r finns ocks\u00e5 mycket konstiga saker, som bubbel-sortering<\/a><\/noindex>).<\/p>\n

      \"S\u00f6k, s\u00f6k
      \nS\u00e5 l\u00e4nge
      \nS\u00f6k, s\u00f6k
      \nJag ville bara dansa\"<\/i>
      \n- Luther Vandross, \"S\u00f6k\" (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Stavfel #2<\/h1>\n

      \nDen andra tryckfelet finns i volym 4A, \"Kombinatoriska algoritmer\", del 1. P\u00e5 sidan 60 beskrivs en uppgift som handlar om planering av komikers upptr\u00e4danden p\u00e5 olika kasinon. Som exempel n\u00e4mns flera verkliga komiker, inklusive Lily Tomlin, 'Weird Al' Yankovic och Robin Williams, som fortfarande levde n\u00e4r boken gavs ut. Knuth skriver alltid ut fullst\u00e4ndiga namn i sitt register, s\u00e5 Williams n\u00e4mns p\u00e5 sidan 882 som \"Williams, Robin McLaurin\". Men hans andra namn slutar p\u00e5 \"n\", inte \"m\", det vill s\u00e4ga McLaurin.<\/p>\n

      McLaurin \u00e4r hans mors flicknamn. Hon var barnbarnsbarn till Anselm Joseph McLaurin, den 34:e guvern\u00f6ren i Mississippi. Hans mandat verkar inte ha blivit ih\u00e5gkommet f\u00f6r n\u00e5got bra. Fr\u00e5n boken \"Mississippi: historia\"<\/a><\/noindex>:<\/p>\n

      \"Den viktigaste h\u00e4ndelsen under McLaurins administration var att F\u00f6renta staterna f\u00f6rklarade krig mot Spanien v\u00e5ren 1898... Tyv\u00e4rr kan kriget ha gett vissa offentliga tj\u00e4nstem\u00e4n m\u00f6jlighet att ut\u00f6va mutor. McLaurin anklagades f\u00f6r olika tvivelaktiga aktiviteter, inklusive nepotism och ett \u00f6verdrivet anv\u00e4ndande av ben\u00e5dningsmakten. Under nykterhetsr\u00f6relsen anklagade kritiker guvern\u00f6ren f\u00f6r alkoholism, n\u00e5got han offentligt erk\u00e4nde.\"<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Historiskt fel<\/h1>\n

      \nL\u00e5t oss titta p\u00e5 traditionell multiplikationsalgoritm<\/b> fr\u00e5n skolprogrammet. Hur m\u00e5nga enhetsoperationer f\u00f6r multiplikation kr\u00e4ver den? Anta att du multiplicerar \"Jag-siffrigt tal \"Jag till \"Jag-siffrigt \"Jag. F\u00f6rst multiplicerar du den f\u00f6rsta siffra \"Jag med varje siffra \"Jag i tur och ordning. Sedan multiplicerar du den andra siffran \"Jag med varje siffra \"Jag i tur och ordning och s\u00e5 vidare, tills du har g\u00e5tt igenom alla siffror \"Jag. D\u00e4rmed kr\u00e4ver traditionell multiplikation \"Jag primitiva multiplikationer. Specifikt kr\u00e4ver multiplikationen av tv\u00e5 tal med \"Jag siffror enheter av multiplikation. \"Jag Detta \u00e4r d\u00e5ligt, men man kan optimera processen med hj\u00e4lp av en metod utvecklad av den sovjetiska matematikern Anatolij Alexejevitj Karatsuba. Anta att<\/p>\n

      -\u00e4r tv\u00e5siffriga decimaler; det vill s\u00e4ga det finns tal \"Jag och \"Jag\u00a0s\u00e5dana att \"Jag, \"Jag, \"Jag, \"Jag ([generalizeringen av denna algoritm till st\u00f6rre siffror kr\u00e4ver vissa manipulationer; \u00e4ven om det inte \u00e4r alltf\u00f6r komplicerat, f\u00f6r att inte g\u00f6ra misstag i detaljerna, f\u00f6redrar jag att h\u00e5lla mig till ett enkelt exempel). D\u00e5 \"Jag och \"Jag . Multiplikation av tv\u00e5 termer ger \"Jag, \"Jag, \"Jag. Just nu har vi fortfarande \"Jagenhetsmultiplikation: \"Jag . Nu l\u00e4gger vi ihop och subtraherar \"Jag, \"Jag, \"Jag, \"Jag. \"Jag. Efter flera omflyttningar, som jag l\u00e4mnar som en \u00f6vning f\u00f6r l\u00e4saren, f\u00e5r vi \"Jag\u00a0\u2014 totalt tre enskilda multiplikationer! (Det finns vissa fasta koefficienter, men de kan bara ber\u00e4knas genom addition och skiftning av siffror).<\/p>\n

      Be inte om bevis, men Karatsubas algoritm<\/b> (rekursivt generaliserad fr\u00e5n det ovanst\u00e5ende exemplet) f\u00f6rb\u00e4ttrar den traditionella multiplikationsmetoden med \"Jag operationer till \"Jag. Observera att detta \u00e4r en verklig f\u00f6rb\u00e4ttring av algoritmen, inte en optimering f\u00f6r mentala ber\u00e4kningar. Faktum \u00e4r att algoritmen inte l\u00e4mpar sig f\u00f6r mentala ber\u00e4kningar, eftersom den kr\u00e4ver stora overheadkostnader f\u00f6r rekursiva operationer. Dessutom kommer effekten inte att manifestera sig helt f\u00f6rr\u00e4n siffrorna blir tillr\u00e4ckligt stora (lyckligtvis, ist\u00e4llet f\u00f6r Karatsubas algoritm kom \u00e4nnu snabbare metoder: i mars 2019 publicerades en algoritm som endast kr\u00e4ver n log n<\/i><\/a><\/noindex> multiplikationer; accelerationen \u00e4r till\u00e4mplig endast p\u00e5 ofattbart stora tal).<\/p>\n

      Denna algoritm beskrivs p\u00e5 sidan 295 i den andra volymen av \"Ber\u00e4kningsalgoritmer\". D\u00e4r skriver Knuth: \"Det \u00e4r intressant att denna id\u00e9 f\u00f6rst uppt\u00e4cktes \u00e5r 1962<\/b> \", n\u00e4r artikeln som beskriver Karatsubas algoritm publicerades. Men! \u00c5r 1995 publicerade Karatsuba artikeln \"Ber\u00e4kningskomplexitet\", d\u00e4r han n\u00e4mner flera saker: 1) omkring 1956 antydde Kolmogorov att multiplikation inte kan utf\u00f6ras p\u00e5 mindre \u00e4n \"Jag steg; 2) \u00e5r 1960<\/b> deltog Karatsuba i ett seminarium d\u00e4r Kolmogorov presenterade sin hypotes n\u00b2. 3) \"Exakt en vecka\" senare utvecklade Karatsuba algoritmen \"dela och h\u00e4rska\"; 4) 1962 skrev och publicerade Kolmogorov en artikel \u00e5 Karatsubas v\u00e4gnar<\/i> som beskriver algoritmen. \"Jag fick veta om denna artikel f\u00f6rst efter att den trycktes om\".<\/p>\n

      S\u00e5ledes ligger felet i att ist\u00e4llet f\u00f6r 1962<\/i> b\u00f6r det anges 1960<\/i> \u00e5r. Det \u00e4r allt.<\/p>\n

      Analys<\/h1>\n

      \nFelletande kr\u00e4vde inte s\u00e4rskild skicklighet.<\/b><\/p>\n

        \n
      1. Det f\u00f6rsta felet var s\u00e5 banalt som m\u00f6jligt och befann sig p\u00e5 ett relativt synligt st\u00e4lle (i b\u00f6rjan av kapitlet). Vilken idiot som helst skulle ha funnit det; jag r\u00e5kade bara vara den idioten.\n<\/li>\n
      2. Att hitta det andra typoskrivet kr\u00e4vde tur och flit, men inte mycket skicklighet. Indexet f\u00f6r \"Williams\" finns p\u00e5 n\u00e4st sista sidan av volymen, en ganska framtr\u00e4dande del av boken. Jag bl\u00e4ddrade just igenom indexet (det \u00e4r inte s\u00e5 synd om det som det verkar, eftersom Knuths index d\u00f6ljer p\u00e5sk\u00e4gg. Till exempel finns det poster p\u00e5 arabiska och hebreiska, och b\u00e5da pekar p\u00e5 sida 66. Men p\u00e5 denna sida n\u00e4mns inget av spr\u00e5ken; ist\u00e4llet n\u00e4mns \"spr\u00e5k som l\u00e4ses fr\u00e5n h\u00f6ger till v\u00e4nster\"). Och min uppm\u00e4rksamhet drogs till det andra namnet. Eftersom jag brukar l\u00e4sa Wikipedia, kollade jag Robin Williams och m\u00e4rkte en avvikelse.\n<\/li>\n
      3. Jag \u00f6nskar jag kunde s\u00e4ga att jag gjorde en seri\u00f6s forskning f\u00f6r att hitta det historiska felet, men i sj\u00e4lva verket tittade jag bara p\u00e5 Wikipedia-sidan om Karatsubas algoritm<\/a><\/noindex>. I f\u00f6rsta raden st\u00e5r det: \"Karatsubas algoritm \u00e4r en algoritm f\u00f6r snabb multiplikation. Uppt\u00e4ckte av Anatolij Karatsuba 1960 och publicerades 1962.\" Efter detta var det bara att l\u00e4gga ihop tv\u00e5 g\u00e5nger tv\u00e5.<\/li>\n<\/ol>\n

        \nI framtiden skulle jag vilja hitta ett mer betydande fel, s\u00e4rskilt i Knuths kod. Jag skulle ocks\u00e5 vilja hitta en bugg i f\u00f6rsta volymen av \"Fundamentala algoritmer\". Kanske skulle jag hitta en, men p\u00e5 det lokala biblioteket finns det av n\u00e5gon anledning bara volymerna 2, 3 och 4A.<\/p>\n

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