Читать онлайн «Занимательная компьютерная арифметика. Быстрые алгоритмы операций с числами и многочленами»

ШЕДЕВРЫ HAVKV НАУЧНО-ПОПУЛЯРНОЙ iui«7ii«7 ЛИТЕРАТУРЫ МАТЕ к А С. Б. Гашков 3' ТЕ Ь ' i b UEP > р „ Ет ,. X ( 2г , noon-00 • ( ВСЕМ! Ч" ч^ / # «* метры ч° 1пгоI ы о ераций с числами и много пе ами са URSS НАУКУ— ВСЕМ! Шедевры научно-популярной литературы (математика) С. Б. Гашков ЗАНИМАТЕЛЬНАЯ КОМПЬЮТЕРНАЯ АРИФМЕТИКА Быстрые алгоритмы операций с числами и многочленами URSS МОСКВА ББК 22. 130 22. 19 22. 1 о 32. 8 II 32. 81o 32. 97 Гашков Сергей Борисович Занимательная компьютерная арифметика: Быстрые алгоритмы операций с числами и многочленами. — М. : Книжный дом «ЛИБРОКОМ», 2012. — 224 с. (НАУКУ — ВСЕМ! Шедевры научно-популярной литературы (математика). ) В настоящей книге рассматриваются методы быстрого выполнения различных видов вычислений, рассказывается о реализации быстрых алгоритмов как в виде логических схем — математической модели реальных электронных микросхем, так и в виде компьютерных программ. Исследуются также вопросы о том, как измерить сложность того или иного вычислительного алгоритма и оценить время его работы на компьютере. Ббльшая часть материала книги доступна всем, кто знаком лишь со школьным курсом математики, но и опытный читатель может найти в этой книге кое-что новое для себя. Книга написана на основе лекций, которые автор в разное время читал учащимся физико-математической Школы им. А. Н. Колмогорова при МГУ, на Малом и Большом мехмате, а также на факультетах информационной безопасности и информатики РГГУ. Издательство «Книжный дом "ЛИБРОКОМ"». 117335, Москва, Нахимовский пр-т, 56. Формат 60«90/16. Печ л 14 Зак. № ЖМ-54. Отпечатано в ООО «ЛЕНАНД». 117312, Москва, пр-т Шестидесггилети» Октябри, 11 А, стр. 11. ISBN 978-5-397-02880-6 © Книжный дом «ЛИБРОКОМ», 2012 10585 ID 124753 ШИПИ . 785397 028806" Все права защищены. Никакая часть настоящей книги не может быть воспроизведена или передана в какой бы то ни было форме и какими бы то ни было средствами, будь то электронные или механические, включая фотокопирование и запись на магнитный носитель, а также размещение в Интернете, если на то нет письменного разрешения владельца. Школьные алгоритмы арифметических операций с многочленами 12 Глава 2. Школьные алгоритмы сложения и умножения чисел 19 Глава 3. Умножение столбиком нескольких чисел 25 Глава 4. Переносы при сложении двоичных чисел и теорема Куммера 30 Глава 5. Минимальные формы двоичной записи с цифрами 0 и ± 1 и первая попытка уменьшить сложность умножения 35 Глава 6. Быстрое умножение многочленов 43 Глава 7. Быстрое умножение чисел 50 Схемная реализация метода Карацубы для умножения двоичных чисел 52 Глава 8. Деление многозначных чисел 62 Глава 9. Как представляются отрицательные числа в компьютере 71 Глава 10. SRT-деление 75 Глава 11. Быстрое деление многочленов 94 Глава 12.