Быстрое преобразование Фурье: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: « using Complex = complex<double>; void fft(vector<Complex> &p, Complex x) { size_t n = p.size(); if (n == 1) return; vector<Complex>...»)
 
 
Строка 64: Строка 64:
== Ссылки ==
== Ссылки ==


Видео
* [https://www.youtube.com/watch?v=h7apO7q16V0 Reducible — The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?]
Теория
Теория
* [http://e-maxx.ru/algo/fft_multiply e-maxx.ru — Быстрое преобразование Фурье за O (N log N). Применение к умножению двух полиномов или длинных чисел]
* [http://e-maxx.ru/algo/fft_multiply e-maxx.ru — Быстрое преобразование Фурье за O (N log N). Применение к умножению двух полиномов или длинных чисел]

Текущая версия от 00:23, 12 октября 2021

using Complex = complex<double>;

void fft(vector<Complex> &p, Complex x) {
    size_t n = p.size();
    if (n == 1)
        return;

    vector<Complex> a(n / 2), b(n / 2);
    for (int i = 0; i < n / 2; i++) {
        a[i] = p[2 * i];
        b[i] = p[2 * i + 1];
    }

    fft(a, x * x);
    fft(b, x * x);

    Complex xPow = 1;
    for (int i = 0; i < n / 2; i++) {
        p[i] = a[i] + xPow * b[i];
        p[n / 2 + i] = a[i] - xPow * b[i];
        xPow *= x;
    }
}

const double PI = acos(-1);

vector<Complex> fixSize(vector<int> &p, int targetSize) {
    vector<Complex> res(p.begin(), p.end());
    while (res.size() < targetSize || (res.size() & (res.size() - 1)))
        res.push_back(0);
    return res;
}

vector<Complex> evaluate(vector<int> &p, int targetSize) {
    vector<Complex> res = fixSize(p, targetSize);
    fft(res, polar(1.0, 2 * PI / res.size()));
    return res;
}

vector<int> interpolate(vector<Complex> &p) {
    int n = p.size();
    fft(p, polar(1.0, -2 * PI / n));

    vector<int> res(n);
    for (int i = 0; i < n; i++)
        res[i] = round(real(p[i]) / n);

    while (res.size() > 1 && !res.back())
        res.pop_back();
    return res;
}

vector<int> multiply(vector<int> &pa, vector<int> &pb) {
    int targetSize = pa.size() + pb.size();
    vector<Complex> a = evaluate(pa, targetSize);
    vector<Complex> b = evaluate(pb, targetSize);

    for (int i = 0; i < a.size(); i++)
        a[i] *= b[i];

    return interpolate(a);
}

Ссылки

Видео

Теория

Код