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

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

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

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

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

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

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

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

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

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

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

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

„Търсене, търсене
Толкова дълго
Търсене, търсене
Просто исках да танцувам“
— Лутър Вандрос, „Търсене“ (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 думи (в средно, с по четири символа) би донесла десет штук.
С три шестнадесетични долара деля 69-то място в списъка на най-богатите вложители на банка Сан-Серриф (към 1 май 2019 г.).

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

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