Тема: РЕАЛИЗАЦИЯ И ИСЛЕДОВАНИЕ БЫСТРОГО УМНОЖЕНИЯ ДЛИННЫХ ЧИСЕЛ НА ОСНОВЕ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

С развитием человечества, а вместе с ним математики и компьютерных наук, сложилась потребность в алгоритмах быстрого умножения длинных чисел. Такие алгоритмы дают возможность компьютеру оперировать числами, которые не помещаются в размерность машинного слова, то есть в регистры процессора.
Данные алгоритмы умножения реализуются не аппаратно, а программно, с использованием базовых аппаратных инструментов работы с числами меньших порядков. При этом, на длину чисел все же накладываются некоторые ограничения, но связаны они только с объемом доступной памяти, и не относятся к аппаратным ограничениям процессора.
Целью работы является реализация одного из алгоритмов быстрого умножения длинных чисел на основе преобразования Фурье, а также некоторых других в среде Visual Studm 2013 на языке C++ и проведение их сравнительного анализа.
План работы:
1. Изучение литературы. Сбор информации о проблеме умножения длинных чисел. Изучить существующие алгоритмы.
2. Реализация алгоритма быстрого умножения Фурье на языке C++.
3. Реализация других алгоритмов быстрого умножения длинных чисел.
4. Проведение исследований характеристик выполнения алгоритмов (скорость работы в различных ситуациях, сложность реализации).
5. Проведение сравнения алгоритмов на основе полученных ранее данных по скорости работы, сложности реализации, а также алгоритмических принципах и алгоритмической сложности.
Объектом исследования является алгоритм умножения длинных чисел на основе преобразования Фурье.
Предметом исследования является реализация, обоснование и сравнительный анализ этого алгоритма.
1. ПОСТАНОВКА ЗАДАЧИ
Работа посвящена изучению алгоритмов длинной арифметики, точнее - быстрому умножению длинных чисел.
Целью дипломной работы является реализация быстрого умножения длинных чисел на основе быстрого преобразования Фурье на языке программирования С++, а так же реализация и последующее сравнение других алгоритмов умножения длинных.
Практическая значимость выпускной квалификационной (дипломной) работы состоит в возможности непосредственного использования результатов работы в других алгоритмах, использующих длинную арифметику, в таких областях как криптография, астрономические вычисления, математическое ПО и т. д.
Купить

На основе проведенных качественных и численных оценок можем утверждать, что при реализации алгоритмов быстрого умножения не разумно останавливать свой выбор только на одном из них, так как в этом случае мы получим просадки в скорости работы либо на малых порядках, либо на сверхбольших. Оптимальным решение будет реализовать небольшую проверку длинны входного числа, которая и будет определять какой алгоритм использовать, основываясь на информации о длине числа. Причем на малых порядках лучше использовать наивный алгоритм, а на длинах чисел более 10-15 тысяч десятичных цифр алгоритм на основе преобразования Фурье (Шёнхаге- Штрассена). Казалось бы, глядя на график и таблицу, что на таких длинах быстрее работает алгоритм Карацубы, а Шёнхаге-Штрассена стоит использовать на еще более длинных числах. Но реализация всех трех алгоритмов видится не разумной, так как это займет достаточно много трудочасов, а на длинах чисел, где алгоритм Карацубы быстрее других, лучше использовать алгоритм на основе преобразования Фурье, так как здесь он не существенно уступает Карацуба и вполне может его заменить, тем самым лишив нас необходимости реализации избыточного количества алгоритмов.
В общем итоге мы достигли поставленных целей реализации и сравнения алгоритмов быстрого умножения длинных чисел и пришли к практически значимым выводам, попутно объяснив принципы, на которых построен алгоритм Шёнхаге-Штрассена.

Купить