Дональд Батіг — вчений у галузі інформатики, який настільки піклується про правильність своїх книг, що пропонує один шістнадцятковий долар ($2,56, 0x$1,00) за будь-яку знайдену помилку, де помилкою вважається все, що «технічно, історично, друкарно чи політично неправильно». Я дуже хотів отримати чек від Кнута, тому вирішив пошукати помилки у його видатній праці «Мистецтво програмування» (TAOCP). Вдалося знайти три. Вірний слову, Кнут надіслав чек на 0x$3,00.

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

Я знайшов дві помилки та одну історичну помилку. Перерахую їх у порядку зменшення тривіальності.

Помилка №1

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

Звісно, ​​у такій помилці немає нічого дивного. Тільки в цій статті обов'язково знайдеться кілька друкарських помилок (ніяких нагород за їх знаходження). Що насправді дивно, то це те, що її так довго не помічали. Сторінка 392 глибоко не зарита в розділ з математикою, це найперша сторінка шостого розділу «Пошук»! Можливо, один із найбільш читаних розділів книги. За ідеєю, там має бути найменше друкарська помилка, але ні.

До речі, якщо ви коли-небудь думали почитати TAOCP, спробуйте. Багато хто скаже, що це довідникне призначений для прямого читання, але це неправда. У автора є чітка думка і своєрідний стиль. Єдине, що перешкоджає читальності, це складність математики. Однак є просте рішення: читайте, поки не дійдете математики, яку ви не розумієте, пропустіть її і відкрийте наступний розділ, який можете зрозуміти. Читаючи таким чином, я пропускаю принаймні 80% книги, але решта 20% чудова!

Також кажуть, що TAOCP нерелевантна, застаріла чи інакше не застосовується до «реального програмування». Це також неправда. Наприклад, у першому розділі після введення розглядається пошук елемента в несортованому масиві. Найпростіший алгоритм знайомий усім програмістам. Запустіть покажчик на початку масиву, а потім виконайте такі дії в циклі:

1. Перевірте, чи поточний елемент є бажаним. Якщо так, то повертаємо його; в іншому випадку
2. Перевірте, чи знаходиться вказівник за кордоном масиву. Якщо так, то повертаємо помилку; в іншому випадку
3. Збільшіть покажчик і продовжуйте.

Тепер розглянемо: скільки перевірок кордонів потребує цей алгоритм у середньому? У гіршому випадку, коли масив не містить елемента, для кожного елемента у списку буде потрібна одна перевірка, і в середньому це буде щось на зразок . Розумніший алгоритм пошуку може обійтися лише одне перевіркою кордонів. Прикріпіть потрібний елемент до кінця масиву, потім запустіть покажчик на початку масиву та виконайте такі дії у циклі:

1. Перевірте, чи поточний елемент є бажаним. Якщо так, повертаємо відповідь, якщо вказівник знаходиться в межах масиву, або помилку, якщо це не так. В іншому випадку
2. Збільшіть покажчик і продовжуйте.

Так чи інакше, елемент гарантовано буде знайдено, а перевірка кордонів виконується лише один раз, коли це сталося. Це глибока ідея, але вона досить проста навіть для програміста-початківця. Напевно, я не можу говорити про актуальність роботи для інших, але мені одразу вдалося застосувати цю мудрість як в особистому, так і в професійному коді. Книга TAOCP сповнена таких перлин (заради справедливості, там багато і дивних речей, таких як пухирцеве сортування).

«Пошук, пошук
Так довго
Пошук, пошук
Я просто хотів танцювати»
- Лютер Вандросс, "Пошук" (1980)

Помилка №2

Друга помилка - у томі 4A, «Комбінаторні алгоритми», частина 1. На сторінці 60 описано завдання з плануванням виступів коміків у різних казино. Як приклад наводяться кілька реальних коміків, у тому числі Лілі Томлін, Дивний Ел Янкович та Робін Вільямс, який був ще живим, коли вийшла книга. Батіг завжди наводить в покажчику повні імена, тому Вільямс згадується на сторінці 882 як «Вільямс, Робін Мак-Лорім». Але його друге ім'я закінчується на "н", а не на "м", тобто Мак-Лорін.

