old/fast_fourier_transform.cpp

category: old
View this file on GitHub
- Last commit date: 2019-11-09 02:16:51+09:00

Code

#include <iostream>
#include <complex>
#include <vector>
using namespace std;

const int N = (1 << 18); // 最大次数
const double PI = acos(-1);
typedef complex<double> comp;

vector<comp> dft(vector<comp> f, int n, bool doesinv)
{
  if (n == 1)
    return f;
  vector<comp> f0, f1;
  for (auto i = 0; i < n / 2; i++)
  {
    f0.push_back(f[2 * i]);
    f1.push_back(f[2 * i + 1]);
  }
  f0 = dft(f0, n / 2, doesinv);
  f1 = dft(f1, n / 2, doesinv);
  comp zeta;
  if (!doesinv)
  {
    zeta = comp(cos(2 * PI / n), sin(2 * PI / n));
  }
  else
  {
    zeta = comp(cos(2 * PI / n), -1 * sin(2 * PI / n));
  }
  comp pow_zeta = comp(1, 0);
  for (auto i = 0; i < n; i++)
  {
    f[i] = f0[i % (n / 2)] + pow_zeta * f1[i % (n / 2)];
    pow_zeta = pow_zeta * zeta;
  }
  return f;
}

vector<comp> multiply(vector<comp> g, vector<comp> h)
{
  vector<comp> gg = dft(g, N, false);
  vector<comp> hh = dft(h, N, false);
  vector<comp> ff = vector<comp>(N);
  for (auto i = 0; i < N; i++)
  {
    ff[i] = gg[i] * hh[i];
  }
  vector<comp> ans = dft(ff, N, true);
  for (auto i = 0; i < N; i++)
  {
    ans[i] = ans[i] / comp(N, 0);
  }
  return ans;
}

int main()
{
}

#line 1 "old/fast_fourier_transform.cpp"
#include <iostream>
#include <complex>
#include <vector>
using namespace std;

const int N = (1 << 18); // 最大次数
const double PI = acos(-1);
typedef complex<double> comp;

vector<comp> dft(vector<comp> f, int n, bool doesinv)
{
  if (n == 1)
    return f;
  vector<comp> f0, f1;
  for (auto i = 0; i < n / 2; i++)
  {
    f0.push_back(f[2 * i]);
    f1.push_back(f[2 * i + 1]);
  }
  f0 = dft(f0, n / 2, doesinv);
  f1 = dft(f1, n / 2, doesinv);
  comp zeta;
  if (!doesinv)
  {
    zeta = comp(cos(2 * PI / n), sin(2 * PI / n));
  }
  else
  {
    zeta = comp(cos(2 * PI / n), -1 * sin(2 * PI / n));
  }
  comp pow_zeta = comp(1, 0);
  for (auto i = 0; i < n; i++)
  {
    f[i] = f0[i % (n / 2)] + pow_zeta * f1[i % (n / 2)];
    pow_zeta = pow_zeta * zeta;
  }
  return f;
}

vector<comp> multiply(vector<comp> g, vector<comp> h)
{
  vector<comp> gg = dft(g, N, false);
  vector<comp> hh = dft(h, N, false);
  vector<comp> ff = vector<comp>(N);
  for (auto i = 0; i < N; i++)
  {
    ff[i] = gg[i] * hh[i];
  }
  vector<comp> ans = dft(ff, N, true);
  for (auto i = 0; i < N; i++)
  {
    ans[i] = ans[i] / comp(N, 0);
  }
  return ans;
}

int main()
{
}