Хабрахабр

[Перевод] Я получил от Кнута чек на 0x$3,00

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

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

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

Только в этой статье обязательно найдётся несколько опечаток (никаких наград за их нахождение). Конечно, в такой ошибке нет ничего удивительного. Страница 392 не зарыта глубоко в раздел с математикой, это самая первая страница шестой главы «Поиск»! Что на самом деле удивительно, так это то, что её так долго не замечали. По идее, там должно быть меньше всего опечаток, но нет. Возможно, один из самых читаемых разделов книги.

Многие скажут, что это справочник, не предназначенный для прямого чтения, но это неправда. Кстати, если вы когда-нибудь думали почитать TAOCP, попробуйте. Единственное, что препятствует читаемости, — это сложность математики. У автора есть чёткая точка зрения и своеобразный стиль. Читая таким образом, я пропускаю по крайней мере 80% книги, но остальные 20% великолепны! Однако есть простое решение: читайте, пока не дойдёте до математики, которую вы не понимаете, пропустите её и откройте следующий раздел, который можете понять.

Это тоже неправда. Также говорят, что TAOCP нерелевантна, устарела или иным образом неприменима к «реальному программированию». Самый простой алгоритм знаком всем программистам. Например, в первом разделе после введения рассматривается поиск элемента в несортированном массиве. Запустите указатель в начале массива, затем выполните следующие действия в цикле:

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

Теперь рассмотрим: сколько проверок границ требует этот алгоритм, в среднем? В худшем случае, когда массив не содержит элемента, для каждого элемента в списке потребуется одна проверка, и в среднем это будет что-то вроде $N/2$. Более умный алгоритм поиска может обойтись всего одно проверкой границ. Прикрепите нужный элемент к концу массива, затем запустите указатель в начале массива и выполните следующие действия в цикле:

  1. Проверьте, является ли текущий элемент желаемым. Если так, возвращаем ответ, если указатель находится в пределах массива, или ошибку, если это не так. В противном случае
  2. Увеличьте указатель и продолжайте.

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

«Поиск, поиск
Так долго
Поиск, поиск
Я просто хотел танцевать»

— Лютер Вандросс, «Поиск» (1980)

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

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

Мак-Лорина обвинили в различных сомнительных практиках, включая кумовство и чрезмерное использование полномочий по помилованию. «Самым важным событием во время администрации Мак-Лорина стало объявление Соединёнными Штатами войны Испании весной 1898 года… К сожалению, война, возможно, дала некоторым государственным чиновникам возможность практиковать взяточничество. В эпоху движения за трезвость критики обвинили губернатора в пьянстве, что он публично признал».

Рассмотрим традиционный алгоритм умножения из школьной программы. Сколько он требует одноразрядных операций умножения? Предположим, вы умножаете $m$-разрядное число $x$ на $n$-разрядное $y$. Сначала умножаете первую цифру $x$ на каждую цифру $y$ по очереди. Затем умножаете вторую цифру $x$ на каждую цифру $y$ по очереди и так далее, пока не пройдёте все цифры $x$. Таким образом, традиционное умножение требует $mn$ примитивных умножений. В частности, перемножение двух чисел по $n$ разрядов требует $n^2$ одноразрядных умножений.

Предположим, что $x$ и $y$ — двузначные десятичные числа; то есть существуют числа $a$, $b$, $c$, $d$ такие, что $x = (ab)_$ и $y = (cd)_{10}$ (обобщение этого алгоритма на большие цифры требует определённых манипуляций; хотя это не слишком сложно, но чтобы не ошибиться в деталях, я лучше буду придерживаться простого примера). Это плохо, но можно оптимизировать процесс с помощью метода, разработанного советским математиком Анатолием Алексеевичем Карацубой. Умножение двучленов даёт $xy = 100ac + 10ad + 10bc + bd$. Тогда $x = 10a + b$, $y = 10c + d$, $xy = (10a + b)(10c + d)$. Теперь сложим и вычтем $10ac + 10bc$. На данный момент у нас по-прежнему $n^2 = 4$ одноразрядных умножения: $ac$, $ad$, $bc$, $bd$. (Есть некоторые постоянные коэффициенты, но их можно вычислить только сложением и сдвигом разрядов). После нескольких перестановок, которые я оставлю в качестве упражнения для читателя, получается $xy = 110ac + 11bd + 10(a - b)(d - c)$ — всего три одноразрядных умножения!

Обратите внимание, что это реальное улучшение алгоритма, а не оптимизация для расчётов в уме. Не просите доказательства, но алгоритм Карацубы (рекурсивно обобщённый из приведённого выше примера) улучшает традиционный метод умножения с $O(n^2)$ операций до $O(n^{(lg 3)})$. Кроме того, эффект проявится не в полной мере, пока цифры не станут достаточно большими (к счастью, вместо алгоритма Карацубы пришли ещё более быстрые методы: в марте 2019 года был опубликован алгоритм, требующий всего n log n умножений; ускорение применимо только к невообразимо большим числам). Действительно, алгоритм не подходит для счёта в уме, так как требует больших накладных расходов на рекурсивные операции.

Там Кнут пишет: «Любопытно, что эту идею обнаружили только в 1962 году», когда была опубликована статья, описывающая алгоритм Карацубы. Этот алгоритм описан на странице 295 второго тома «Получисленные алгоритмы». В 1995 году Карацуба опубликовал статью «Сложность вычислений», в которой говорит несколько вещей: 1) около 1956 года Колмогоров предположил, что умножение нельзя произвести менее чем в $O(n^2)$ шагов; 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
Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть