Donald Knuth er tölvunarfræðingur sem er svo annt um nákvæmni bóka sinna að hann stingur upp á einn hex dollar ($2,56, 0x$1,00) fyrir allar „villur“ sem finnast, þar sem villa er skilgreind sem allt sem er „tæknilega, sögulega, leturfræðilega eða pólitískt rangt“. Ég vildi endilega fá ávísun frá Knuth, svo ég ákvað að leita að villum í magnum opus hans "Listin að forritun" (TAOCP). Okkur tókst að finna þrjá. Trúur orðum sínum sendi Knútur ávísun fyrir 0x$3,00.

Eins og þú sérð er þetta ekki alvöru ávísun. Knuth sendi vanalega alvöru ávísanir en hætti 2008 vegna hömlulaus svik. Hann sendir nú út "persónuleg innstæðubréf" til Bank of San Serriff (BoSS). Hann segist tilbúinn að senda alvöru peninga ef þörf krefur, en það virðist vera of mikið vesen.

Ég fann tvær innsláttarvillur og eina söguvillu. Ég mun skrá þá í röð eftir minnkandi léttvægleika.

Innsláttarvilla #1

Fyrsta innsláttarvillan er á blaðsíðu 392 í þriðja bindi „Flokkun og leit“, áttundu línu frá botni: „Eftir árangurslausa leit er stundum (stundum) æskilegt að slá inn nýja skrá í töfluna sem inniheldur K; aðferðin sem gerir þetta er kölluð leitar- og innsetningaralgrím. Mistökin eru að í staðinn einhvern tíma ætti að vera stundum.

Slík mistök koma auðvitað ekki á óvart. Það eru víst nokkrar innsláttarvillur í þessari grein einni saman (engin verðlaun fyrir að finna þær). Það sem kemur mjög á óvart er að það fór óséður svo lengi. Síða 392 er ekki grafin djúpt í stærðfræðihlutanum, það er það fyrstu síðuna Kafli XNUMX "Leita"! Mögulega einn mest lesna hluti bókarinnar. Í orði ættu að vera fæstar innsláttarvillur, en nei.

Við the vegur, ef þú hefur einhvern tíma hugsað um að lesa TAOCP, prófaðu það. Margir munu segja að svo sé skrá, ekki ætlað til beins lestrar, en þetta er ekki satt. Höfundur hefur skýrt sjónarhorn og áberandi stíl. Það eina sem hindrar læsileika er hversu flókin stærðfræðin er. Hins vegar er einföld lausn: lestu þangað til þú kemur að stærðfræði sem þú skilur ekki, slepptu henni og farðu í næsta kafla sem þú skilur. Þegar ég les svona missi ég að minnsta kosti 80% af bókinni, en hin 20% eru frábær!

Það er líka sagt að TAOCP óviðkomandi, er úrelt eða á á annan hátt ekki við um "raunverulega forritun". Þetta er heldur ekki rétt. Til dæmis, fyrsti hluti eftir innganginn lítur á að finna frumefni í óflokkuðu fylki. Einfaldasta reikniritið er öllum forriturum kunnugt. Byrjaðu bendilinn í upphafi fylkisins, gerðu síðan eftirfarandi í lykkju:

1. Athugaðu hvort núverandi þáttur sé sá sem óskað er eftir. Ef svo er skilum við því; annars
2. Athugaðu hvort bendillinn sé fyrir utan fylkismörkin. Ef svo er, skilaðu villu; annars
3. Stækkaðu og haltu áfram.

Íhugaðu nú: hversu margar markapróf þarf þetta reiknirit að meðaltali? Í versta tilfelli, þar sem fylkið inniheldur ekki stak, mun hver þáttur á listanum þurfa eina ávísun og að meðaltali verður það eitthvað eins og . Snjallari leitarreiknirit gæti komist upp með aðeins einni markaskoðun. Festu viðkomandi frumefni við enda fylkisins, byrjaðu síðan bendilinn í byrjun fylkisins og gerðu eftirfarandi í lykkju:

1. Athugaðu hvort núverandi þáttur sé sá sem óskað er eftir. Ef svo er, skilum við svari ef bendillinn er innan fylkisins, eða villu ef svo er ekki. Annars
2. Stækkaðu og haltu áfram.

Með einum eða öðrum hætti er tryggt að þátturinn finnist og markaskoðunin er aðeins framkvæmd einu sinni þegar þetta gerist. Þetta er djúp hugmynd, en hún er nógu einföld, jafnvel fyrir nýliða forritara. Ég get sennilega ekki talað um mikilvægi verksins fyrir aðra, en ég gat strax beitt þessari visku bæði í persónulegum og faglegum siðareglum. TAOCP bókin er stútfull af slíkum gimsteinum (til að vera sanngjarn, þá er líka margt skrítið þarna inni s.s. tegund kúla).

