Donald Knuth maoy usa ka computer scientist nga nagpakabana pag-ayo sa katukma sa iyang mga libro nga iyang gisugyot usa ka hex nga dolyar ($2,56, 0x$1,00) alang sa bisan unsang "sayup" nga nakit-an, diin ang usa ka sayup gihubit nga bisan unsang butang nga "sa teknikal, kasaysayan, tipograpikal, o politikal nga dili husto." Gusto gyud nako nga makakuha usa ka tseke gikan sa Knuth, mao nga nakahukom ko nga pangitaon ang mga sayup sa iyang magnum opus "Ang Arte sa Programming" (TAOCP). Nakapangita mig tulo. Tinuod sa iyang pulong, nagpadala si Knut og tseke 0x$3,00.

Sama sa imong nakita, dili kini tinuod nga tseke. Kaniadto nagpadala si Knuth og tinuod nga mga tseke, apan mihunong sa 2008 tungod sa kaylap nga pagpanglimbong. Siya karon nagpadala sa "personal nga mga sertipiko sa deposito" sa Bangko sa San Serriff (BoSS). Matod niya andam siyang magpadala og tinuod nga kuwarta kon gikinahanglan, apan morag hasol kaayo kini.

Nakakita kog duha ka typo ug usa ka historical error. Ilista ko sila sa han-ay sa pagkunhod sa mga butang nga walay hinungdan.

Typo #1

Ang unang typo anaa sa panid 392 sa ikatulo nga tomo “Pag-sort ug Pagpangita”, ikawalong linya gikan sa ubos: “Pagkahuman sa usa ka dili molampos nga pagpangita, usahay (usahay) tilinguhaon nga magsulod ug bag-ong rekord sa talaan nga adunay sulod. K; ang pamaagi nga naghimo niini gitawag nga search and insert algorithm. Ang sayop mao na hinuon usahay kinahanglan gayud usahay.

Siyempre, ang maong sayop dili ikatingala. Adunay kinahanglan nga pipila ka mga typo sa kini nga artikulo lamang (walay mga ganti sa pagpangita niini). Ang nakapatingala gyud kay wala kini mamatikdi sa dugay nga panahon. Ang pahina 392 wala gilubong sa lawom nga bahin sa math, kini mao ang pinakaunang panid Kapitulo 6 "Pagpangita"! Posible nga usa sa labing gibasa nga mga seksyon sa libro. Sa teorya, kinahanglan adunay labing gamay nga typo, apan wala.

By the way, kung nakahunahuna ka bahin sa pagbasa sa TAOCP, sulayi kini. Daghan ang moingon nga mao kini direktoryo, wala gituyo alang sa direktang pagbasa, apan kini dili tinuod. Ang tagsulat adunay usa ka tin-aw nga punto sa panglantaw ug usa ka talagsaon nga estilo. Ang bugtong butang nga makababag sa pagkabasa mao ang pagkakomplikado sa matematika. Bisan pa, adunay usa ka yano nga solusyon: basaha hangtod moabut ka sa matematika nga dili nimo masabtan, laktawan kini, ug adto sa sunod nga seksyon nga imong masabtan. Ang pagbasa niining paagiha, gimingaw ko sa labing menos 80% sa libro, apan ang laing 20% ​​maayo!

Giingon usab nga ang TAOCP walay labot, wala na sa panahon o dili magamit sa "tinuod nga programming". Dili usab kini tinuod. Pananglitan, ang unang seksyon human sa pasiuna nagtan-aw sa pagpangita sa usa ka elemento sa usa ka unsorted array. Ang pinakasimple nga algorithm pamilyar sa tanan nga mga programmer. Sugdi ang pointer sa sinugdanan sa array, dayon buhata ang mosunod sa usa ka loop:

1. Susiha kung ang kasamtangan nga elemento mao ang gusto. Kon mao, among iuli kini; kon dili
2. Susiha kung ang pointer naa sa gawas sa utlanan sa array. Kung mao, ibalik ang usa ka sayup; kon dili
3. Pag-zoom in ug pagpadayon.

