Курсовая работа по C++
Курсовая работа 3 семестра по теме: Умножение длинных чисел используя быстрое преобразование Фурье. Исходный код доступен на GitHub
Оглавление
Постановка задачи
Разработать программу которая использует быстрое преобразование Фурье для умножения длинных чисел. Программа должна уметь считывать числа из файлов и иметь интерфейс командной строки.
Описание алгоритмов
В программе используются три основных алгоритма: алгоритм быстрого преобразования Фурье, алгоритм умножения длинных чисел используя БПФ, и алгоритм умножения в столбик. В программе также присутствует функционал бенчмарка для сравнения двух алгоритмов умножения.
Быстрое преобразование Фурье
Быстрое преобразование Фурье (БПФ, FFT) — алгоритм ускоренного вычисления дискретного преобразования Фурье, позволяющий получить результат за время, меньшее чем O(n^2) (требуемого для прямого, поформульного вычисления).
Дискретное преобразование Фурье (ДПФ, DFT) — преобразование конечных последовательностей (комплексных) чисел, которое, как и в непрерывном случае, превращает свёртку в поточечное умножение. Используется в цифровой обработке сигналов и в других ситуациях, где необходимо быстро выполнять свёртку, например, при умножении больших чисел.
Для увеличения эффективности в этой реализации не используется рекурсия в явном виде. В рекурсивной реализации необходимо разделять вектор на два вектора — элементы на четных позициях относятся к одному временно созданному вектору, а на нечетных — к другому. Однако, если мы применим поразрядно обратную перестановку, то необходимость в создании временных векторов отпадает, так как все вычисления теперь можно производить на месте, прямо в исходном векторе.
Теперь выполним работу, выполняемую нижним уровнем рекурсии, разделим вектор на пары элементов, для каждого применим преобразование бабочки, в результате в векторе будут находиться результаты работы нижнего уровня рекурсии. На следующем шаге разделим вектор на четвёрки элементов, к каждой применим преобразование бабочки, в результате получим ДПФ для каждой четверки, и так далее, пока не получим ДПФ для всего вектора.
Затем выполняется lg(n-1) стадий алгоритма, на k-ой из которых вычисляются ДПФ для блоков длины 2k. Для всех этих блоков будет одно и то же значение первообразного корня, которое запоминается в переменной. Цикл итерируется по блокам, а вложенный в него цикл применяет преобразование бабочки ко всем элементам блока.
Если нам нужно найти обратное ДПФ, то после выполнения предыдущих операций, в еще одном цикле проходим по всем элементам полученного вектора, и каждый элемент делим на длину вектора.
Реализация быстрого преобразования Фурье на языке C++:
#include <cmath>
#include <complex>
#include <vector>
constexpr double M_2PI = 2 * M_PI;
void fft(vector<base> &a, bool invert) {
size_t n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j >= bit; bit >>= 1) j -= bit;
j += bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = M_2PI / len * (invert ? -1 : 1);
base wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
base w(1);
for (int j = 0; j < len / 2; j++) {
base u = a[i + j], v = a[i + j + len / 2] * w;
a[i + j] = u + v;
a[i + j + len / 2] = u - v;
w *= wlen;
}
}
}
if (invert)
for (base &x : a) x /= n;
}Так как внешний цикл имеет lg(n) итераций, а внутренний ровно n итераций, то общая оценка сложности алгоритма — O(n log n).
Умножение с помощью БПФ
Для перемножения двух длинных чисел с помощью быстрого преобразования Фурье они должны быть представлены как векторы разрядов. Для упрощения реализации создадим вспомогательный класс Number :
class Number {
private:
std::vector<int> digits;
bool negative;
};При умножении создается два вектора комплексных чисел, в которые копируются разряды исходных чисел. Для гарантии отсутствия переполнения оба вектора расширяются до ближайшей степени двойки и еще вдвое.
Затем над обоими векторами производится БПФ и выполняется поэлементное умножение векторов. Результат записывается в первый вектор. После этого над ним производится обратное БПФ. Однако здесь проявляется проблема большой погрешности при вычислении БПФ: погрешность может оказаться значительной, поэтому мнимые числа округляются самым надёжным способом — прибавлением 0.5 к действительной части и последующим округлением вниз.
После этого нормализуем результат, выполняя все переносы разрядов, и убираем незначащие нули.
Реализация умножения длинных чисел с использованием БПФ на языке C++:
Number fft_multiply(const Number &a, const Number &b) {
vector<base> fa(a.digits.begin(), a.digits.end());
vector<base> fb(b.digits.begin(), b.digits.end());
int n = 1;
while (n < a.size() + b.size()) n <<= 1;
fa.resize(n), fb.resize(n);
fft(fa, false), fft(fb, false);
for (int i = 0; i < n; i++) fa[i] *= fb[i];
fft(fa, true);
vector<int> result(n);
for (int i = 0; i < n; i++) {
result[i] = int(fa[i].real() + 0.5);
}
for (int i = 0; i < n - 1; i++) {
result[i + 1] += result[i] / 10;
result[i] %= 10;
}
while (result.size() > 1 && result.back() == 0) result.pop_back();
return Number(result, a.negative != b.negative);
}Алгоритм имеет сложность O(n log n), так как такую сложность имеет алгоритм БПФ, а поэлементное умножение векторов выполняется за линейное время. Алгоритм крайне эффективен при умножении длинных чисел, но уступает умножению в столбик при умножении чисел, у которых меньше 500 знаков, из-за достаточно сложных операций с комплексными числами.
Умножение в столбик
Умножение в столбик — простейший из алгоритмов умножения, известный всем еще со школы. Алгоритм также предельно прост в реализации.
Создается вектор длины равной сумме длин исходных чисел. Далее в цикле проходимся по всем цифрам первого числа, и для каждой из них проходимся по всем цифрам второго числа, перемножая эти цифры и записывая в результирующий вектор по индексу i + j, где i и j - индекс разряда в первом и втором векторах соответственно. После этого нормализуем результат, выполняя все переносы разрядов, и убираем незначащие нули.
Реализация умножения в столбик на языке C++ (используя ранее объявленный класс Number):
Number column_multiply(const Number &a, const Number &b) {
vector<int> result(a.size() + b.size(), 0);
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < b.size(); j++) {
result[i + j] += a[i] * b[j];
}
}
for (int i = 0; i < result.size() - 1; i++) {
result[i + 1] += result[i] / 10;
result[i] %= 10;
}
while (result.size() > 1 && result.back() == 0) result.pop_back();
return Number(result, a.is_negative() ^ b.is_negative());
}Алгоритм имеет сложность O(n^2) и крайне эффективен при умножении небольших чисел (менее 500 разрядов), но при увеличении длины его становится практически невозможно использовать в силу слишком большого времени выполнения.
Тестирование и бенчмарк
Для теста были созданы текстовые файлы содержащие длинные числа с размером от 2⁰ до 2²⁴ знаков. Для каждой пары чисел количество итерации выбиралось индивидуально, так, чтобы время выполнения всех итераций было приемлимо (≤ 30 мин), но при этом сохранялась достаточная точность (> 10 сек).
Примечание: для чисел длиннее 2²⁰ время выполнения алгоритма умножения в столбик не измерялось, из-за слишком большого времени выполнения даже одной итерации.
Интерактивный пример
Курсовая работа размещена в открытом доступе на GitHub и Repl.it в образовательных целях для студентов ГУАПа и других вузов
Краткая инструкция
- Нажмите Run
- Введите первое и второе число (числа могут быть абсолютно любого размера, на то она вам и длинная арифметика)
- Получите результат
Для выхода из программы достаточно просто нажать Enter в поле ввода. После выхода можно заново запустить выполнение кнопкой Run или командой ./main -i -b 100 в которой при необходимости можно изменить или добавить дополнительные аргументы (см. справку: --help)
Список источников
- Быстрое преобразование Фурье за O (N log N). Применение к умножению двух полиномов или длинных чисел