FFT (高速フーリエ変換)
Last updated：2018-03-31 04:16:51
Tweet
Category:数学,
Tag：
FFT
概要
列$a$,$b$について，$a$,$b$を畳み込んで次の列$c$を作る:
\[c_k = \sum_{i=0}^k a_i b_{k-i}\]計算量
$N$を$\max(|a|, |b|)$より大きい$2$ベキの数として，$O(N\log N)$.
使い方
FFTはdouble型の演算を行うため誤差に注意
$m_a:=\max(a), m_b:=\max(b), n:=\min(|a|, |b|)$として,
$m_a m_b n \leq 2^{53}$が限度.
// 列a, bを用意
std::vector<int> a, b;
// a，bを畳み込んだ結果をcとする
std::vector<int> c(FFT::mul(a, b));
実装例
以下は非再帰，not-in-placeの実装．