М.: Либроком, 2012. — 224 с. — (Науку - всем!) — ISBN
9785397028806.
В настоящей книге рассматриваются методы быстрого выполнения
различных видов вычислений, рассказывается о реализации быстрых
алгоритмов как в виде логических схем - математической модели
реальных электронных микросхем, так и в виде компьютерных программ.
Исследуются также вопросы о том, как измерить сложность того или
иного вычислительного алгоритма и оценить время его работы на
компьютере. Большая часть материала книги доступна всем, кто знаком
лишь со школьным курсом математики, но и опытный читатель может
найти в этой книге кое-что новое для себя.
Книга написана на основе лекций, которые автор в разное время читал учащимся физико-математической Школы им. А.Н. Колмогорова при МГУ, на Малом и Большом мехмате, а также на факультетах информационной безопасности и информатики РГГУ. От автора
Введение
Школьные алгоритмы арифметических операций с многочленами
Школьные алгоритмы сложения и умножения чисел
Умножение столбиком нескольких чисел
Переносы при сложении двоичных чисел и теорема Куммера
Минимальные формы двоичной записи с цифрами 0 и ±1 и первая попытка уменьшить сложность умножения
Быстрое умножение многочленов
Быстрое умножение чисел
Схемная реализация метода Карацубы для умножения двоичных чисел
Деление многозначных чисел
Как представляются отрицательные числа в компьютере
SRT-деление
Быстрое деление многочленов
Быстрое деление чисел
Сравнение сложности умножения, деления, возведения в квадрат и извлечения квадратного корня
О сложности преобразования чисел из одной системы в другую
Модулярная арифметика и китайская теорема об остатках
Сложность операций модулярной арифметики
Как найти остаток от деления не вычисляя частное
Умножение и деление на константы
Некоторые быстрые алгоритмы работы с битами
Маленькие хитрости в работе с битами
Вычисление некоторых целочисленных элементарных функций
Целочисленный квадратный корень
Целочисленные логарифмы
Быстрые операции с дробно-рациональными функциями
Быстрое сложение дробно-рациональных функций
Быстрый китайский алгоритм
Быстрая интерполяция
Еще о быстром умножении многочленов
Варианты алгоритма Евклида
Алгоритм Евклида с выбором минимального остатка
Бинарный алгоритм Евклида
Ещё о схеме Горнера
Что можно вычислить на счетах
Литература
Книга написана на основе лекций, которые автор в разное время читал учащимся физико-математической Школы им. А.Н. Колмогорова при МГУ, на Малом и Большом мехмате, а также на факультетах информационной безопасности и информатики РГГУ. От автора
Введение
Школьные алгоритмы арифметических операций с многочленами
Школьные алгоритмы сложения и умножения чисел
Умножение столбиком нескольких чисел
Переносы при сложении двоичных чисел и теорема Куммера
Минимальные формы двоичной записи с цифрами 0 и ±1 и первая попытка уменьшить сложность умножения
Быстрое умножение многочленов
Быстрое умножение чисел
Схемная реализация метода Карацубы для умножения двоичных чисел
Деление многозначных чисел
Как представляются отрицательные числа в компьютере
SRT-деление
Быстрое деление многочленов
Быстрое деление чисел
Сравнение сложности умножения, деления, возведения в квадрат и извлечения квадратного корня
О сложности преобразования чисел из одной системы в другую
Модулярная арифметика и китайская теорема об остатках
Сложность операций модулярной арифметики
Как найти остаток от деления не вычисляя частное
Умножение и деление на константы
Некоторые быстрые алгоритмы работы с битами
Маленькие хитрости в работе с битами
Вычисление некоторых целочисленных элементарных функций
Целочисленный квадратный корень
Целочисленные логарифмы
Быстрые операции с дробно-рациональными функциями
Быстрое сложение дробно-рациональных функций
Быстрый китайский алгоритм
Быстрая интерполяция
Еще о быстром умножении многочленов
Варианты алгоритма Евклида
Алгоритм Евклида с выбором минимального остатка
Бинарный алгоритм Евклида
Ещё о схеме Горнера
Что можно вычислить на счетах
Литература