Занимательная компьютерная арифметика, Быстрые алгоритмы операций с числами и многочленами, Гашков С.Б., 2012

Занимательная компьютерная арифметика, Быстрые алгоритмы операций с числами и многочленами, Гашков С.Б., 2012.

   В настоящей книге рассматриваются методы быстрого выполнения различных видов вычислений, рассказывается о реализации быстрых алгоритмов как в виде логических схем — математической модели реальных электронных микросхем, так и в виде компьютерных программ. Исследуются также вопросы о том, как измерить сложность того или иного вычислительного алгоритма и оценить время его работы на компьютере. Большая часть материала книги доступна всем, кто знаком лишь со школьным курсом математики, но и опытный читатель может найти в этой книге кое-что новое для себя.
Книга написана на основе лекций, которые автор в разное время читал учащимся физико-математической Школы им. А. Н. Колмогорова при МГУ, на Малом и Большом мехмате, а также на факультетах информационной безопасности и информатики РГГУ.




Некоторые быстрые алгоритмы работы с битами.
Встречаются ситуации, когда приходится выполнять операции не с числами, а с битами, составляющими эти числа (или машинные слова). Для этого используются команды языка ассемблера. Но и язык С (и С++) имеет возможности для непосредственной работы с битами. Для быстрого выполнения различных манипуляций с битами в программистском фольклоре и в литературе известно множество различных эффективных программ. Замечательная коллекция таких трюков содержится в уже упоминавшейся книге Г. Уоррена. Приведем здесь некоторые из них.

Рассмотрим задачу подсчета числа единичных битов в машинном слове (т. е. количества единичных разрядов в данном 32-битном числе х), Известно много элегантных и эффективных решений этой задачи. Приведем одно из самых лучших. Заметим, что рассматриваемая задача очень близка к задаче построения логической схемы, выполняющей суммирование n однобитных чисел в двоичной системе счисления. Известно, что такую схему можно построить следующим образом. Разобьем эти числа на пары и сложим каждую пару. Получим n/2 двухбитных чисел. Эти числа опять разобьем на пары и сложим каждую пару. Получим n/4 трехбитных чисел. Разобьем эти числа на пары и сложим каждую пару. Получим n/8 четырехбитных чисел. Далее получаем n/16 пятибитных чисел и т. д. В результате получится одно (1оg2 n+1)-битное число (предполагаем, что n есть степень двойки), которое и равно сумме всех n чисел, а другими словами, количеству единиц среди них.

ОГЛАВЛЕНИЕ.
От автора.
Введение.
Глава 1. Школьные алгоритмы арифметических операций с многочленами.
Глава 2. Школьные алгоритмы сложения и умножения чисел.
Глава 3. Умножение столбиком нескольких чисел.
Глава 4. Переносы при сложении двоичных чисел и теорема Куммера.
Глава 5. Минимальные формы двоичной записи с цифрами 0 и ± 1 и первая попытка уменьшить сложность умножения.
Глава 6. Быстрое умножение многочленов.
Глава 7. Быстрое умножение чисел.
Схемная реализация метода Карацубы для умножения двоичных чисел.
Глава 8. Деление многозначных чисел.
Глава 9. Как представляются отрицательные числа в компьютере.
Глава 10. SRТ-деление.
Глава 11. Быстрое деление многочленов.
Глава 12. Быстрое деление чисел.
Глава 13. Сравнение сложности умножения, деления, возведения в квадрат и извлечения квадратного корня.
Глава 14. О сложности преобразования чисел из одной системы в другую.
Глава 15. Модулярная арифметика и китайская теорема об остатках.
Глава 16. Сложность операций модулярной арифметики.
Как найти остаток от деления, не вычисляя частное.
Глава 17. Умножение и деление на константы.
Глава 18. Некоторые быстрые алгоритмы работы с битами.
Маленькие хитрости в работе с битами.
Глава 19. Вычисление некоторых целочисленных элементарных функций.
Целочисленный квадратный корень.
Целочисленные логарифмы.
Глава 20. Быстрые операции с дробно-рациональными функциями.
Быстрое сложение дробно-рациональных функций.
Быстрый китайский алгоритм.
Быстрая интерполяция.
Еще о быстром умножении многочленов.
Глава 21. Варианты алгоритма Евклида.
Алгоритм Евклида с выбором минимального остатка.
Бинарный алгоритм Евклида.
Глава 22. Еще о схеме Горнера.
Глава 23. Что можно вычислить на счетах.
Литература.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Занимательная компьютерная арифметика, Быстрые алгоритмы операций с числами и многочленами, Гашков С.Б., 2012 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - djvu - Яндекс.Диск.




Теги: учебник по информатике :: информатика :: компьютеры :: Гашков :: алгоритм :: арифметика