С++ это не страшно
October 7, 2022

Курсовая работа по 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 в образовательных целях для студентов ГУАПа и других вузов

Краткая инструкция

  1. Нажмите Run
  2. Введите первое и второе число (числа могут быть абсолютно любого размера, на то она вам и длинная арифметика)
  3. Получите результат

Для выхода из программы достаточно просто нажать Enter в поле ввода. После выхода можно заново запустить выполнение кнопкой Run или командой ./main -i -b 100 в которой при необходимости можно изменить или добавить дополнительные аргументы (см. справку: --help)

Курсовая работа размещенная на Replit

Список источников

  1. Быстрое преобразование Фурье за O (N log N). Применение к умножению двух полиномов или длинных чисел