Доналд Кнут — учен в областта на информатиката, който толкова се грижи за точността на книгите си, че предлага един хекса десетичен долар ($2,56, 0x$1,00) за всяка „грешка“, открита от него, където грешка се счита всичко, което е „технически, исторически, типографски или политически неправилно“. Бях много заинтересован да получа чек от Кнут, затова реших да търся грешки в неговото изключително произведение „Изкуството на програмирането“ (TAOCP). Успях да намеря три. Вярвайки на словото, Кнут ми изпрати чек на 0x$3,00.

Както виждате, това не е истински чек. По-рано Кнут изпращаше истински чекове, но спря през 2008 година поради безразборно измамничество. Сега той разпраща „лични депозитни сертификати“ в банка Сан-Серрифф (BoSS). Той казва, че е готов да изпрати истински пари при необходимост, но изглежда, че това е твърде затруднително.

Намерих две печатни грешки и една историческа грешка. Ще ги изброя в реда на намаляване на тривиалността.

Печатна грешка №1

Първата печатна грешка — на страница 392 на третия том „Сортиране и търсене“, осмата редица отдолу: „След неуспешно търсене понякога (sometime) е желателно да въведете в таблицата нов запис, съдържащ K; методът, който прави това, се нарича алгоритъм за търсене и вмъкване. Грешката е, че вместо sometime трябва да бъде sometimes.

Разбира се, в такава грешка няма нищо изненадващо. Само в тази статия задължително ще намерите няколко печатни грешки (няма награди за тяхното намиране). Това, което наистина е изненадващо, е, че толкова дълго не са забелязвали. Страница 392 не е заровена дълбоко в раздела с математиката, а е най-първата страница на шестата глава „Търсене“! Може би един от най-често четените раздели на книгата. По принцип, там би трябвало да има най-малко печатни грешки, но не.

Между другото, ако някога сте мислили да прочетете TAOCP, опитайте. Много хора биха казали, че това е справочник, не предназначен за пряко четене, но това не е вярно. Авторът има ясна точка на гледна точка и характерен стил. Единственото, което възпрепятства четимостта, е сложността на математиката. Но има просто решение: четете, докато не стигнете до математиката, която не разбирате, пропуснете я и отворете следващия раздел, който можете да разберете. Четейки по този начин, пропускам поне 80% от книгата, но останалите 20% са великолепни!

Също така се казва, че TAOCP не е релевантна, остаряла или по другому не приложима к «реалния софтуер». Това също е неистина. Например, в първия раздел след въведението се разглежда търсенето на елемент в несортиран масив. Най-простият алгоритъм е познат на всички програмисти. Започнете с указателя в началото на масива, след това изпълнете следните стъпки в цикъл:

Проверете дали текущият елемент е желаният. Ако да, връщаме го; в противен случай
Проверете дали указателят е извън границите на масива. Ако да, връщаме грешка; в противен случай
Увеличете указателя и продължете.

Сега да разгледаме: колко проверки на границите изисква този алгоритъм, средно? В най-лошия случай, когато масивът не съдържа елемента, за всеки елемент от списъка ще е необходима една проверка, а средно това ще бъде нещо като . По-умният алгоритъм за търсене може да се оправи с една проверка на границите. Прикрепете желания елемент в края на масива, след това стартирайте указателя в началото на масива и изпълнете следните стъпки в цикъл:

Проверете дали текущият елемент е желаният. Ако да, връщаме отговора, ако указателят е в границите на масива, или грешка, ако не е. В противен случай
Увеличете указателя и продължете.

Така или иначе, елементът със сигурност ще бъде намерен, а проверката на границите се изпълнява само веднъж, когато това се случи. Това е дълбока идея, но е достатъчно проста дори за начинаещ програмист. Вероятно не мога да говоря за актуалността на работата за другите, но успях веднага да приложа тази мъдрост както в личния, така и в професионалния код. Книгата TAOCP е пълна с такива перли (по справедливост, там има и много странни неща, като б Bubble Sort).

«Търсене, търсене
Толкова дълго
Търсене, търсене
Просто исках да танцувам»
— Лутер Вандрос, «Търсене» (1980)

Типографска грешка №2

Втората грешка е в том 4A, «Комбинаторни алгоритми», част 1. На страница 60 е описан проблем с планирането на представления на комици в различни казино. Като пример са споменати няколко реални комика, включително Лили Томлин, Странен Ал Янкович и Робин Уилямс, който беше все още жив, когато излезе книгата. Кнут винаги предоставя пълните имена в указателя, затова Уилямс е споменат на страница 882 като «Уилямс, Робин Мак-Лорим». Но второто му име завършва на «н», а не на «м», тоест Мак-Лорин.

Мак-Лорин е девическото име на майка му. Тя беше правнучка на Анселм Джоузеф Мак-Лорин, 34-ти губернатор на Мисисипи. Управлението му явно не се запомня с нищо добро. Из книгата «Мисисипи: история»:

«Най-важното събитие по време на администрацията на Мак-Лорин беше обявяването на война между Съединените щати и Испания през пролетта на 1898 година... За съжаление, войната може да е дала възможност на някои държавни чиновници да практикуват корупция. Мак-Лорин беше обвинен в различни съмнителни практики, включително роднинска връзка и прекомерна употреба на правомощията за помилване. В ерата на движението за трезвеност критиците обвиняваха губернатора в алкохолизъм, което той публично признаваше.»

Историческа грешка

