Сравнительный анализ алгоритмов умножения больших чисел

1.

Сравнительный анализ
алгоритмов умножения больших
чисел
Курсовой проект
Автор: Новокшонов М.Р.
Группа: ФИб-2302-52-00
Руководитель: доц. Е.В. Разова
Киров, 2025

2.

Актуальность темы
Умножение больших чисел широко применяется в криптографии, научных
расчетах, Big Data и ИИ
При росте объема данных эффективность классических методов снижается
Возникает необходимость выбора более эффективных алгоритмов

3.

Цель и задачи проекта
Цель: провести анализ и сравнение алгоритмов умножения больших чисел
Задачи:
— изучить алгоритмы (классический, Карацубы, Тоом-Кука, Штрассена, FFT)
— реализовать их на языке C++
— провести эксперимент по сравнению времени работы

4.

Описание алгоритмов
Классический алгоритм — простой, но медленный (O(n²))
Карацуба — рекурсивный метод, сложность около O(n^1.58)
Тоом-Кук — разбиение на блоки, сложность O(n^1.46)
Штрассен — блочный, адаптация из матричной алгебры
FFT — самый быстрый (O(n log n)), но требует осторожности с точностью

5.

Программная реализация
Язык: C++
Использованы библиотеки chrono, vector, string, random
Каждый алгоритм реализован как отдельная функция
Добавлена генерация тестов и измерение времени

6.

Методика эксперимента
Тесты проводились на числах длиной 128, 512, 2048 и 4096 цифр
Повтор каждого теста — для усреднения результата
Учет структуры данных (нули, повторяющиеся цифры и т.д.)
Всего 14 разных тестов

7.

Результаты эксперимента
Классический — лучше на коротких числах (до 128)
Карацуба эффективен при длине больше 500
Тоом-Кук превосходит остальные на 2048 и более
FFT лидирует при 4096, но подвержен погрешностям округления

8.

Выводы и рекомендации
Оптимальный выбор алгоритма зависит от длины чисел
Для малых чисел — классика
Средняя длина — Карацуба и Тоом-Кук
Очень большие числа — FFT при корректной реализации
На практике целесообразен гибридный подход

9.

Спасибо за внимание!
Готов ответить на ваши вопросы