„Leita, leita
Svo lengi
Leita, leita
Mig langaði bara að dansa"
- Luther Vandross, "Leitin" (1980)

Innsláttarvilla #2

Önnur innsláttarvillan er í bindi 4A, Combinatorial Algorithms, Part 1. Page 60 lýsir vandamáli sem felur í sér að skipuleggja grínista til að koma fram á ýmsum spilavítum. Nokkrir alvöru grínistar eru nefndir sem dæmi, þar á meðal Lily Tomlin, Weird Al Yankovic og Robin Williams, sem var enn á lífi þegar bókin kom út. Knuth skráir alltaf full nöfn í skránni, svo Williams er skráð á síðu 882 sem "Williams, Robin McLorim." En millinafn hans endar á „n“ en ekki „m“, það er McLaurin.

McLaurin var ættarnafn móður sinnar. Hún var barnabarnabarn Anselm Joseph McLaurin, 34. ríkisstjóra Mississippi. Stjórnartíð hans var greinilega ekki minnst fyrir neitt gott. Úr bók "Mississippi: Saga":

„Mikilvægasti atburðurinn í stjórnartíð McLaurin var stríðsyfirlýsing Bandaríkjanna á Spáni vorið 1898... Því miður gæti stríðið hafa veitt sumum embættismönnum tækifæri til að taka þátt í mútum. McLaurin var sakaður um ýmis vafasöm vinnubrögð, þar á meðal frændhygli og óhóflega beitingu náðunarvalds. Í hófsemishreyfingunni sökuðu gagnrýnendur ríkisstjórann um að vera handrukkari, sem hann viðurkenndi opinberlega.“

Söguleg mistök

Hugleiddu hefðbundið margföldunaralgrím úr skólanámskrá. Hversu margar eins stafa margföldun þarf til? Segjum að þú margfaldir -stafa númer á -bita . Margfaldaðu fyrst fyrsta tölustafinn fyrir hvern tölustaf eitt af öðru. Margfaldaðu síðan annan tölustafinn fyrir hvern tölustaf eitt af öðru og svo framvegis þar til þú ferð í gegnum allar tölurnar . Þannig þarf hefðbundin margföldun frumstæð margföldun. Einkum að margfalda tvær tölur með röðum sem krafist er eins stafa margföldun.

Þetta er slæmt, en það er hægt að fínstilla ferlið með aðferð sem þróuð var af sovéska stærðfræðingnum Anatoly Alekseevich Karatsuba. Við skulum láta sem það и  - tveggja stafa aukastafa tölur; það er að segja að það eru tölur , , , þannig að и (Að alhæfa þetta reiknirit yfir stærri tölur krefst nokkurrar meðhöndlunar; þó það sé ekki of erfitt, til þess að gera ekki mistök í smáatriðum, mun ég betur halda mig við einfalt dæmi). Þá , , . Margföldun tvínefna gefur . Í augnablikinu höfum við enn eins stafa margföldun: , , , . Nú skulum við leggja saman og draga frá . Eftir nokkrar endurröðun, sem ég mun skilja eftir sem æfingu fyrir lesandann, kemur í ljós  - aðeins þriggja eins stafa margföldun! (Það eru nokkrir stöðugir stuðlar, en þá er aðeins hægt að reikna út með því að bæta við og færa tölustafina til).

Ekki biðja um sönnun, en Karatsuba reiknirit (endurkvæmt alhæft úr dæminu hér að ofan) bætir hefðbundna margföldunaraðferð með aðgerðum áður . Vinsamlegast athugaðu að þetta er raunveruleg framför á reikniritinu, ekki hagræðingu fyrir hugarútreikninga. Reyndar hentar reikniritið ekki fyrir hugarreikning þar sem það krefst mikils kostnaðar við endurteknar aðgerðir. Að auki munu áhrifin ekki koma að fullu fram fyrr en tölurnar verða nógu stórar (sem betur fer hefur reiknirit Karatsuba verið skipt út fyrir enn hraðari aðferðir: í mars 2019 var reiknirit birt sem krefst aðeins n log n margföldun; hröðun á aðeins við um ólýsanlega stórar tölur).