Karon hunahunaa: pila ka mga bound check ang gikinahanglan niini nga algorithm, sa kasagaran? Sa pinakagrabe nga kaso, diin ang array walay elemento, ang matag elemento sa listahan magkinahanglan og usa ka tseke, ug sa kasagaran kini mahimong sama sa . Ang usa ka mas maalamon nga algorithm sa pagpangita mahimong makalusot sa usa lang ka bound check. Ilakip ang gusto nga elemento sa katapusan sa array, dayon sugdi ang pointer sa sinugdanan sa array ug buhata ang mosunod sa usa ka loop:

1. Susiha kung ang kasamtangan nga elemento mao ang gusto. Kung mao, ibalik namon ang tubag kung ang pointer naa sa laray, o sayup kung wala. Kung dili
2. Pag-zoom in ug pagpadayon.

Usa ka paagi o lain, ang elemento gigarantiyahan nga makit-an, ug ang pagsusi sa mga utlanan gihimo kausa ra kung kini mahitabo. Kini usa ka lawom nga ideya, apan kini igo nga yano bisan alang sa usa ka bag-ong programmer. Tingali dili ako makasulti sa kalabutan sa trabaho ngadto sa uban, apan diha-diha dayon akong nagamit kini nga kaalam sa personal ug propesyonal nga code. Ang libro sa TAOCP puno sa ingon nga mga mutya (aron patas, adunay daghang mga katingad-an nga butang dinha, sama sa matang sa bula).

“Pangitaa, pangitaa
Dugay kaayo
Pangitaa, pangitaa
Gusto lang ko mosayaw"
- Luther Vandross, "Ang Pagpangita" (1980)

Typo #2

Ang ikaduhang typo naa sa Volume 4A, Combinatorial Algorithms, Part 1. Page 60 naghulagway sa problema nga naglambigit sa pag-iskedyul sa mga komedyante nga mopasundayag sa lain-laing mga casino. Daghang mga komedyante sa tinuod nga kinabuhi ang gikutlo isip mga pananglitan, lakip si Lily Tomlin, Weird Al Yankovic, ug Robin Williams, nga buhi pa sa dihang gimantala ang libro. Kanunay nga gilista ni Knuth ang tibuok nga mga ngalan sa indeks, mao nga gilista si Williams sa pahina 882 isip "Williams, Robin McLorim." Apan ang iyang tunga nga ngalan natapos sa "n" ug dili "m", nga mao, McLaurin.

McLaurin ang ngalan sa dalaga sa iyang inahan. Siya ang apo sa tuhod ni Anselm Joseph McLaurin, ika-34 nga Gobernador sa Mississippi. Ang iyang paghari, dayag, wala mahinumdom sa bisan unsa nga kaayohan. Gikan sa libro "Mississippi: Kasaysayan":

“Ang pinakaimportante nga hitabo sa panahon sa administrasyong McLaurin mao ang deklarasyon sa gubat sa Estados Unidos batok sa Espanya sa tingpamulak sa 1898... Ikasubo, ang gubat tingali naghatag ug kahigayonan sa pipila ka opisyal sa gobyerno sa paghimog panghiphip. Giakusahan si McLaurin sa lain-laing mga kwestyonable nga mga buhat, lakip ang nepotismo ug sobra nga paggamit sa mga gahum sa pagpasaylo. Panahon sa pagpugong sa pagpugong, giakusahan sa mga kritiko ang gobernador ingong palahubog, nga iyang giangkon sa publiko.”

Makasaysayanhong sayop

Hunahunaa tradisyonal nga multiplication algorithm gikan sa kurikulum sa eskwelahan. Pila ka single-digit nga pagpadaghan ang gikinahanglan niini? Ibutang ta nga modaghan ka -digit nga numero sa -gamay . Una i-multiply ang unang digit alang sa matag digit tagsa-tagsa. Dayon i-multiply ang ikaduhang digit alang sa matag digit sa usa-usa ug sa ingon sa hangtud nga kamo sa pinaagi sa tanan nga mga numero . Busa gikinahanglan ang tradisyonal nga pagpadaghan primitive nga pagpadaghan. Sa partikular, pagpadaghan sa duha ka numero pinaagi sa mga ranggo nga gikinahanglan single-digit nga pagpadaghan.

