Прочитал совершенно замечательную книжку Jack Crenshaw «Math Toolkit for Real-Time Development». Хоть она и предназначена в первую очередь для программистов «встраиваемых систем» — читал с большим удовольствием. А почему? А просто потому, что она в первую очередь — про математику, а не про программирование.
Любой относительно нормальный программист почти не задумывается над тем, как реализованы функции из «стандартной» математической библиотеки. Крайне нечасто возникают и задачи, где надо как-то учитывать, скажем, ограниченную точность чисел с плавающей запятой. Во вводных курсах программирования такие вещи практически никогда не рассматривают, а если и рассматривают — то неправильно. Например, я был в свое время очень удивлен, когда узнал, что некоторые вполне себе профессиональные программисты не имеют никакого представления об IEEE 754, и искренне считают, что вещественные числа в Delphi ведут себя так же, как вещественные числа в школьной математике.
Почему речь идет именно про «встраиваемые системы»? Книжка написана в 2000 году, задолго до того, как появилось представление об Internet of Things — и встраиваемые системы оставались последним местом, где жила всякая экзотика типа восьми- и шестнадцатибитных процессоров. Сейчас это уже немного не так, всякие PIC и AVR в более-менее серьезных местах найти уже трудно, а даже самой простенькой техникой рулят микроконтроллеры, которые по своим характеристикам уже вплотную подбираются к моему первому компьютеру (и заметьте — начинал я отнюдь не со «Спектрума», я еще не настолько стар!). В общем, о практическом применении этой книжки можно и поспорить.
В общем, будем считать, что эта книга со временем все больше и больше приближается к «чистой», то есть совершенно бесполезной, математике. Глобально в ней рассматриваются две темы — реализация некоторых «математических» функций, обычно входящих в стандартную библиотеку, и некоторые численные методы — дифференцирование, интегрирование и решение задачи Коши для дифференциальных уравнений. Первая из них возникала в мехматовском «Программировании и работе на ЭВМ», вторая — в том или ином виде присутствовала в течение всех четырех лет, что на мехмате читается курс околокомпьютерных наук (речь о 2005-2010 годах, сейчас что-то немного поменялось) — но в целом я бы отнес это к второму семестру.
Что можно сказать про первую тему? Да, писать собственные синусы с косинусами приходится немногим. Но очень и очень немногие при необходимости смогут сделать это правильно. Из «остаточных знаний» второго семестра я смог бы навскидку назвать лишь пару-тройку из тех «подводных камней», что упоминаются в книге. О некоторых вещах речь вообще не заходила ни разу и они оказались для меня сюрпризом. Более того, даже для сравнительно простой задачи — вычисления квадратного корня — приводится несколько алгоритмов, отличающихся требованиями по точности, скорости, наличию или отсутствию математического сопроцессора. Если вам вдруг захочется реализовать вычисление квадратного корня на каком-нибудь AVR — есть и «целочисленный» алгоритм.
Один из шедевров, не побоюсь этого слова, приведенных в книге — функция bitlog(), приближенно вычисляющая логарифм. Вместе с ее кодом — который можно смело использовать для любых Obfuscated C Contest — приводится подробнейшее описание, как и почему она работает.
/* Bitlog function * * Invented by Tom Lehman at Invivo Research, Inc., * ca. 1990 * * Gives an integer analog of the log function * For large x, * * B(x) = 8*(log(base 2)(x) – 1) */ short bitlog(unsigned long n) { short b; // shorten computation for small numbers if(n <= 8) return (short)(2 * n); // find the highest non-zero bit b=31; while((b > 2) && ((long)n > 0)) { --b; n <<= 1; } n &= 0x70000000; n >>= 28; cout << b << ' ' << n << endl; return (short)n + 8 * (b - 1); }
Впечатляет? А в книге описано, как подобные алгоритмы разрабатывать, с оценками точности и так далее.
Вторая группа вопросов, разобранных в этой книге - численные методы. Уровень математической строгости, конечно, уступает "кирпичу" Бахвалова, да и первой части этой же книги - но дело в том, что для понимания численного дифференцирования и интегрирования надо хотя бы немного знать о дифференцировании и интегрировании обычном - на что американский автор книги для программистов рассчитывать никак не может. Тем не менее, приводятся несколько формул численного дифференцирования и интегрирования с оценками их точности и читатель даже подводится к одному из способов построения таких формул - представить, что функция приближена многочленом, и добиться того, чтобы для многочленов рассматриваемая функция была бы точной.
Для дифференциальных уравнений довольно подробно рассматриваются методы Адамса (многошаговый) и Рунге-Кутты. Опять же, так как с точки зрения программирования они тривиальны, много внимания уделяется получению формул для расчетов. Это все вполне доступно второкурснику мехмата (или любому, кто осилил формулу Тейлора и азы программирования), так что вполне можно обозвать книжку "Кратким введением в численные методы".
Что очень важно - такого рода "элементарного" учебника на русском языке я припомнить не могу. Учебники по численным методам рассчитаны на студентов где-то 4 курса и обычно требуют неплохой математической подготовки вместе с серьезным "погружением" в предмет. Книги "для программистов" обходят численные методы стороной - тема эта все-таки довольно специфическая. Ценность же этой книги - в том, что в ней рассматриваются некоторые неочевидные приемы, о которых, как я помню, действительно упоминалось на семинарах - но они сохранились у меня в лучшем случае в виде "остаточных знаний", а в худшем - "вроде это было вот в той книжке" (а по численным методам пришлось почитать довольно много чего интересного, спасибо И. С. Григорьеву и его отношению к прогульщикам-халявщикам).
В общем, мне понравилось.