快速傅里叶变换与多项式乘法优化

1 .快速傅里叶变换与多项式乘法优化 5120309037 赵卓越

2 .多项式乘法 有 2n 项，直接计算的时间复杂度为 n-1 次多项式也可以用 n 个不同的点表示  

3 .离散傅里叶变换 (DFT) 定义 逆变换（ IDFT ） 时间复杂度

4 .快速傅里叶变换 (FFT) 二 分思想 递归实现 迭代实现

5 .递归实现 Vector Recursive_FFT (Vector x){ if (n == 1) return x; Vector x0, x1; for ( auto i = x.begin (); i!= x.end ();){ x0.push_back(*i++); x1.push_back(*i++); } x0 = Recursive_FFT (x0); x1 = Recursive_FFT (x1); Complex w0(1.0); Complex w1( exp (Complex(0.0 , - 2 * pi / x.size ()))); for ( int i = 0; i < x0.size(); ++i, w0 *= w1){ x[i] = x0[i] + w0 * x1[i]; x[i + x0.size()] = x0[i] - w0 * x1[i]; } return x; }

6 .递归实现 Vector Recursive_FFT (Vector x){ if (n == 1) return x; Vector x0, x1; for ( auto i = x.begin (); i!= x.end ();){ x0.push_back(*i++); x1.push_back(*i++); } x0 = Recursive_FFT (x0); x1 = Recursive_FFT (x1); Complex w0(1.0); Complex w1( exp (Complex(0.0 , - 2 * pi / x.size ()))); for ( int i = 0; i < x0.size(); ++i, w0 *= w1){ x[i] = x0[i] + w0 * x1[i]; x[i + x0.size()] = x0[i] - w0 * x1[i]; } return x; }

7 .void iterative_fft (Vector& a, int sign = -1){ bit_reverse (a); for (unsigned s = 1; s < a.size (); s <<= 1){ Complex w0( exp (Complex(0.0, sign * pi_mul2 / (s << 1)))); for (unsigned i = 0; i < a.size (); i += (s << 1)){ Complex w(1.0); for (unsigned k = 0; k < s; ++k, w*=w0){ Complex t1 = w * a[i + k + s]; Complex t2 = a[i + k]; a[i + k] = t2 + t1; a[i + k + s] = t2 - t1; } } } } inline void inverse_fft (Vector& v){ iterative_fft (v, 1); for (Vector::iterator i = v.begin (); i != v.end (); ++i) *i /= v.size (); }