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

Както можете да видите, това не е истинска проверка. Кнут изпращаше истински чекове, но спря през 2008 г. поради необуздана измама. Сега той изпраща "лични сертификати за депозит" на Bank of San Serriff (BoSS). Той казва, че е готов да изпрати реални пари, ако е необходимо, но изглежда, че това е твърде голяма караница.

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

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

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

Разбира се, такава грешка не е изненадваща. Със сигурност ще има няколко правописни грешки само в тази статия (няма награди за намирането им). Наистина изненадващо е, че остана незабелязано толкова дълго. Страница 392 не е заровена дълбоко в математическия раздел, а е още първата страница Глава XNUMX "Търсене"! Вероятно един от най-четените раздели на книгата. На теория трябва да има най-малко правописни грешки, но не.

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

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

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

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

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

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

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

Печатна грешка #2

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

Маклорин беше моминското име на майка му. Тя беше правнучка на Анселм Джоузеф Маклаурин, 34-ти губернатор на Мисисипи. Неговото царуване, очевидно, не беше запомнено с нищо добро. От книгата „Мисисипи: История“:

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

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

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

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

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

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

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

Анализ

Откриването на грешки не изисква специални умения.

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

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

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

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

Други дискусии за чекове от Кнут

• Как да получите чек от Кнут

  Общи препоръки за намиране на грешки в книгите на Кнут. Най-вече се отнасят до технически грешки, каквито аз нямам. Там има едно предложение, което приех сериозно:

  Най-добре е да изчакате, докато съберете набор от грешки, за да ги изпратите. Комбинирайки няколко реални, но не много ценни грешки, вие увеличавате вероятността една от тях действително да се счита за грешка или съвет. Ако изпращате грешки една по една, всяка една поотделно може да бъде отхвърлена.

  Не исках да изпращам просто глупави правописни грешки, но послушах съвета и изпратих писмото едва когато открих историческа грешка, която изглеждаше достатъчно сериозна.

• Чековете на Ашутош Мехра

  Ашутош Мехра е третият най-богат инвеститор в San Serriff с огромна нетна стойност от 0x$207.f0 в BoSS.

• Проверете за някои нефункционални грешки в реалния TeX код
• Разни: #1 #2 #3 #4 #5 #6

Източник: www.habr.com