Kini dili maayo, apan posible nga ma-optimize ang proseso gamit ang usa ka pamaagi nga gihimo sa Sobyet nga matematiko nga si Anatoly Alekseevich Karatsuba. Magpakaaron-ingnon ta и  - duha ka digit nga decimal nga mga numero; kana mao, adunay mga numero , , , ingon niana и (Ang pag-general niini nga algorithm sa mas daghang numero nanginahanglan pipila nga pagmaniobra; bisan kung kini dili kaayo lisud, aron dili masayop sa mga detalye, mas maayo nga magpabilin ako sa usa ka yano nga pananglitan). Unya , , . Ang pagpadaghan sa binomials naghatag . Sa pagkakaron naa pa mi single-digit nga pagpadaghan: , , , . Karon atong idugang ug ipaubos . Pagkahuman sa pipila ka mga pag-usab, nga akong ibilin ingon usa ka ehersisyo alang sa magbabasa, kini nahimo  - tulo lang ka single-digit nga pagpadaghan! (Adunay pipila ka kanunay nga coefficients, apan kini mahimo lamang nga kalkulado pinaagi sa pagdugang ug pagbalhin sa mga numero).

Ayaw pagpangayo og pruweba, apan Algoritmo sa Karatsuba (recursively generalized gikan sa panig-ingnan sa ibabaw) pagpalambo sa tradisyonal nga multiplikasyon nga paagi sa mga operasyon kaniadto . Palihug timan-i nga kini usa ka tinuud nga pag-uswag sa algorithm, dili usa ka pag-optimize alang sa mga kalkulasyon sa pangisip. Sa tinuud, ang algorithm dili angay alang sa mental nga aritmetika, tungod kay nanginahanglan kini daghang mga gasto sa overhead alang sa mga recursive nga operasyon. Dugang pa, ang epekto dili hingpit nga magpakita sa kaugalingon hangtod ang mga numero mahimong igo nga kadako (maayo na lang, ang algorithm sa Karatsuba gipulihan sa labi ka paspas nga mga pamaagi: kaniadtong Marso 2019, usa ka algorithm ang gipatik nga nanginahanglan lamang n log n pagpadaghan; ang pagpatulin magamit lamang sa dili mahanduraw nga daghang numero).

Kini nga algorithm gihulagway sa panid 295 sa Tomo XNUMX, Semi-Numerical Algorithms. Didto si Knuth misulat: “Makapatingala nga kini nga ideya nadiskobrehan lamang sa 1962 tuig,” sa dihang gipatik ang usa ka artikulo nga naghubit sa algorithm ni Karatsuba. Apan! Niadtong 1995, gipatik ni Karatsuba ang usa ka papel sa "Computational Complexity," nga nag-ingon sa daghang mga butang: 1) Sa mga 1956, si Kolmogorov misugyot nga ang pagpadaghan dili mahimo sa ubos sa mga lakang; 2) sa 1960 tuig Karatsuba mitambong sa seminar diin gipresentar ni Kolmogorov ang iyang pangagpas n². 3) "Sa eksakto nga usa ka semana," gipalambo ni Karatsuba ang algorithm nga "divide and conquer"; 4) niadtong 1962, si Kolmogorov misulat ug nagpatik ug artikulo sa ngalan sa Karatsuba nga adunay usa ka paghulagway sa algorithm. "Nahibal-an ra nako ang bahin sa kini nga artikulo pagkahuman gipatik pag-usab."

Busa ang sayop mao nga sa baylo nga sa 1962 kinahanglan nga espesipiko 1960 tuig. Mao ra.

Анализ

Ang pagpangita sa mga sayup wala magkinahanglan og espesyal nga kahanas.

