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

1.

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

2.

Актуальность темы
Умножение больших чисел важно в криптографии, науке, ИИ
Классические методы неэффективны при больших данных
Необходим анализ более быстрых алгоритмов

3.

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

4.

Алгоритмы умножения
- Классический алгоритм: простой, но медленный (O(n^2))
- Карацуба: рекурсивный, O(n^1.58)
- Toom-Cook: деление на блоки, O(n^1.46)
- Штрассен: блочный подход, матричная идея
- FFT: самый быстрый (O(n log n)), но сложный

5.

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

6.

Методика эксперимента
Тесты на числах длиной 128, 512, 2048, 4096 цифр
Повторное выполнение — усреднение времени
Проверка устойчивости к структуре данных
14 тестов: от нулей до одинаковых цифр

7.

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

8.

Выводы
Нет универсального алгоритма
Для коротких — классика, для больших — FFT и Toom
На практике — гибридный подход
Разработанное ПО подтвердило теорию на практике

9.

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