ВВЕДЕНИЕ
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. ПОСТАНОВКА ЗАДАЧИ
Работа посвящена изучению алгоритмов длинной арифметики, точнее - быстрому умножению длинных чисел.
Целью дипломной работы является реализация быстрого умножения длинных чисел на основе быстрого преобразования Фурье на языке программирования С++, а так же реализация и последующее сравнение других алгоритмов умножения длинных.
Практическая значимость выпускной квалификационной (дипломной) работы состоит в возможности непосредственного использования результатов работы в других алгоритмах, использующих длинную арифметику, в таких областях как криптография, астрономические вычисления, математическое ПО и т. д.
Купить