Алгоритмы компьютерной арифметики, 4-е издание
Год издания: 2024
Автор: Окулов С. М.
Издательство: Лаборатория знаний
ISBN: 978-5-93208-677-3
Серия: Развитие интеллекта школьников
Язык: Русский
Формат: PDF
Качество: Издательский макет или текст (eBook)
Количество страниц: 288
Описание: В книге речь идет о традиционных алгоритмах, которые кажутся очевидными,—об алгоритмах выполнения арифметических операций: о том, сколько тайного смысла и усилий интеллекта многих специалистов по информатике заложено в эти алгоритмы. Материал книги формирует содержательную основу деятельностного изучения алгоритмов компьютерной арифметики, чему способствует стиль изложения, синтезирующий в себе и математический материал, и формализованную запись логики работы компьютера.
Для школьников, преподавателей информатики и студентов информационно-технологических специальностей.
Примеры страниц (скриншоты)
Оглавление
Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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
