Введение......5Часть 1. Компьютерная арифметика......91.1. Алгоритмы целочисленной арифметики......9Вспомогательные инструменты......10Сложение неотрицательных целых чисел......12Вычитание неотрицательных целых чисел......15Умножение неотрицательных целых чисел......18Деление неотрицательных целых чисел......21Упражнения......221.2. Отрицательные целые числа......24Алгоритм умножения для знаковых чисел в дополнительном коде......27Алгоритм А. Бута......30Упражнения......331.3. Алгоритмы арифметики вещественных чисел......34Упражнения......481.4. Алгоритм Евклида......49Переборный алгоритм......50Алгоритм
использующий разложение числа на простые множители......50Алгоритм Евклида «c вычитанием»......54Алгоритм Евклида «с делением»......56Бинарный алгоритм Евклида......57Алгоритм Евклида для n чисел......59Временнáя сложность алгоритма......60Обратная задача......62Упражнения......621.5. Расширенный алгоритм Евклида......71Первый вопрос......72Второй вопрос......74Расширенный итеративный алгоритм Евклида......74Расширенный рекурсивный алгоритм Евклида......77Третий вопрос......80Четвертый вопрос......82Упражнения......861.6. Алгоритмы возведения в степень......102Упражнения......1101.7. Модулярная арифметика......1131.7.1. Элементы теории сравнений......113Определение и свойства сравнений......113Функция Эйлера......115Система вычетов......118Теорема Л. Эйлера......125Сравнение первой степени......126Упражнения......1281.7.2. Китайская теорема об остатках......130Система из двух сравнений......131Упражнения......1461.7.3. Алгоритмы модулярной арифметики......150Упражнения......1561.8. Сравнения второй степени......157Упражнения......165Часть 2. Алгоритмы умножения целых чисел......1672.1. Алгоритм А. А. Карацубы......167Упражнения......1732.2. Алгоритм А. Тоома и С. Кука......176Упражнения......1852.3. Дискретное преобразование Ж. Фурье......186Алгоритм умножения......187Тривиальное решение......189Быстрое дискретное преобразование Ж. Фурье......189Рекурсивная реализация вычисления FFTn(A)......194Обратное дискретное преобразование Ж. Фурье......196Умножение чисел на основе быстрого преобразования Ж. Фурье......201Оптимизация алгоритма......203Упражнения......2112.4. Алгоритм А. Шенхаге и Ф. Штрассена......215Оценка временнóй сложности алгоритма Шенхаге–Штрассена......220Алгоритм Шенхаге–Штрассена......221Упражнения......224Приложения......225Приложение 1. Система быстрого счета Я. Трахтенберга......225Упражнения......238Приложение 2. Дерево Штерна–Броко......240О нумерации рациональных чисел......240Упражнения......244Дерево Штерна–Броко как способ нумерации положительных рациональных чисел......252Упражнения......261Дерево Штерна–Броко как способ приближения одних рациональных чисел другими......271Упражнения......276Дерево Штерна–Броко как система счисления для положительных рациональных чисел......277Упражнения......282