Алгоритмы компьютерной арифметики

АЛГОРИТМЫ
КОМПЬЮТЕРНОЙ
АРИФМЕТИКИ

3-е издание, электронное

Москва
Лаборатория знаний
2020

УДК 519.85(023)
ББК 22.18

О-52

С е р и я о с н о в а н а в 2008 г.
Окулов С. М.

О-52
Алгоритмы компьютерной арифметики / С. М. Окулов, А. В. Лялин, О. А. Пестов, Е. В. Разова. — 3-е изд.,
электрон. — М. : Лаборатория знаний, 2020. — 288 с. —
(Развитие интеллекта школьников). — Систем. требования: Adobe Reader XI ; экран 10".— Загл. с титул.
экрана. — Текст : электронный.
ISBN 978-5-00101-657-1
В книге речь идет о традиционных алгоритмах, которые
кажутся очевидными, — об алгоритмах выполнения арифметических операций: о том, сколько тайного смысла и усилий
интеллекта многих специалистов по информатике заложено
в эти алгоритмы. Материал книги формирует содержательную
основу деятельностного изучения алгоритмов компьютерной
арифметики, чему способствует стиль изложения, синтезирующий в себе и математический материал, и формализованную
запись логики работы компьютера.
Для школьников, преподавателей информатики и студентов информационно-технологических специальностей.
УДК 519.85(023)
ББК 22.18

Деривативное издание на основе печатного аналога: Алгоритмы компьютерной арифметики / С. М. Окулов, А. В. Лялин, О. А. Пестов, Е. В. Разова. — М. : БИНОМ. Лаборатория
знаний, 2014. — 285 с. : ил. — (Развитие интеллекта школьников). — ISBN 978-5-9963-1549-9.

В
соответствии
со
ст. 1299
и
1301
ГК
РФ
при
устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации

ISBN 978-5-00101-657-1
c○ Лаборатория знаний, 2015

2

Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
5

Часть 1. Компьютерная арифметика  . . . . . . . . . . . . . . . . . .
9

1.1. Алгоритмы целочисленной арифметики  . . . . . . . . . . . . . . . .
9

Вспомогательные инструменты  . . . . . . . . . . . . . . . . . 10
Сложение неотрицательных целых чисел. . . . . . . . . 12
Вычитание неотрицательных целых чисел. . . . . . . . 15
Умножение неотрицательных целых чисел  . . . . . . . 18
Деление неотрицательных целых чисел  . . . . . . . . . . 21

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.2. Отрицательные целые числа . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Алгоритм умножения для знаковых чисел 
в дополнительном коде . . . . . . . . . . . . . . . . . . . . . . . . 27
Алгоритм А. Бута  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

1.3. Алгоритмы арифметики вещественных чисел. . . . . . . . . . . 34

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

1.4. Алгоритм Евклида  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Переборный алгоритм. . . . . . . . . . . . . . . . . . . . . . . . . 50
Алгоритм, использующий разложение числа 
на простые множители  . . . . . . . . . . . . . . . . . . . . . . . . 50
Алгоритм Евклида «c вычитанием»  . . . . . . . . . . . . . 54
Алгоритм Евклида «с делением» . . . . . . . . . . . . . . . . 56
Бинарный алгоритм Евклида. . . . . . . . . . . . . . . . . . . 57
Алгоритм Евклида для n чисел  . . . . . . . . . . . . . . . . . 59
Времення сложность алгоритма . . . . . . . . . . . . . . . . 60
Обратная задача. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

1.5. Расширенный алгоритм Евклида. . . . . . . . . . . . . . . . . . . . . . . 71

Первый вопрос. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Второй вопрос  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Расширенный итеративный алгоритм Евклида  . . . . 74
Расширенный рекурсивный алгоритм Евклида  . . . . 77
Третий вопрос  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
Четвертый вопрос  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

1.6. Алгоритмы возведения в степень. . . . . . . . . . . . . . . . . . . . . . .102

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . .110

1.7. Модулярная арифметика  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .113

1.7.1. Элементы теории сравнений. . . . . . . . . . . . . . . . . . . .113

