Рецензии на книгу
"Алгоритмические трюки для программистов"

03.08.2005
RSDN.RU (портал)
Лаптев Валерий
http://www.rsdn.ru/res/book/prog/worren.xml

Знаете ли Вы Первый закон творческого программирования? Он используется в качестве эпиграфа в книге Уоррена и звучит так:

     Cтоимость сопровождения программного обеспечения пропорциональна

     квадрату творческих способностей программиста.

      Роберт Д. Блисc Это, конечно, шутка, но в ней, как всегда, есть изрядная доля правды. Я эту книжку мог бы купить даже за один эпиграф! Но Вы - это не я, поэтому расскажу, о чем в книге написано. Уже по оглавлению можно судить о содержании. Множество изящнейших решений задач, которые время от времени появляются в форуме "Этюды для программистов". Уже на первой странице первой главы есть несколько простых формул. Одна из них x & (x-1) Как вы думаете, для чего она может пригодиться? Оказывается, так можно обнулить крайний справа единичный бит. И таких формул - море! Но книжка ценна не только простыми формулами. Здесь огромное количество алгоритмов. Например, в главе 11 приводится аппаратный алгоритм вычисления целочисленного квадратного корня, в котором используются только операции вычитания, сдвига вправо, и логического или (- >> | в нотации С). Считать все алгоритмы я не стал, но то, что их больше сотни - это факт! Алгоритмы написаны в одной из двух нотаций: либо на псевдо-С (очень похож на настоящий), либо в кодах гипотетической трехадресной RISC-машины, которая (ИМХО) сильно похожа на кнутовскую MMIX. В первой главе Уоррен приводит полное ее описание. В общем, понятно написано.

В книжке СОВСЕМ нет никакой воды - сплошная информация. Читать ее в автобусе или в метро - трудно. Если хочешь понять, почему работает, то надо вдумчиво, за столом разбирать много примеров. Изучение (не чтение, нет) этой книги существенно повысит понимание встроенных типов данных (особенно целых) и многих нюансов работы процессора. Для большинства алгоритмов приводится математическое доказательство корректности - для некоторых это может быть интересно. Книгу можно использовать и при разработке компилятора - тут прямо приводятся оптимизационные формулы и алгоритмы. Например, на странице 206 приводится алгоритм вычисления 2^n в компиляторе IBM XL Fortran. Полезна книга окажется и для разработчиков систем реального времени, где критично время вычислений. Да и в обычных приложениях найдется, где можно применить что-нибудь из этой книжки.

И напоследок. В 80-е годы в сборнике Уэзерелла "Этюды для программистов" была опубликована наверное самая знаменитая задача (по крайней мере, в России): написать программу, которая выводит свой собственный текст. Файлы использовать нельзя. Автор приводит САМУЮ КОРОТКУЮ программу на С, из известных ему, содержащую всего 64 символа. Написана Владом Таировым и Рашидом Фахреевым.

main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);} Печатает саму себя - проверено в Borland C++ 3.1 в режиме трансляции С-программ без отладочной информации для UNIX V. Конечно, с высоты современных стандартов это уродец, но в данном случае это неважно. Книга содержит и учит находить такие нестандартные решения. Почитайте - не пожалеете.

18.09.2003
Открытые системы
Г.И. Рузайкин

Вторая книга — Hacker’s Delight — является сборником программных приемов, собранных ее автором, Генри Уореном. Как отмечено в предисловии, «главная тема книги — рассмотреть базовые структурные отношения среди целых чисел и битовых строк, а также эффективные операции над ними». Во «Вступлении» автор уточняет: «Основное внимание уделено приемам работы с отдельными машинными словами или командами. Чаще всего в таких приемах используется смесь арифметических и логических команд».

Свою книгу автор начал с введения системы обозначений, команд и модели оценки времени их выполнения, рассмотрел «основы» — манипуляции с битами, словами, логические операции, сложение и многие другие действия, всего 20 функций. В последующих главах полезные алгоритмы подсчета битов, поиска и перестановки битов и байтов в слове. Эффективные приемы реализации компьютерной арифметики продемонстрированы в книге на алгоритмах выполнения округления до степени «2» и вычисления границ целых чисел, их сумм и разностей, а также логических выражений. Рассмотрены способы реализации алгоритмов вычисления целочисленных значений некоторых элементарных функций, использующих методы дихотомии. Приведены приемы для вычисления квадратного и кубического корней, степени и логарифма целых чисел.

Глава, посвященная приемам использования различных систем счисления в программировании, для большинства читателей книги явится «изысканным блюдом». Несколько завершающих глав книги описывают хорошо известные математические задачи, весьма полезные при программировании. Автор выбрал приемы построения кода Грея, кривой Гилберта, простых чисел, позволяющие при программировании реализовывать перебор без повторов всех n–разрядных двоичных чисел и всех целочисленных точек произвольного квадрата на плоскости, а также вычислять по известным из теории чисел формулам простые числа. В книге коротко рассмотрены отношения целых чисел и чисел с плавающей точкой, точнее автор критически анализирует рекомендации стандарта IEEE 754-1985.

Однако необходимо отметить, что перевод и редактирование книги вызывают ряд замечаний. Первое, не удачен перевод заглавия, в котором сделан акцент на «трюках», тогда как гораздо важнее демонстрация автором самого того пути к трюкам, которым он прошел. Второе замечание касается напрасных попыток переводчика или редактора заменять устоявшиеся термины, например, «дихотомия» на «бинарный поиск» или округление «до числа» на «к числу» — при чтении такого перевода создается впечатление, что предыдущего опыта не существует. Вряд ли стоит забывать, что теория чисел много старше computer science.