АЛГОРИТМЫ КОМПЬЮТЕРНОЙ АРИФМЕТИКИ 2-е издание (электронное) Москва БИНОМ. <...> Материал книги формирует содержательную основу деятельностного изучения алгоритмов компьютерной арифметики, чему способствует стиль изложения, синтезирующий в себе и математический материал, и формализованную запись логики работы компьютера. <...> УДК 519.85(023) ББК 22.18 Деривативное электронное издание на основе печатного аналога: Алгоритмы компьютерной арифметики / С. М. Окулов, А. В. Лялин, О. А. Пестов, Е. В. Разова. <...> И эти открытия способен сделать только человек, имеющий алгоритмическую культуру, на формирование которой направлен в том числе и материал этой книги, включающий кроме методов реализации арифметических операций рассмотрение таких фундаментальных алгоритмов, как бинарный алгоритм возведения в степень, алгоритм Евкли да, китайский алгоритм об остатках и алгоритм быстрого преобразования Фурье. <...> При реализации операций сложения, вычитания, умножения и деления неотрицательных целых чисел мы будем ис8) Считаем, что с темой «системы счисления» читатель знаком. <...> При наличии процедуры Print основная программа для анализа операции сложения двух целых неотрицательных чисел (u, v) записывается так: Begin ReadLn(u,v); Print(u); Print(v); Add(u,v,w); { } Print(w); End. рованы справа налево, как это принято для двоичных чисел. <...> Сложение чисел Фактически требуется реализовать логику сложения одноразрядных чисел с учетом переноса единицы из младшего в старший разряд (переменная k). <...> Представление 16-разрядных целых неотрицательных чисел В криптографии и ряде других областей возникает необходимость работы с числами, занимающими в памяти 1024 разряда и более (назовем такие числа «большими»). <...> Tmax] Of Word; Var u,v,r:Nb; При сложении 1024-битовых чисел изменяется только значение константы Tmax и, соответственно, размер массива для хранения величин. <...> Процедура Add при этом претерпит несущественные изменения: переменную k следует исключить из локальных переменных <...>
Алгоритмы_компьютерной_арифметики_(2).pdf
УДК 519.85(023)
ББК 22.18
О-52
С е р и я о с н о в а н а в 2008 г.
Окулов С. М.
О-52 Алгоритмы компьютерной арифметики / С. М. Окулов,
А. В. Лялин, О. А. Пестов, Е. В. Разова.—4-е изд.,
электрон.—М. : Лаборатория знаний, 2024.—288 с.—
(Развитие интеллекта школьников).—Систем. требования:
Adobe Reader XI ; экран 10".—Загл. с титул.
экрана.—Текст : электронный.
ISBN 978-5-93208-677-3
В книге речь идет о традиционных алгоритмах, которые
кажутся очевидными,—об алгоритмах выполнения арифметических
операций: о том, сколько тайного смысла и усилий
интеллекта многих специалистов по информатике заложено
в эти алгоритмы. Материал книги формирует содержательную
основу деятельностного изучения алгоритмов компьютерной
арифметики, чему способствует стиль изложения, синтезирующий
в себе и математический материал, и формализованную
запись логики работы компьютера.
Для школьников, преподавателей информатики и студентов
информационно-технологических специальностей.
УДК 519.85(023)
ББК 22.18
Деривативное издание на основе печатного аналога: Алгоритмы
компьютерной арифметики / С. М. Окулов, А. В. Лялин,
О. А. Пестов, Е. В. Разова.—М. : БИНОМ. Лаборатория
знаний, 2014.—285 с. : ил.—(Развитие интеллекта школьников).—ISBN
978-5-9963-1549-9.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации
ISBN 978-5-93208-677-3
© Лаборатория знаний, 2015
Стр.3
Содержание
Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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
Стр.4
4
Содержание
Сравнение первой степени . . . . . . . . . . . . . . . . . . . . 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
Стр.5