Определение и свойства сравнений  . . . . . . . . . . . . . .113
Функция Эйлера  . . . . . . . . . . . . . . . . . . . . . . . . . . . . .115
Система вычетов  . . . . . . . . . . . . . . . . . . . . . . . . . . . . .118
Теорема Л. Эйлера. . . . . . . . . . . . . . . . . . . . . . . . . . . .125

Содержание

Содержание

Сравнение первой степени  . . . . . . . . . . . . . . . . . . . . 126

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

1.7.2. Китайская теорема об остатках  . . . . . . . . . . . . . . . . 130

Система из двух сравнений. . . . . . . . . . . . . . . . . . . . 131

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

1.7.3. Алгоритмы модулярной арифметики  . . . . . . . . . . . 150

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

1.8. Сравнения второй степени  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

Часть 2. Алгоритмы умножения целых чисел. . . . . . . . . . 167
2.1. Алгоритм А. А. Карацубы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

2.2. Алгоритм А. Тоома и С. Кука  . . . . . . . . . . . . . . . . . . . . . . . . . 176

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

2.3. Дискретное преобразование Ж. Фурье . . . . . . . . . . . . . . . . . 186

Алгоритм умножения . . . . . . . . . . . . . . . . . . . . . . . . 187
Тривиальное решение . . . . . . . . . . . . . . . . . . . . . . . . 189
Быстрое дискретное преобразование Ж. Фурье  . . . 189 
Рекурсивная реализация вычисления FFTn(A)  . . . 194 
Обратное дискретное преобразование Ж. Фурье . . . 196 
Умножение чисел на основе 
быстрого преобразования Ж. Фурье  . . . . . . . . . . . . 201
Оптимизация алгоритма. . . . . . . . . . . . . . . . . . . . . . 203

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

2.4. Алгоритм А. Шенхаге и Ф. Штрассена. . . . . . . . . . . . . . . . . 215

Оценка временнй сложности 
алгоритма Шенхаге–Штрассена. . . . . . . . . . . . . . . . 220
Алгоритм Шенхаге–Штрассена . . . . . . . . . . . . . . . . 221

Упражнения.  . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

Приложения  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
Приложение 1. Система быстрого счета Я. Трахтенберга. . . . 225

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

Приложение 2. Дерево Штерна–Броко   . . . . . . . . . . . . . . . . . . . . 240

О нумерации рациональных чисел  . . . . . . . . . . . . . 240

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

Дерево Штерна–Броко как способ нумерации 
положительных рациональных чисел . . . . . . . . . . . 252

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

Дерево Штерна–Броко как способ приближения 
одних рациональных чисел другими. . . . . . . . . . . . 271

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 276

Дерево Штерна–Броко как система счисления 
для положительных рациональных чисел  . . . . . . . 277

Упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

Обучение программированию, конечно, включает 
обучение фактам — о системах, машинах, языках 
программирования и т. д. Все это очень легко сделать явным. Но неприятность состоит в том, что 
эти факты составляют всего лишь десять процентов. То, что должно преподаваться в оставшиеся 
девяносто процентов, — это как решать задачи, 
как избежать непреодолимых трудностей. Короче, это обучение умению мыслить, не больше и не 
меньше.

Эдсгер Дейкстра, 
«Ремесленник или ученый?»

Дано число:

m = 114381625757888867669325779976146612010218296
721242362562561842935706935245733897830597123563
958705058989075147599290026879543541.

Оно состоит из 129 десятичных цифр. С помощью этого 
числа Р. Ривест, А. Шамир и Л. Адлеман в 1978 г. зашифровали определенный текст с помощью широко известного алгоритма RSA. Алгоритм расшифровки тоже известен: чтобы 
получить исходный текст, число m надо разложить на произведение множителей. Но лишь через 17 лет (в 1994 г.) эта задача была решена — за 220 дней на 1600 компьютерах1).
Ваш ноутбук (например, с тактовой частотой 1,67 ГГц) выполняет одно умножение примерно за t = 3,5 · 10–9 с. Количество чисел, которые можно представить 129 десятичными 
цифрами, равно 10129. Чтобы решить вышеупомянутую задачу 
самым простым способом, надо для половины этих 10129 чи
1) 
 Ященко В. В. Введение в криптографию. — М.: МЦНМО: «ЧеРо», 2000. — 