Þessum reiknirit er lýst á blaðsíðu 295 í bindi XNUMX, Hálftalna reiknirit. Þar skrifar Knuth: „Það er forvitnilegt að þessi hugmynd hafi aðeins fundist í 1962 ári,“ þegar grein sem lýsir reiknirit Karatsuba var birt. En! Árið 1995 gaf Karatsuba út ritgerðina „Computational Complexity“ sem segir ýmislegt: 1) Um 1956 lagði Kolmogorov til að margföldun væri ekki hægt að gera á minna en skref; 2) í 1960 ári sótti Karatsuba málþingið þar sem Kolmogorov kynnti tilgátu sína n². 3) „Á nákvæmlega einni viku,“ þróaði Karatsuba „deila og sigra“ reikniritið; 4) árið 1962 skrifaði og birti Kolmogorov grein fyrir hönd Karatsuba með lýsingu á reikniritinu. „Ég komst aðeins að þessari grein eftir að hún var endurbirt.

Svo villan er sú að í staðinn fyrir 1962 verður að tilgreina 1960 ári. Það er allt og sumt.

Greining

Það þurfti ekki sérstaka kunnáttu til að finna villur.

1. Fyrsta villan var eins léttvæg og hægt var og var á tiltölulega sýnilegum stað (upphaf kaflans). Hvaða hálfviti sem er hefði fundið það; Ég reyndist bara vera þessi hálfviti.
2. Að finna seinni innsláttarvilluna krafðist heppni og dugnaðar, en ekki kunnáttu. Vísitalan fyrir "Williams" er á næstsíðustu síðu bindsins, nokkuð áberandi hluti bókarinnar. Ég var bara að fletta í gegnum vísitöluna (það er ekki eins aumkunarvert og það hljómar, því það eru páskaegg falin í vísitölunni hans Knuth. Til dæmis eru færslur á arabísku og hebresku, báðar benda á síðu 66. En sú síða nefnir ekki annað hvort tungumálið; í staðinn vísar það til „tungumála sem eru lesin frá hægri til vinstri“). Og seinna nafnið vakti athygli mína. Þar sem ég les venjulega Wikipedia athugaði ég Robin Williams og tók eftir misræmi.
3. Ég vildi að ég gæti sagt að ég gerði alvarlegar rannsóknir til að finna sögulega villu, en ég leitaði bara Wikipedia síða um reiknirit Karatsuba. Allar fyrstu línurnar segja: „Karatsuba reikniritið er hröð margföldunaralgrím. Uppgötvuð af Anatoly Karatsuba árið 1960 og gefin út árið 1962." Eftir það var ekki annað eftir en að bæta við tveimur og tveimur.

Í framtíðinni myndi ég vilja finna mikilvægari villu, sérstaklega í kóða Knuth. Mig langar líka að finna villu í fyrsta bindinu af Fundamental Algorithms. Kannski hefði ég fundið það, en af ​​einhverjum ástæðum er staðbundið bókasafn aðeins með bindi 2, 3 og 4A.

Fjárhagslegar staðreyndir:

• Alls samanstendur framlag mitt til TAOCP aðeins af þremur persónum: einni viðbót s, skipti m á n и 2 á 0. Á $2,56 eru þetta nokkuð ábatasamir tákn; Ef þú fengir borgað svona peninga myndi grein með 1000 orðum (fjórir stafir að meðaltali) þéna þér tíu þúsund krónur.
• Með þrjá sextánda dollara er ég, ásamt 29 öðrum borgurum, jafnir í 69. sæti á listanum yfir ríkustu innstæðueigendur San Serriff bankans (frá og með 1. maí 2019).

Aðrar umræður um ávísanir frá Knuth

• Hvernig á að fá ávísun frá Knuth

  Almennar ráðleggingar til að finna villur í bókum Knuth. Aðallega varða þær tæknilegar villur, sem ég hef ekki. Það er ein tillaga þarna sem ég tók alvarlega:

  Það er best að bíða þangað til þú hefur safnað upp villum til að senda inn. Með því að sameina nokkrar raunverulegar en ekki mjög dýrmætar villur, eykur þú líkurnar á því að litið sé á eina þeirra sem mistök eða ráðgjöf. Ef þú sendir inn villur eina í einu gæti hverri fyrir sig verið hafnað.

  Ég vildi ekki senda bara vitleysu innsláttarvillur, en tók ráðinu og sendi bréfið aðeins þegar ég fann sögulega villu sem virtist nógu alvarleg.

• Ávísanir Ashutosh Mehra

  Ashutosh Mehra er þriðji ríkasti fjárfestirinn í San Serriff með gríðarlega eign upp á 0x$207.f0 í BoSS.

• Athugaðu hvort einhverjar villur eru ekki virkar í alvöru TeX kóða
• Ýmislegt: #1 #2 #3 #4 #5 #6

Heimild: www.habr.com