1. Ang unang sayop kay gamay ra kutob sa mahimo ug anaa sa medyo makita nga dapit (ang sinugdanan sa kapitulo). Bisan kinsa nga buang nga makit-an kini; Ako ra diay tong tanga.
2. Ang pagpangita sa ikaduhang typo nagkinahanglan og suwerte ug kakugi, apan dili kahanas. Ang index para sa "Williams" naa sa penultimate nga panid sa volume, usa ka prominenteng bahin sa libro. Nagpakli-pakli lang ko sa index (dili kini makaluluoy nga ingon niini, tungod kay adunay mga itlog sa Pasko sa Pagkabanhaw nga gitago sa mga indeks ni Knuth. Pananglitan, adunay mga entries sa Arabic ug Hebrew, nga parehong nagtudlo sa pahina 66. Apan ang maong panid wala maghisgot bisan asa nga mga pinulongan; hinoon kini nagtumong sa "mga pinulongan nga gibasa gikan sa tuo ngadto sa wala"). Ug ang ikaduhang ngalan nakakuha sa akong atensyon. Tungod kay kasagaran akong nagbasa sa Wikipedia, akong gisusi si Robin Williams ug nakamatikod nga adunay kalainan.
3. Nanghinaut ko nga makaingon ko nga naghimo ko og seryoso nga panukiduki aron makit-an ang usa ka kasaypanan sa kasaysayan, apan sa tinuod ako lang nangita Wikipedia nga panid mahitungod sa Karatsuba's algorithm. Ang una nga mga linya nag-ingon: "Ang Karatsuba algorithm usa ka paspas nga pagpadaghan nga algorithm. Nadiskobrehan ni Anatoly Karatsuba niadtong 1960 ug gipatik niadtong 1962." Human niana ang tanan nga nahibilin mao ang pagdugang og duha ug duha.

Sa umaabot gusto ko nga mangita usa ka labi ka hinungdanon nga bug, labi na sa code ni Knuth. Gusto usab nako nga mangita usa ka bug sa una nga volume sa Fundamental Algorithms. Tingali nakit-an ko kini, apan sa pipila ka hinungdan ang lokal nga librarya adunay mga volume nga 2, 3 ug 4A.

Pinansyal nga mga kamatuoran:

• Sa kinatibuk-an, ang akong kontribusyon sa TAOCP naglangkob lamang sa tulo ka mga karakter: usa ka dugang s, kapuli m sa n и 2 sa 0. Sa $2,56, kini mao ang pipila ka pretty dakog kita simbolo; Kung gibayran ka sa kana nga klase nga salapi, ang usa ka artikulo nga 1000 nga mga pulong (aberids nga upat ka mga karakter) mokita kanimo og napulo ka grand.
• Uban sa tulo ka hexadecimal dollars, ako, uban sa 29 ka ubang mga lungsuranon, nahigot sa ika-69 nga dapit sa listahan sa labing adunahan nga mga depositor sa San Serriff Bank (sa Mayo 1, 2019).

Ang ubang mga panaghisgot bahin sa mga tseke gikan sa Knuth

• Giunsa pagkuha ang usa ka tseke gikan sa Knuth

  Kinatibuk-ang rekomendasyon alang sa pagpangita og mga sayop sa mga libro ni Knuth. Kasagaran nabalaka sila sa mga teknikal nga sayup, nga wala nako. Adunay usa ka sugyot didto nga akong giseryoso:

  Labing maayo nga maghulat hangtod nga makolekta nimo ang usa ka hugpong sa mga sayup nga isumite. Pinaagi sa pagkombinar sa daghang tinuod apan dili kaayo bililhon nga mga sayop, imong gipadako ang posibilidad nga ang usa niini isipon gayod nga sayop o tambag. Kung magsumite ka mga sayup sa usa ka higayon, ang matag usa mahimong isalikway.

  Dili ko gusto nga magpadala lang ug walay pulos nga mga typo, apan gidawat ang tambag ug gipadala lang ang sulat kung nakit-an nako ang usa ka sayup sa kasaysayan nga ingon og grabe.

• Mga tseke ni Ashutosh Mehra

  Si Ashutosh Mehra mao ang ikatulo nga labing adunahan nga mamumuhunan sa San Serriff nga adunay dako nga kantidad nga 0x$207.f0 sa BoSS.

• Susiha ang pipila ka mga non-functional nga mga bug sa tinuod nga TeX code
• Miscellaneous: #1 #2 #3 #4 #5 #6

Source: www.habr.com