С. 90.

Введение

Введение

сел проверить, являются ли они делителями числа m. Пусть 
время  выполнения операции деления совпадает с временем 
выполнения операции умножения. Тогда требуется выполнить 
порядка 10128/2 умножений (будем считать, что первая цифра 
известна). Это потребует 3,5 · 10–9 · 10128/2 = 1,75 · 10119 с. Один 
год — это приблизительно 3,155 · 107 с. Тогда для решения 
этой задачки на вашем ноутбуке потребуется ни много ни мало 
0,55·10112 лет (небольшая погрешность в вычислении количества лет уже не принципиальна). 
Описанный выше пример — один из самых ярких, но далеко не единственный. Количество проблем, нерешаемых с помощью классического варианта компьютера (настольного или 
ноутбука), по-прежнему не уменьшается несмотря на рост быстродействия современных процессоров. Требуется всё большая производительность компьютеров. 
В информатике можно выделить по крайней мере два направления в достижении этой цели. Первый, в самой общей 
формулировке, заключается в повышении производительности компьютера на аппаратном уровне. Второй — это поиск 
на алгоритмическом уровне способов ускорения выполнения 
как традиционных арифметических операций, так и методов 
решения задач.
В этой книге (а она в первую очередь предназначена для 
школьников и учителей информатики) арифметические операции рассматриваются на алгоритмическом уровне. Эти знания 
представляют собой необходимый компонент образованности 
человека, выбравшего информатику в качестве области своей 
профессиональной деятельности. 
Второе направление в достижении вышеупомянутой цели, 
вероятно, самое эффективное, заключается в создании новых 
алгоритмов. Но универсальных алгоритмов не существует! 
Каждая конкретная область обработки данных с помощью 
компьютера, например обработка строк, требует своих открытий и изобретений. И эти открытия способен сделать только 
человек, имеющий алгоритмическую культуру, на формирование которой направлен в том числе и материал этой книги, 
включающий кроме методов реализации арифметических операций рассмотрение таких фундаментальных алгоритмов, как 
бинарный алгоритм возведения в степень, алгоритм Евкли да, 
китайский алгоритм об остатках и алгоритм быстрого преобразования Фурье. Без знания последних невозможно понять 

Введение 
7

многие достижения современной информатики, например 
в криптографии, обработке видеоинформации и т. д.
Заметим, что задачи, связанные с эффективным выполнением арифметических операций и обработкой больших чисел, 
нередко появляются в олимпиадной информатике и являются одним из обязательных разделов подготовки школьника 
к олимпиадам по программированию. Однако систематическое изучение этого раздела в рамках элективных курсов для 
физико-математического, информационно-технологического 
и естественнонаучного профилей обычно отсутствует. 
Основные алгоритмы входят в примерную программу 
по олимпиадной информатике под названием «числовых 
алгоритмов»2). К обязательным для изучения при этом относятся: алгоритм Евклида, методы решения линейных сравнений и т. д. Эти алгоритмы считают дидактическими единицами, «изучение которых формирует у школьников ключевые 
умения в области олимпиадной подготовки, открывает перед 
участником олимпиадного состязания возможность проявить 
свой творческий потенциал на достойном уровне ... — дипломов победителей и призеров заключительных этапов Всероссийской олимпиады школьников»3).
В этой книге синтезируются два подхода в изложении материала, а именно математический и компьютерный. Подобный стиль изложения подставляет авторов под огонь критики 
как с той, так и с другой стороны. Но авторы не претендуют 
на некую абсолютизацию своего подхода в изучении данного 
раздела алгоритмистики, а предлагают рассматривать его как 
один из возможных вариантов. 
При написании книг по компьютерным алгоритмам и при 
преподавании этого раздела информатики нередко приходится 
сталкиваться с удивительным фактом. Что бы автор ни писал, 
что бы ни делал, достаточно заглянуть в монументальный труд 
Дональда Кнута4), и практически всегда оказывается, что он 
так или иначе уже описал и рассмотрел этот вопрос. Конечно, книги Д. Кнута написаны непростым языком и работать с 
ними не просто. Однако, так или иначе, вдохновителем мно
2) 
Кирюхин В. М. Информатика: всероссийские олимпиады. — М.: Просвещение, 2008. — С. 71.
3) 
 Там же — С. 67. 
