Math Toolkit for Real-Time Development

Прочитал совершенно замечательную книжку 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 курса и обычно требуют неплохой математической подготовки вместе с серьезным "погружением" в предмет. Книги "для программистов" обходят численные методы стороной - тема эта все-таки довольно специфическая. Ценность же этой книги - в том, что в ней рассматриваются некоторые неочевидные приемы, о которых, как я помню, действительно упоминалось на семинарах - но они сохранились у меня в лучшем случае в виде "остаточных знаний", а в худшем - "вроде это было вот в той книжке" (а по численным методам пришлось почитать довольно много чего интересного, спасибо И. С. Григорьеву и его отношению к прогульщикам-халявщикам).

В общем, мне понравилось.

Комментарии отключены.