DFTを速くやってくれるやつ。繰り返しになる部分を良い感じに処理してくれるのでO(n2)の計算がO(nlogn)が出来てしまう。多倍長乗算に応用されている。 離散フーリエ変換の計算法(pdf): 周期間引きというのは周期領域で行の入れ替えをすること 離散フーリエ変…