В настоящей книге рассматриваются методы быстрого выполнения различных видов вычислений, рассказывается о реализации быстрых алгоритмов как в виде логических схем --- математической модели реальных электронных микросхем, так и в виде компьютерных программ. Исследуются также вопросы о том, как измерить сложность того или иного вычислительного алгоритма и оценить время его работы на компьютере. Большая часть материала книги доступна всем, кто знаком лишь со школьным курсом математики, но и опытный читатель может найти в этой книге кое-что новое для себя.
Книга написана на основе лекций, которые автор в разное время читал учащимся физико-математической Школы им. А.Н.Колмогорова при МГУ, на Малом и Большом мехмате, а также на факультетах информационной безопасности и информатики РГГУ.
Введение
Развитие быстрых алгоритмов происходит медленно.
Арнольд Шёнхаге
Здесь уместно разъяснить, что означает термин "компьютерная арифметика" или, по крайней мере, как он понимается в книге.
Как и любая область науки, компьютерная арифметика состоит из нескольких связанных между собой направлений и по-разному выглядит с разных точек зрения. В ней есть и многочисленные технические детали, и фундаментальные понятия. Естественно, вторым будет уделяться больше внимания, чем первым, поэтому в технической области изложение не всегда будет исчерпывающим.
С одной стороны, компьютерная арифметика, как и следует ожидать, должна объяснять, как выполняются на компьютере различные операции с числами и/или машинными словами. Компьютеры имеют многочисленные команды для выполнения таких операций, среди которых есть и арифметические, и логические. Разные компьютеры (а к их числу без большой ошибки можно причислить и калькуляторы, да и почти любую цифровую технику) делают это по-разному и имеют различные наборы команд. Знание особенностей системы команд компьютера, конечно, нужно каждому программисту, хотя оно выходит за пределы собственно программирования -- чтобы писать программы, в общем-то не обязательно знать, каким образом компьютер выполняет команду сравнения чисел или их деления с остатком. Кроме того, полное понимание процессов, реально происходящих в компьютере во время выполнения программы, требует знания массы технических деталей, связанных с устройством процессора и других микросхем, составляющих компьютер, и выходит за рамки собственно компьютерной арифметики, относясь к области, которую можно назвать архитектурой вычислительных систем.
Тем не менее компьютерные процессоры и другие большие цифровые микросхемы ("чипы") содержат в себе сравнительно небольшие микросхемы для выполнения отдельных арифметических или логических операций. Разобраться в их устройстве, по крайней мере в общих принципах функционирования, не так уж и сложно, потому что электронные микросхемы, как старые, так и самые современные, имеют очень простую математическую модель -- схему из функциональных логических элементов, часто называемую в инженерной практике комбинационной схемой, а в теории -- булевой логической схемой, или просто схемой (реализующей булевы функции, называемые также функциями алгебры логики). Построение булевых схем, реализующих арифметические и логические операции, относится к сфере первоочередных интересов компьютерной арифметики, и в тоже время составляет существенный раздел теории сложности булевых функций. Впрочем, вопросы связанные с поиском эффективных алгоритмов построения булевых схем и с автоматизацией проектирования реальных электронных микросхем содержат множество технических деталей и выходят за рамки как компьютерной арифметики, так и теории сложности булевых функций, относясь к специальной области компьютерных наук -- автоматизации проектирования микросхем. Разумеется, касаться этой области в популярной книге неуместно.
В программировании иногда возникает необходимость выполнять арифметические действия с "длинными" числами, не умещающимися в разрядную сетку компьютера, например в научных расчетах для достижения требуемой точности, в криптографии для выполнения действий с числами, состоящими из сотен цифр, в рекордных вычислениях, например, с целью найти миллиард знаков числа pi и т.д. Для выполнения этих действий нельзя непосредственно использовать команды машинной арифметики, а необходимо писать программы для так называемой длинной арифметики. Такие программы давно написаны и входят в пакеты многих систем компьютерной алгебры. Чтобы самому написать подобные программы и разобраться в работе известных программ нужна компьютерная арифметика. На самом деле используемые в этих программах арифметические алгоритмы весьма близки к алгоритмам, "зашитым в железе" электронных микросхем для выполнения арифметических операций. Но вместо двоичной системы счисления, которая используется в микросхемах (хотя используются и микросхемы, реализующие с помощью двоичных элементов десятичную арифметику), в компьютерных программах "длинной арифметики" обычно применяется система счисления с основанием 2w где w -- длина машинного слова применяемого компьютера, а для записи самих программ вместо двоичной удобно использовать шестнадцатеричную систему (так как это в четыре раза сокращает длину записи чисел).
Использование подходящей (как правило, того или иного варианта позиционной) системы счисления является простейшей, старейшей, и в то же время важнейшей и фундаментальной идеей, используемой в компьютерной арифметике. Поэтому знакомство с ней естественно начинать с рассмотрения различных систем счисления. Книга "Занимательная компьютерная арифметика: Математика и искусство счета на компьютерах и без них" с этого и начинается, причем содержит почти целиком (и в несколько дополненном виде) материал из брошюры автора "Системы счисления и их применения". На самом деле упомянутая брошюра и задумывалась как первая часть популярной книги по компьютерной арифметике, но ее написание несколько затянулось, и первую часть пришлось опубликовать отдельно. Арифметические алгоритмы в нашей книге обычно излагаются для произвольной позиционной системы, но иногда они даются только для десятичной системы (чтобы подчеркнуть удобство их применения в ручных вычислениях, и даже в устном счете), а иногда -- только для двоичной (потому что в двоичной системе они имеют наиболее простой вид и наиболее широкую область применения).
Кроме чисто арифметических алгоритмов уместно показалось рассмотреть в книге некоторые вопросы, связанные с вычислениями с обыкновенными дробями, многочленами и дробно-рациональными функциями. Эти вопросы являются пограничными между компьютерной алгеброй и компьютерной арифметикой и весьма близки к последней. Их включение в книгу оправдано также тем, что, например, алгоритмы арифметических действий с многочленами на самом деле проще аналогичных алгоритмов для чисел.
Особенностью книги является также то, что, помимо описания различных алгоритмов, часто дается обоснованная оценка их сложности (т.е. числа выполняемых ими операций). В случае логических схем оценка их сложности позволяет объективно судить о размерах, которые может иметь реальная электронная микросхема, моделируемая рассматриваемой логической схемой. В случае же программных алгоритмов оценка их сложности позволяет судить о времени их работы. Умение оценивать сложность алгоритма, таким образом, полезно и в программировании и в проектировании (и производстве) электронной техники. Разделы, связанные с оценками сложности, находятся в конце книги и составляют, по-видимому, наиболее сложную ее часть (извините за каламбур). Это не удивительно, поскольку они находятся на границе между собственно компьютерной арифметикой и теорией сложности вычислений.
Чтобы компенсировать неизбежную сложность некоторых разделов книги, в нее показалось разумным вставить различный развлекательный материал, вроде приемов устных вычислений, интересных даже младшеклассникам, алгоритмам вычислений на калькуляторах, применений систем счисления за пределами компьютерной арифметики, исторических сведений о первооткрывателях тех или иных идей, затрагиваемых в книге и т.д. (однако точные ссылки на используемые результаты, как правило, не даются). Рассмотрены также вопросы эффективного выполнения некоторых манипуляций с числами и машинными словами на компьютере в условиях, когда отсутствуют команды, непосредственно их выполняющие. Подобные вопросы несомненно также относятся к компьютерной арифметике.
Книга, претендующая на популярность, не может освещать рассматриваемые вопросы в достаточной полноте. Поэтому некоторые вопросы, связанные с компьютерной арифметикой, затронуты лишь мимоходом или не затронуты вовсе. Это и вопросы оценки точности машинных вычислений, арифметика с плавающей запятой, логические схемы с памятью (автоматные схемы), алгоритмы вычисления элементарных функций, принципы работы компьютерного процессора, физические принципы работы электронных микросхем и их математического моделирования, вопросы проектирования, тестирования и производства чипов и т.д. Многим из подобных вопросов уже посвящаются целые книги (разумеется, не научно-популярные). Из великого множества алгоритмов компьютерной арифметики в книге упоминается лишь небольшая часть.
Предполагается, что читатель немного знает школьную математику (сейчас изучает ее или еще не успел забыть), поэтому иногда в книге используются без пояснений некоторые понятия и обозначения. Но во многих случаях необходимые пояснения даются. В отличие от учебников изложение не всегда систематичное, одним вопросам уделяется больше внимания, другим -- меньше, некоторые темы даже не упоминаются, в книге встречаются ссылки как назад, так и вперед и т.д. Все это неизбежные особенности вольного стиля изложения (вообще свойственного, как нам кажется, научно-популярной литературе). Но изНза почти полного отсутствия на русском языке литературы по компьютерной арифметике автор надеется, что ее можно будет использовать и с учебной целью как в школах, так и в вузах.
В заключение автор благодарит своих бывших учеников (и нынешних коллег) А.А.Бурцева и И.С.Сергеева за помощь в работе.
Издание: обложка.
Параметры: формат: 60x90/16, 224 стр.
