ВВЕДЕНИЕ
1. Постановка задачи 4
2. Исторический обзор алгоритмов быстрого умножения
3. Алгоритм Карацубы
4. Алгоритм быстрого умножения, основанный на преобразовании Фурье
(Шёнхаге-Штрассена)
4.1 Свертка
4.2 Теорема о свертке
4.3 Выбор кольца
4.4 Пример
4.5 Возможные способы усовершенствования алгоритма 13
5. Наивный алгоритм умножения 14
6. Статистика по трем алгоритмам, при различной длине входных значений 15
ЗАКЛЮЧЕНИЕ 17
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 188
ПРИЛОЖЕНИЕ 19
С развитием человечества, а вместе с ним математики и компьютерных наук, сложилась потребность в алгоритмах быстрого умножения длинных чисел. Такие алгоритмы дают возможность компьютеру оперировать числами, которые не помещаются в размерность машинного слова, то есть в регистры процессора.
Данные алгоритмы умножения реализуются не аппаратно, а программно, с использованием базовых аппаратных инструментов работы с числами меньших порядков. При этом, на длину чисел все же накладываются некоторые ограничения, но связаны они только с объемом доступной памяти, и не относятся к аппаратным ограничениям процессора.
Целью работы является реализация одного из алгоритмов быстрого умножения длинных чисел на основе преобразования Фурье, а также некоторых других в среде Visual Studm 2013 на языке C++ и проведение их сравнительного анализа.
План работы:
1. Изучение литературы. Сбор информации о проблеме умножения длинных чисел. Изучить существующие алгоритмы.
2. Реализация алгоритма быстрого умножения Фурье на языке C++.
3. Реализация других алгоритмов быстрого умножения длинных чисел.
4. Проведение исследований характеристик выполнения алгоритмов (скорость работы в различных ситуациях, сложность реализации).
5. Проведение сравнения алгоритмов на основе полученных ранее данных по скорости работы, сложности реализации, а также алгоритмических принципах и алгоритмической сложности.
Объектом исследования является алгоритм умножения длинных чисел на основе преобразования Фурье.
Предметом исследования является реализация, обоснование и сравнительный анализ этого алгоритма.
1. ПОСТАНОВКА ЗАДАЧИ
Работа посвящена изучению алгоритмов длинной арифметики, точнее - быстрому умножению длинных чисел.
Целью дипломной работы является реализация быстрого умножения длинных чисел на основе быстрого преобразования Фурье на языке программирования С++, а так же реализация и последующее сравнение других алгоритмов умножения длинных.
Практическая значимость выпускной квалификационной (дипломной) работы состоит в возможности непосредственного использования результатов работы в других алгоритмах, использующих длинную арифметику, в таких областях как криптография, астрономические вычисления, математическое ПО и т. д.
На основе проведенных качественных и численных оценок можем утверждать, что при реализации алгоритмов быстрого умножения не разумно останавливать свой выбор только на одном из них, так как в этом случае мы получим просадки в скорости работы либо на малых порядках, либо на сверхбольших. Оптимальным решение будет реализовать небольшую проверку длинны входного числа, которая и будет определять какой алгоритм использовать, основываясь на информации о длине числа. Причем на малых порядках лучше использовать наивный алгоритм, а на длинах чисел более 10-15 тысяч десятичных цифр алгоритм на основе преобразования Фурье (Шёнхаге- Штрассена). Казалось бы, глядя на график и таблицу, что на таких длинах быстрее работает алгоритм Карацубы, а Шёнхаге-Штрассена стоит использовать на еще более длинных числах. Но реализация всех трех алгоритмов видится не разумной, так как это займет достаточно много трудочасов, а на длинах чисел, где алгоритм Карацубы быстрее других, лучше использовать алгоритм на основе преобразования Фурье, так как здесь он не существенно уступает Карацуба и вполне может его заменить, тем самым лишив нас необходимости реализации избыточного количества алгоритмов.
В общем итоге мы достигли поставленных целей реализации и сравнения алгоритмов быстрого умножения длинных чисел и пришли к практически значимым выводам, попутно объяснив принципы, на которых построен алгоритм Шёнхаге-Штрассена.
1. Карацуба, А. А. «Сложность вычислений» / А. А. Карацуба // Оптимальное управление и дифференциальные уравнения: сборник статей к семидесятилетию со дня рождения академика Евгения Фроловича Мищенко, М.: МИАН, Наука, Физматлит, 1995, Т. 211. С. 186 - 202. Барановская Т..П., Лойко
B. .И. и другие Информационные системы и технологии в экономике: Учебник - М.: Финансы и статистика, 2003. - 416 с.
2. Кнут, Д. Э. Искусство программирования. В 2 т. Т. 2 / Д.Э. Кнут. Вильямс, 2001. С. 294 - 304.
3. Окулов, С. М. Алгоритмы компьютерной арифметики/ С. М. Окулов, А. В. Лялин, О. А. Пестов, Е. В. Разова. М.: БИНОМ. Лаборатория знаний, 2015.
C. 9 - 186.
4. Статья «Олимпиадное программирование как искусство»
[Электронный ресурс]. URL: ййр://собе1огсез.сот/Ь1од/еп1гу/2100 (дата
обращения: 07.06.2016).
5. Статья «Умножение длинных чисел методом Карацубы» [Электронный ресурс]. URL: ййр://йаЬгайаЬг.гн/роз!/124258/ (дата обращения: 07.03.2016).
6. Статья «Длинная арифметика от Мюгозой» [Электронный ресурс]. URL: ййрз://йаЬгайаЬг.гн/роз!/207754 (дата обращения: 07.03.2016).
7. Дайитбегов Д.М., Черноусов Е.А. Основы алгоритмизации и алгоритмические языки: учебное пособие.- 2-е изд.- М.: Финансы и статистика, 1992.