Мак-Лорін - дівоче прізвище його матері. Вона була правнучкою Анзельма Джозефа Мак-Лоріна, 34-го губернатора Міссісіпі. Його правління, мабуть, не запам'яталося нічим добрим. Із книги «Міссісіпі: історія»:

«Найважливішою подією під час адміністрації Мак-Лоріна стало оголошення Сполученими Штатами війни Іспанії навесні 1898 року… На жаль, війна, можливо, дала деяким державним чиновникам можливість практикувати хабарництво. Мак-Лоріна звинуватили у різних сумнівних практиках, включаючи кумівство та надмірне використання повноважень з помилування. В епоху руху за тверезість критики звинуватили губернатора у пияцтві, що він публічно визнав».

Історична помилка

Розглянемо традиційний алгоритм множення зі шкільної програми. Скільки він потребує однорозрядних операцій множення? Припустимо, ви примножуєте -розрядне число на -розрядне . Спочатку множите першу цифру на кожну цифру по черзі. Потім множите другу цифру на кожну цифру по черзі і так далі, поки не пройдете всі цифри . Таким чином, традиційне множення вимагає примітивних множень. Зокрема, перемноження двох чисел за розрядів вимагає однорозрядних множень.

Це погано, але можна оптимізувати процес за допомогою методу, розробленого радянським математиком Анатолієм Олексійовичем Карацубою. Припустимо, що и  - Двозначні десяткові числа; тобто існують числа , , , такі, що и (узагальнення цього алгоритму на великі цифри вимагає певних маніпуляцій; хоча це не надто складно, але щоб не помилитися в деталях, я краще дотримуватимуся простого прикладу). Тоді , , . Розмноження двочленів дає . На даний момент у нас, як і раніше однорозрядного множення: , , , . Тепер складемо і віднімемо . Після кількох перестановок, які я залишу як вправу для читача, виходить  - всього три однорозрядні множення! (Є деякі постійні коефіцієнти, але їх можна обчислити лише додаванням та зсувом розрядів).

Не просіть доказів, але алгоритм Карацуби (Рекурсивно узагальнений з наведеного вище прикладу) покращує традиційний метод множення з операцій до . Зверніть увагу, що це реальне покращення алгоритму, а не оптимізація для розрахунків у думці. Дійсно, алгоритм не підходить для рахунку в умі, тому що потребує великих накладних витрат на рекурсивні операції. Крім того, ефект виявиться не повною мірою, поки цифри не стануть досить великими (на щастя, замість алгоритму Карацуби прийшли ще швидші методи: у березні 2019 року було опубліковано алгоритм, що потребує всього n журнал n множень; прискорення застосовується лише до неймовірно великим числам).

Цей алгоритм описаний на сторінці 295 другого тома «Опівчисленні алгоритми». Там Кнут пише: «Цікаво, що цю ідею виявили лише в 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-е місце у списку найбагатших вкладників банку Сан-Серріфф (станом на 1 травня 2019 року).

Інші обговорення чеків від Кнута

• Як отримати чек від Кнута

  Загальні рекомендації щодо пошуку помилок у книгах Батіга. Здебільшого стосуються технічних помилок, яких я не маю. Там є одна пропозиція, яку я прийняв серйозно:

  Краще почекати, поки ви не зберете набір помилок для надсилання. Поєднавши кількох реальних, але не дуже цінних помилок, ви підвищите ймовірність того, що одну з них дійсно розцінять як помилку чи пораду. Якщо надсилати помилки по одній, кожну окремо можуть відхилити.

  Я не хотів посилати просто дурні помилки, а послухався поради і відправив листа тільки коли знайшов історичну помилку, яка здалася досить серйозною.

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

  Ашутош Мехра — третій за багатством вкладник у Сан-Серріфф із колосальним станом 0x$207,f0 у BoSS.

• Чек за деякі нефункціональні помилки у реальному коді TeX
• Різне: #1 #2 #3 #4 #5 #6

Джерело: habr.com