4) 
Кнут Д.  Искусство программирования для ЭВМ. В 3 тт. — М.: Мир, 1976, 
1977, 1978. (Всего автором задумано семь томов, но остальные четыре тома 
еще не изданы. — Прим. авт.)

Введение

гих страниц данной книги (а она отражает реальное преподавание!) является именно этот труд Д. Кнута (даже при отсутствии ссылок на него).
Настольными и даже, если можно так выразиться, «священными» книгами для программиста являются также труды 
Никлауса Вирта5) и Витольда Липского6). Их влияние на материал данной книги не так заметно, но оно есть — если не 
прямое, то косвенное. Оно заметно и в стиле изложения, и в 
синтезе математических фактов с реально работающими алгоритмами (при их проверке на компьютере). Последнее позволяет строить изучение материала не на уровне фактографического «вливания в сосуд7)», а путем экспериментального 
исследования этих фактов. Этим достигается самостоятельное 
осознание материала учащимся (школьником или студентом 
младших курсов), что требует от учащегося «пребывания в состоянии мысли». А это очень не просто — пребывать в состоянии мысли, думать, — это требует значительных усилий от 
человека (попробуйте, например, в течение часа осмысливать 
некую проблему, не связанную с бытовой прагматикой!), и в 
этом случае компьютер снова становится нашим помощником.
Эта книга — коллективный труд. Каждый автор внес посильную лепту в ее создание. Но мы обязаны сказать слова 
благодарности и всем школьникам и студентам за их критическое отношение к изложению материала, за многочисленные 
замечания и вопросы. Также и наши коллеги по факультету 
информатики, математики и физики Вятского государственного гуманитарного университета оказали нам незаменимую 
поддержку даже в том, что слегка разгружали нас от рутинной 
работы во время написания книги, не говоря уже о сделанных 
ими ценных замечаниях и предложениях.

5) 
 Вирт Н. Алгоритмы + Структуры данных = Программы. — М.: Мир, 1985.
6) 
 Липский В. Комбинаторика для программистов. — М.: Мир, 1988.
7) 
 Аналогия с мыслью К. Поппера, когда он рассуждает о традиционной педагогике и сравнивает ее с механизмом «вливания в голову» учеников некой 
суммы фактов.

Программист должен обладать способностью 
первоклассного математика к абстракции и 
логическому мышлению в сочетании с эдисоновским талантом сооружать все, что угодно, 
из нуля и единиц.

А. П. Ершов, «О человеческом и эстетическом факторах в программировании»

1.1. Алгоритмы целочисленной арифметики

Любая гениальная идея, в сущности, очень 
проста. 
К. Чапек 

Примечание. В этом параграфе рассмотрена программная 
реализация особенностей выполнения арифметических операций с целыми числами в компьютере. Вопросы аппаратной 
(схемной) реализации данных операций (а они достаточно интересны) выходят за рамки данной книги. 

Известно, что компьютер обрабатывает данные, представленные в двоичной системе счисления8). В данном параграфе 
рассматриваются алгоритмы выполнения операций сложения, 
вычитания, умножения и деления целых неотрицательных 
чисел. 
Однако прежде чем начать работу, обратим внимание на 
два удивительных факта.
При реализации операций сложения, вычитания, умножения и деления неотрицательных целых чисел мы будем ис
8) 
Считаем, что с темой «системы счисления» читатель знаком. Если нет, 
то она прекрасно изложена в книге: Андреева Е. В., Босова Л. Л., Фалина И. Н. Математические основы информатики. 2-е изд. — М.: БИНОМ. 
Лаборатория знаний, 2007.

Часть 1

Компьютерная арифметика

Часть 1. Компьютерная арифметика

