１の原始N乗根による表現を使った離散フーリエ変換

これなら分かる 応用数学教室4.6 「１の原始N乗根による表現」

普通の（fastじゃない）離散フーリエ変換に引き続き。 $$\omega_N = e^{i 2\pi/N}$$

とすると

$$\begin{align} F_k &= \frac{1}{N} \sum_{l=0}^{N-1} f_l e^{-i 2\pi kl/N} \\ &= \frac{1}{N} \sum_{l=0}^{N-1} f_l(\omega_N)^{-kl} \\ \end{align}$$ $\overline{\omega_N} = \omega_N^{-1}$ より（上バーは[複素数の共役](http://onohiro.hp.infoseek.co.jp/amanojack2/a/kisokaku018.htm)をあらわす） $$= \frac{1}{N} \sum_{l=0}^{N-1} f_l \overline{\omega_N^{kl} }$$ $\overline{ab} = \overline{a} \cdot \overline{b}$ より $$\begin{align} &= \frac{1}{N} \overline{\overline{ \sum_{l=0}^{N-1} f_l \overline{\omega_N^{kl} } }} \\ &= \frac{1}{N} \overline{ \sum_{l=0}^{N-1} \overline{f_l} \omega_N^{kl} } \\ \end{align}$$

となる。

$b_k = \sum_{l=0}^{N-1} a_l \omega_N^{kl}$ , $a_l = \overline{f_l}$ とすれば、 $$F_k = \overline{b_k} / N.$$

プログラム化

RubyのComplexを使って

require 'complex' # 原始N乗根 def primitiveNthRoot(n, k=1) t = 2 * Math::PI * k / n Complex(Math.cos(t), Math.sin(t)) end # 係数計算 def calcb(a, k) n = a.length (0...n).inject(Complex(0, 0)) do |r, l| wklN = primitiveNthRoot(n, k * l) r + a[l] * wklN end end # 離散フーリエ変換 def dft(fs) n = fs.length a = fs.map{|fl| Complex(fl, 0)} b = (0...n).map {|k| calcb(a, k)} b.map {|be| be.conjugate / n} end p dft([1,7,3,2,0,5,0,8])

結果：

[(3.25-0.0i), (0.8321067811865474-0.021446609406726047i), (-0.2500000000000002-0.25i), (-0.5821067811865479+0.7285533905932745i), (-2.25-1.3471114790620886e-15i), (-0.5821067811865464-0.7285533905932751i), (-0.2500000000000022+0.25i), (0.8321067811865511+0.02144660940672849i)]

• O(N^2)