Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 577346)
Консорциум Контекстум Информационная технология сбора цифрового контента
Уважаемые СТУДЕНТЫ и СОТРУДНИКИ ВУЗов, использующие нашу ЭБС. Рекомендуем использовать новую версию сайта.

Алгоритмы компьютерной арифметики (340,00 руб.)

0   0
АвторыОкулов С. М., Лялин А. В., Пестов О. А., Разова Е. В.
ИздательствоМ.: Лаборатория знаний
Страниц288
ID443329
АннотацияВ книге речь идет о традиционных алгоритмах, которые кажутся очевидными, - об алгоритмах выполнения арифметических операций: о том, сколько тайного смысла и усилий интеллекта многих специалистов по информатике заложено в эти алгоритмы. Материал книги формирует содержательную основу деятельностного изучения алгоритмов компьютерной арифметики, чему способствует стиль изложения, синтезирующий в себе и математический материал, и формализованную запись логики работы компьютера.
Кому рекомендованоДля школьников, преподавателей информатики и студентов информационно-технологических специальностей.
ISBN978-5-00101-657-1
УДК519.85(023)
ББК22.18
Алгоритмы компьютерной арифметики : [учеб. пособие] / С.М. Окулов, А.В. Лялин, О.А. Пестов, Е.В. Разова .— 3-е изд. (эл.) .— Москва : Лаборатория знаний, 2020 .— 288 с. — (Развитие интеллекта школьников) .— Авт. указаны на обороте тит. л.; Деривативное эл. изд. на основе печ. аналога (М.: БИНОМ. Лаборатория знаний, 2014); Электрон. текстовые дан. (1 файл pdf : 288 с.); Систем. требования: Adobe Reader XI; экран 10" .— ISBN 978-5-00101-657-1 .— URL: https://rucont.ru/efd/443329 (дата обращения: 26.01.2022)

Предпросмотр (выдержки из произведения)

АЛГОРИТМЫ КОМПЬЮТЕРНОЙ АРИФМЕТИКИ 2-е издание (электронное) Москва БИНОМ. <...> Материал книги формирует содержательную основу деятельностного изучения алгоритмов компьютерной арифметики, чему способствует стиль изложения, синтезирующий в себе и математический материал, и формализованную запись логики работы компьютера. <...> УДК 519.85(023) ББК 22.18 Деривативное электронное издание на основе печатного аналога: Алгоритмы компьютерной арифметики / С. М. Окулов, А. В. Лялин, О. А. Пестов, Е. В. Разова. <...> И эти открытия способен сделать только человек, имеющий алгоритмическую культуру, на формирование которой направлен в том числе и материал этой книги, включающий кроме методов реализации арифметических операций рассмотрение таких фундаментальных алгоритмов, как бинарный алгоритм возведения в степень, алгоритм Евкли да, китайский алгоритм об остатках и алгоритм быстрого преобразования Фурье. <...> При реализации операций сложения, вычитания, умножения и деления неотрицательных целых чисел мы будем ис8) Считаем, что с темой «системы счисления» читатель знаком. <...> При наличии процедуры Print основная программа для анализа операции сложения двух целых неотрицательных чисел (u, v) записывается так: Begin ReadLn(u,v); Print(u); Print(v); Add(u,v,w); { } Print(w); End. рованы справа налево, как это принято для двоичных чисел. <...> Сложение чисел Фактически требуется реализовать логику сложения одноразрядных чисел с учетом переноса единицы из младшего в старший разряд (переменная k). <...> Представление 16-разрядных целых неотрицательных чисел В криптографии и ряде других областей возникает необходимость работы с числами, занимающими в памяти 1024 разряда и более (назовем такие числа «большими»). <...> Tmax] Of Word; Var u,v,r:Nb; При сложении 1024-битовых чисел изменяется только значение константы Tmax и, соответственно, размер массива для хранения величин. <...> Процедура Add при этом претерпит несущественные изменения: переменную k следует исключить из локальных переменных <...>
Алгоритмы_компьютерной_арифметики.pdf
КАЛГОРИТМЫ АРИФОМПЬЮТЕРНОЙ МЕТИКИ 3-е издание, электронное Москва Лаборатория знаний 2020
Стр.2
УДК 519.85(023) ББК 22.18 О-52 С е р и я о с н о в а н а в 2008 г. Окулов С. М. О-52 Алгоритмы компьютерной арифметики / С. М. Окулов, А. В. Лялин, О. А. Пестов, Е. В. Разова.—3-е изд., электрон.—М. : Лаборатория знаний, 2020.—288 с.— (Развитие интеллекта школьников).—Систем. требования: Adobe Reader XI ; экран 10".— Загл. с титул. экрана.—Текст : электронный. ISBN 978-5-00101-657-1 В книге речь идет о традиционных алгоритмах, которые кажутся очевидными,—об алгоритмах выполнения арифметических операций: о том, сколько тайного смысла и усилий интеллекта многих специалистов по информатике заложено в эти алгоритмы. Материал книги формирует содержательную основу деятельностного изучения алгоритмов компьютерной арифметики, чему способствует стиль изложения, синтезирующий в себе и математический материал, и формализованную запись логики работы компьютера. Для школьников, преподавателей информатики и студентов информационно-технологических специальностей. УДК 519.85(023) ББК 22.18 Деривативное издание на основе печатного аналога: Алгоритмы компьютерной арифметики / С. М. Окулов, А. В. Лялин, О. А. Пестов, Е. В. Разова.—М. : БИНОМ. Лаборатория знаний, 2014.—285 с. : ил.—(Развитие интеллекта школьников).—ISBN 978-5-9963-1549-9. В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации ISBN 978-5-00101-657-1 ○c Лаборатория знаний, 2015
Стр.3
Содержание Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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
Стр.4
4 Содержание Сравнение первой степени . . . . . . . . . . . . . . . . . . . . 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
Стр.5