Donald Knuth on tietojenkäsittelytieteilijä, joka välittää niin paljon kirjojensa tarkkuudesta, että hän ehdottaa yksi hex dollari (2,56 dollaria, 0x 1,00 dollaria) kaikista löydetyistä "virheistä", joissa virhe määritellään mitä tahansa, mikä on "teknisesti, historiallisesti, typografisesti tai poliittisesti epäkorrektia". Halusin todella saada shekin Knuthilta, joten päätin etsiä virheitä hänen magnum opuksestaan "Ohjelmoinnin taito" (TAOCP). Onnistuimme löytämään kolme. Sanansa mukaan Knut lähetti shekin 0x3,00 dollaria.

Kuten näette, tämä ei ole todellinen tarkistus. Knuth lähetti todellisia shekkejä, mutta lopetti vuonna 2008 sen takia rehottava petos. Hän lähettää nyt "henkilökohtaisia ​​talletustodistuksia" osoitteeseen Bank of San Serriff (Pomo). Hän sanoo olevansa valmis lähettämään tarvittaessa oikeaa rahaa, mutta se näyttää olevan liian vaivalloinen.

Löysin kaksi kirjoitusvirhettä ja yhden historiallisen virheen. Listaan ​​ne tärkeysjärjestykseen.

Kirjoitusvirhe #1

Ensimmäinen kirjoitusvirhe on "Lajittelu ja etsi" kolmannen osan sivulla 392, kahdeksas rivi alhaalta: "Epäonnistuneen haun jälkeen joskus (joskus) on toivottavaa syöttää taulukkoon uusi tietue, joka sisältää K; menetelmää, joka tekee tämän, kutsutaan haku- ja lisäysalgoritmiksi. Virhe on, että sen sijaan jonkin aikaa täytyy olla joskus.

Tällainen virhe ei tietenkään ole yllättävää. Pelkästään tässä artikkelissa on varmasti muutamia kirjoitusvirheitä (ei palkintoja niiden löytämisestä). Todella yllättävää on, että se jäi huomaamatta niin pitkään. Sivu 392 ei ole haudattu syvälle matematiikan osaan, se on aivan ensimmäinen sivu Luku 6 "Haku"! Ehkä yksi kirjan luetuimmista osista. Teoriassa kirjoitusvirheitä pitäisi olla vähiten, mutta ei.

Muuten, jos olet koskaan ajatellut lukea TAOCP:tä, kokeile sitä. Monet sanovat, että näin on hakemisto, ei ole tarkoitettu suoraan luettavaksi, mutta tämä ei pidä paikkaansa. Tekijällä on selkeä näkökulma ja omaleimainen tyyli. Ainoa asia, joka haittaa luettavuutta, on matematiikan monimutkaisuus. On kuitenkin yksinkertainen ratkaisu: lue, kunnes tulet matematiikkaan, jota et ymmärrä, ohita se ja siirry seuraavaan osaan, jonka ymmärrät. Näin lukiessani kaipaan ainakin 80 % kirjasta, mutta loput 20 % on hienoa!

Sanotaan myös, että TAOCP merkityksetöntä, on vanhentunut tai ei muuten sovellu "oikeaan ohjelmointiin". Tämä ei myöskään pidä paikkaansa. Esimerkiksi ensimmäinen osa johdannon jälkeen tarkastelee elementin löytämistä lajittelemattomasta taulukosta. Yksinkertaisin algoritmi on tuttu kaikille ohjelmoijille. Aloita osoitin taulukon alusta ja tee sitten seuraava silmukassa:

1. Tarkista, onko nykyinen elementti haluamasi. Jos on, palautamme sen; muuten
2. Tarkista, onko osoitin taulukon rajan ulkopuolella. Jos on, palauta virhe; muuten
3. Lähennä ja jatka.

Mieti nyt: kuinka monta rajatarkistusta tämä algoritmi keskimäärin vaatii? Pahimmassa tapauksessa, kun taulukko ei sisällä elementtiä, jokainen listan elementti vaatii yhden tarkistuksen, ja keskimäärin se on jotain . Älykkäämpi hakualgoritmi selviäisi yhdellä rajojen tarkastuksella. Kiinnitä haluttu elementti taulukon loppuun, aloita sitten osoitin taulukon alusta ja tee seuraava silmukassa:

1. Tarkista, onko nykyinen elementti haluamasi. Jos on, palautamme vastauksen, jos osoitin on taulukon sisällä, tai virheen, jos se ei ole. Muuten
2. Lähennä ja jatka.

Tavalla tai toisella elementti löytyy varmasti, ja rajojen tarkistus suoritetaan vain kerran, kun näin tapahtuu. Tämä on syvällinen idea, mutta se on tarpeeksi yksinkertainen jopa aloittelevalle ohjelmoijalle. En ehkä osaa puhua työn merkityksestä muille, mutta pystyin heti soveltamaan tätä viisautta sekä henkilökohtaiseen että ammatilliseen koodiin. TAOCP-kirja on täynnä tällaisia ​​helmiä (rehellisyyden nimissä, siellä on myös paljon outoja asioita, kuten esim. kuplalajittelu).