пользовать только элементарные действия. Предположим, что 
компьютер может выполнять только сложение двух одноразрядных (однобитовых) чисел, операции сдвигов влево и вправо и логические операции, — другими словами, некое заданное множество примитивных действий9). Естественно, что без 
стандартных алгоритмических конструкций (следования, ветвления и повторения) сделать ничего нельзя. Но оказывается, 
что этих действий достаточно для решения задачи! 
Итак, арифметику неотрицательных целых чисел мы конструируем из элементарных действий. Но если есть эта арифметика, то можно продолжить процесс и создавать более сложные конструкции, которые опять же будут построены из этих 
простых «кирпичиков». Удивительно, но вся сложная система 
под названием «компьютер» со всеми ее возможностями может быть создана только из этих элементарных действий.
Компьютерная арифметика — это арифметика конечных 
(ограниченных) чисел. В одном разряде можно хранить только 
два различных значения, в двух — четыре, в n разрядах — 2n. 
Например, при хранении целых неотрицательных чисел в n 
разрядах возможно представить только числа от 0 до 2n–1. 
То есть число 2n — это нуль с точки зрения компьютера. Число 
2n в двоичном представлении — это единственный единичный 
(n+1)-й бит, а все остальные биты нулевые. В результате мы 
получаем n нулевых разрядов. Другими словами, число 2n — 
это нуль в компьютерном представлении, или 2n сравнимо 
с нулем (2n 0). 
А теперь мысленно представим себе то множество проблем, 
которое решается с помощью компьютера. И все эти проблемы 
спроецированы, если можно так выразиться, в конечную область значений. Другими словами, «мир компьютера» — это 
конечный мир. 

Вспомогательные инструменты
Для наглядности изложения необходимо определить количество разрядов в представлении неотрицательных целых 
чисел. Будем считать, что оно равно 16 (двум байтам). В среде 
программирования Паскаль это тип данных Word. Определим 
в разделе констант выбранное значение:
Const Nmax=16;

9) 
Это не совсем точное предположение. В реальном компьютере множество 
примитивов еще меньше, но в качестве допущения оно может быть принято.

1.1. Алгоритмы целочисленной арифметики 
11

В процессе работы необходимо реализовать вывод числа в 
двоичном виде. Эту задачу решает процедура Print:
Procedure Print(s:Word);
  Var t:String;
      j:Word;
  Begin
   t:=''; {}
   j:=Nmax;
   While j>0 Do Begin 
   {}
    If (s And 1)=1 Then t:='1'+t
     Else t:='0'+t;
    s:=s ShR 1; {}
    j:=j-1;
   End;
   WriteLn(t);
  End;

Примечание. Можно было бы использовать конструкцию:
While s<>0 Do …,
но в этом случае длины строк будут различны и нет требуемой 
наглядности в представлении результата.

При наличии процедуры Print основная программа для 
анализа операции сложения двух целых неотрицательных 
чисел  (u, v) записывается так:
Begin
 ReadLn(u,v);
 Print(u);
 Print(v);
 Add(u,v,w); {}
 Print(w);
End.

Неотрицательные целые числа u и v в двоичном представлении имеют вид u15u14...u1u0 и v15v14...v1v0. Разряды пронумерованы справа налево, как это принято для двоичных чисел. 
В ряде случаев требуется знать точное количество задействованных разрядов в представлении числа (например, чтобы 
отбросить старшие нулевые разряды). Эти значения фиксиру

Часть 1. Компьютерная арифметика

ются с помощью функции Nbit в глобальных переменных n 
и m: 
Function Nbit(a:Word):Word;
  Var cnt:Word;
  Begin
   cnt:=0;
   While a>0 Do Begin
     cnt:=cnt+1;
     a:=a ShR 1;
    End;
   Nbit:=cnt;
  End;

Тогда основная программа, например для анализа операции деления, имеет вид:

Begin
 ReadLn(u,v);
 n:=Nbit(u);
 m:=Nbit(v);
 Divs(u,v,w,r); 
 {, w — , r — }
 Print(w);
 Print(r);
End.

Сложение неотрицательных целых чисел

Даны два неотрицательных целых числа u = u15u14...u1u0 и 
v = v15v14...v1v0. Требуется найти их сумму — число r = r15r14...r1r0.
На рис. 1.1 приведен пример сложения 8-разрядных двоичных чисел u = 182 и v = 43.

Рис. 1.1. Сложение чисел

Фактически требуется реализовать логику сложения одноразрядных чисел с учетом переноса единицы из младшего 
в старший разряд (переменная k). Эта логика представлена 
в табл. 1.1, где k— новое (пересчитанное) значение k.