Нека разгледаме традиционен алгоритъм за умножение от училищната програма. Колко едноразрядни операции за умножение изисква? Да предположим, че умножавате -разрядно число на -разрядно . Първо умножавате първата цифра на всяка цифра по ред. След това умножавате втората цифра на всяка цифра по ред и така нататък, докато не преминете през всички цифри . Така традиционното умножение изисква примитивни умножения. В частност, умножаването на две числа по разреда изисква едноразрядни умножения.

Това е лошо, но може да се оптимизира процесът чрез метод, разработен от съветския математик Анатолий Алексеевич Карацуба. Да предположим, че и са двуцифрени десетични числа; тоест съществуват числа , , , такива, че и (обобщението на този алгоритъм за по-големи цифри изисква определени манипулации; макар че това не е твърде сложно, но за да не сбъркам в детайлите, по-добре ще спазвам прост пример). Тогава , , . Умножението на двучлени дава . В момента все още имаме едноразрядни умножения: , , , . Сега да съберем и извадим След няколко пренареждания, които ще оставя като упражнение за читателя, се получава — само три едноразрядни умножения! (Има някои постоянни коефициенти, но те могат да се изчислят само чрез събиране и преместване на разрядите).

Не искайте доказателство, но алгоритъмът на Карацуба (рекурсивно обобщен от посочения по-горе пример) подобрява традиционния метод на умножение от операции до . Обърнете внимание, че това е истинско подобрение на алгоритъма, а не оптимизация за счетоводство в ума. Всъщност, алгоритъмът не е подходящ за умствени изчисления, тъй като изисква значителни разходи за рекурсивни операции. Освен това, ефектът ще се прояви напълно едва когато числата станат достатъчно големи (за щастие, вместо алгоритъма на Карацуба се появиха още по-бързи методи: през март 2019 година беше публикуван алгоритъм, който изисква само n log n умножения; ускорението се прилага само за несъзнателно големи числа).

Този алгоритъм е описан на страница 295 от втория том на „Получени алгоритми“. Там Кнут пише: „Любопитно е, че тази идея е открита едва през 1962 година“, когато беше публикувана статия, описваща алгоритъма на Карацуба. Но! През 1995 година Карацуба публикува статия „Сложност на изчисленията“, в която споменава няколко неща: 1) около 1956 година Колмогоров предполага, че умножението не може да се извърши за по-малко от стъпки; 2) през 1960 година Карацуба присъства на семинар, на който Колмогоров изложил своята хипотеза n². 3) „Точно за една седмица“ Карацуба разработил алгоритъма „разделяй и властвай“; 4) през 1962 година Колмогоров написал и публикувал статия от името на Карацуба с описание на алгоритъма. „Разбрах за тази статия само след като беше препечатана.“

Така че, грешката е в това, че вместо 1962 беше посочена 1960 година. Това е всичко.

Анализ

Търсенето на грешки не изискваше особена умения.

Първата грешка беше толкова банална, колкото е възможно, и беше в сравнително видимо място (началото на главата). Всеки идиот би я открил; просто аз бях този идиот.
Търсенето на втората печатна грешка изискваше късмет и усърдие, а не умения. Индексът за „Уилямс“ се намира на предпоследната страница на тома, доста забележима част от книгата. Тъкмо прелиствах индекса (не е толкова жалко, колкото изглежда, защото в индексите на Кнут са скрити великденски яйца. Например, има записи на арабски и иврит, и двата сочат към страница 66. Но на тази страница не се споменава нито един от тези езици; вместо това се споменават „езиците, които се четат отдясно наляво“). И вниманието ми привлече второто име. Понеже обикновено чета Уикипедия, проверих Робин Уилямс и забелязах несъответствие.
Искам да кажа, че съм провел сериозно изследване, за да намеря историческа грешка, но всъщност просто погледнах страницата на Уикипедия за алгоритъма на Карацула.. В първите редове е написано: „Алгоритъмът на Карацула е алгоритъм за бързо умножение. Открит от Анатолий Карацула през 1960 г. и публикуван през 1962 г.“ След това оставаше само да събера две и две.

В бъдеще бих искал да намеря по-съществена грешка, особено в кода на Кнут. Освен това бих искал да намеря бъг в първия том на „Фундаментални алгоритми“. Може би бих намерил, но в местната библиотека по някаква причина имат само томове 2, 3 и 4A.

Финансови факти:

Общо взето, моят принос в TAOCP се състои само от три символа: едно добавяне s, замяна m на n и 2 на 0. На цена от $2.56 тези символи са доста печеливши; ако ви плащаха толкова, статия от 1000 думи (в средно по четири символа) би ви донесла десет парчета.
С три шестнадесетични долара, аз заедно с 29 други граждани деля 69-то място в списъка на най-богатите вложители в банката Сан-Серриф (към 1 май 2019 г.).

Други обсъждания на чековете от Кнут

Как да получите чек от Кнут
Общи насоки за търсене на грешки в книгите на Кнут. Основно се отнасят за технически грешки, които нямам. Там има едно изречение, което взех насериозно:
По-добре е да изчакате, докато не съберете набор от грешки за изпращане. Обединявайки няколко реални, но не много ценни грешки, ще увеличите вероятността да бъде оценена една от тях действително като грешка или съвет. Ако изпращате грешки по една, всяка поотделно може да бъде отхвърлена.
Не искам да изпращам просто глупави печатни грешки, а послушах съвета и изпратих писмо само когато намерих историческа грешка, която ми се стори достатъчно сериозна.
Чековете на Ашутош Мехра
Ашутош Мехра е третият най-богат вложител в Сан-Серрифф с колосално състояние 0x$207,f0 в BoSS.
Чек за някои нефункционални грешки в реалния код на TeX
Разнообразно: #1 #2 #3 #4 #5 #6