"Etsi, etsi
Näkemiin
Etsi, etsi
Halusin vain tanssia"
- Luther Vandross, "The Search" (1980)

Kirjoitusvirhe #2

Toinen kirjoitusvirhe on Volume 4A, Combinatorial Algorithms, Osa 1. Sivu 60 kuvaa ongelmaa, joka liittyy koomikkojen ajoittamiseen esiintymään eri kasinoilla. Esimerkkeinä mainitaan useita tosielämän koomikoita, mukaan lukien Lily Tomlin, Weird Al Yankovic ja Robin Williams, joka oli vielä elossa kirjan ilmestyessä. Knuth listaa aina täydet nimet hakemistossa, joten Williams on listattu sivulla 882 nimellä "Williams, Robin McLorim". Mutta hänen toinen nimensä päättyy kirjaimeen "n" eikä "m", eli McLaurin.

McLaurin oli hänen äitinsä tyttönimi. Hän oli Anselm Joseph McLaurinin, Mississippin 34. kuvernöörin, tyttärentytär. Hänen hallituskauttaan ei ilmeisesti muistettu millään hyvällä. Kirjasta "Mississippi: Historia":

”McLaurinin hallinnon tärkein tapahtuma oli Yhdysvaltojen sodanjulistus Espanjalle keväällä 1898... Valitettavasti sota on saattanut tarjota joillekin hallituksen virkamiehille mahdollisuuden lahjontaan. McLaurinia syytettiin useista kyseenalaisista käytännöistä, mukaan lukien nepotismista ja armahdusvallan liiallisesta käytöstä. Raittiusliikkeen aikana kriitikot syyttivät kuvernööriä juopaasta, minkä hän julkisesti myönsi."

Historiallinen virhe

Harkita perinteinen kertolaskualgoritmi koulun opetussuunnitelmasta. Kuinka monta yksinumeroista kertolaskua se vaatii? Oletetaan, että kerrot -numeroinen numero päälle -bitti . Kerro ensin ensimmäinen numero jokaiselle numerolle yksi kerrallaan. Kerro sitten toinen numero jokaiselle numerolle yksitellen ja niin edelleen, kunnes käyt läpi kaikki numerot . Perinteinen kertolasku vaatii siis primitiivisiä kertolaskuja. Erityisesti kertomalla kaksi numeroa rivejä vaaditaan yksinumeroisia kertolaskuja.

Tämä on huono, mutta on mahdollista optimoida prosessi Neuvostoliiton matemaatikon Anatoli Aleksejevitš Karatsuban kehittämällä menetelmällä. Teeskennetäänpä sitä и  - kaksinumeroiset desimaaliluvut; eli numeroita on , , , sellasta и (Tämän algoritmin yleistäminen suurempiin lukuihin vaatii jonkin verran manipulointia; vaikka se ei ole liian vaikeaa, pysyn mieluummin yksinkertaisessa esimerkissä, jotta en tekisi virheitä yksityiskohdissa). Sitten , , . Binomien kertominen antaa . Tällä hetkellä meillä on vielä yksinumeroinen kertolasku: , , , . Nyt lisätään ja vähennetään . Muutaman uudelleenjärjestelyn jälkeen, jotka jätän lukijalle harjoitukseksi, se selviää  - vain kolme yksinumeroista kertolaskua! (Joitakin vakiokertoimia on, mutta ne voidaan laskea vain lisäämällä ja siirtämällä numeroita).

Älä pyydä todisteita, mutta Karatsuba-algoritmi (yllä olevasta esimerkistä rekursiivisesti yleistetty) parantaa perinteistä kertolaskumenetelmää kanssa operaatioita ennen . Huomaa, että tämä on todellinen parannus algoritmiin, ei optimointi mentaalisia laskelmia varten. Algoritmi ei todellakaan sovellu mentaaliaritmetiikkaan, koska se vaatii suuria yleiskustannuksia rekursiivisista operaatioista. Lisäksi vaikutus ei ilmene täysin ennen kuin luvut ovat riittävän suuria (onneksi Karatsuban algoritmi on korvattu vielä nopeammilla menetelmillä: maaliskuussa 2019 julkaistiin algoritmi, joka vaatii vain n log n kertolaskuja; kiihtyvyys koskee vain käsittämättömän suuria lukuja).

