Новак Калуджерович писал арифметику больших чисел для криптографической библиотеки и нашёл ошибку в Algorithm D — том самом длинном делении из книги Кнута, которое перепечатано в сотнях реализаций.

Суть места, где всё ломается: очередная цифра частного сначала оценивается по старшим разрядам, а потом оценка исправляется. Кнут утверждает, что после коррекции она гарантированно помещается в один разряд. Контрпример нашёлся в системе счисления по основанию 3: делим 45 на 16, правильное частное 2, а пробная оценка 5. После двух коррекций оценка всё ещё двухразрядная, и дальнейшее умножение берёт только младший разряд, вычитая фактически ноль.

Ошибка десятилетиями оставалась незаметной, потому что зависит от того, как именно ведёт себя аппаратное деление на конкретной архитектуре. На современных машинах с основанием два в шестьдесят четвёртой она практически не проявляется.

Автор написал Кнуту и получил тот самый гексадецимальный доллар — чек за найденную ошибку — с рукописной пометкой, что Algorithm D читают чаще многих других алгоритмов книги.

@prog_stuff