Tämä algoritmi on kuvattu osan 295, Semi-numerical Algorithms, sivulla XNUMX. Siellä Knuth kirjoittaa: "On kummallista, että tämä idea löydettiin vasta vuonna 1962 vuonna”, kun Karatsuban algoritmia kuvaava artikkeli julkaistiin. Mutta! Vuonna 1995 Karatsuba julkaisi artikkelin "Computational Complexity", jossa sanotaan useita asioita: 1) Noin 1956 Kolmogorov ehdotti, että kertomista ei voitaisi tehdä alle askeleet; 2) sisään 1960 Karatsuba osallistui seminaariin, jossa Kolmogorov esitteli hypoteesinsa n². 3) "Tasan viikossa" Karatsuba kehitti "hajoita ja hallitse" -algoritmin; 4) Vuonna 1962 Kolmogorov kirjoitti ja julkaisi artikkelin Karatsuban puolesta algoritmin kuvauksen kanssa. "Sain tietää tästä artikkelista vasta, kun se julkaistiin uudelleen."

Joten virhe on, että sen sijaan 1962 on täsmennettävä 1960 vuosi. Siinä kaikki.

Analyysi

Virheiden etsiminen ei vaatinut erityistä taitoa.

1. Ensimmäinen virhe oli mahdollisimman vähäpätöinen ja oli suhteellisen näkyvässä paikassa (luvun alku). Kuka tahansa idiootti olisi löytänyt sen; Minusta vain tuli se idiootti.
2. Toisen kirjoitusvirheen löytäminen vaati onnea ja ahkeruutta, mutta ei taitoa. "Williamsin" hakemisto on osan toiseksi viimeisellä sivulla, joka on melko näkyvä osa kirjaa. Selasin juuri hakemistoa (se ei ole niin säälittävä kuin miltä se kuulostaa, koska Knuthin hakemistoihin on piilotettu pääsiäismunia. Esimerkiksi arabiaksi ja hepreaksi on merkintöjä, jotka molemmat osoittavat sivulle 66. Mutta sillä sivulla ei mainita jompikumpi kieli; sen sijaan se viittaa "kieliin, joita luetaan oikealta vasemmalle"). Ja toinen nimi kiinnitti huomioni. Koska luen yleensä Wikipediaa, tarkistin Robin Williamsia ja huomasin ristiriidan.
3. Toivon, että voisin sanoa, että tein vakavaa tutkimusta löytääkseni historiallisen virheen, mutta todella katsoin vain Wikipedia-sivu Karatsuban algoritmista. Ensimmäiset rivit sanovat: "Karatsuba-algoritmi on nopea kertolaskualgoritmi. Anatoli Karatsuba löysi sen vuonna 1960 ja julkaisi vuonna 1962." Sen jälkeen ei ollut muuta kuin lisättävä kaksi ja kaksi.

Jatkossa haluaisin löytää merkittävämmän bugin, erityisesti Knuthin koodista. Haluaisin myös löytää virheen Fundamental Algorithms -julkaisun ensimmäisestä osasta. Ehkä olisin löytänyt sen, mutta jostain syystä paikallisessa kirjastossa on vain osat 2, 3 ja 4A.

Taloudelliset tosiasiat:

• Yhteensä panokseni TAOCP:hen koostuu vain kolmesta hahmosta: yhdestä lisäyksestä s, korvaus m päälle n и 2 päälle 0. 2,56 dollarilla nämä ovat melko tuottoisia symboleja; Jos sinulle maksettaisiin tällaista rahaa, 1000 sanan artikkeli (keskimäärin neljä merkkiä) ansaitsisi sinulle kymmenen dollaria.
• Kolmella heksadesimaalidollarilla olen 29 muun kansalaisen kanssa jaettu 69. sijalle San Serriff Bankin rikkaimpien tallettajien luettelossa (1 alkaen).

Muita keskusteluja Knuthin shekeistä

• Kuinka saada sekki Knuthilta

  Yleisiä suosituksia virheiden löytämiseksi Knuthin kirjoista. Useimmiten ne koskevat teknisiä virheitä, joita minulla ei ole. Siinä on yksi ehdotus, jonka otin vakavasti:

  On parasta odottaa, kunnes olet kerännyt joukon virheitä lähettääksesi. Yhdistämällä useita todellisia mutta ei kovin arvokkaita virheitä lisäät todennäköisyyttä, että yksi niistä todella katsotaan virheeksi tai neuvoksi. Jos lähetät virheet yksitellen, jokainen yksittäin voidaan hylätä.

  En halunnut lähettää pelkkiä typeriä kirjoitusvirheitä, vaan otin neuvoja vastaan ​​ja lähetin kirjeen vasta, kun löysin riittävän vakavan historiallisen virheen.

• Ashutosh Mehran shekit

  Ashutosh Mehra on San Serriffin kolmanneksi rikkain sijoittaja, jonka nettovarallisuus on 0x207,f0 BoSSissa.

• Tarkista todellisen TeX-koodin toimimattomien virheiden varalta
• Muut tiedot: #1 #2 #3 #4 #5 #6

Lähde: will.com