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

普通の(fastじゃない)離散フーリエ変換に引き続き。

とすると

より(上バーは複素数の共役をあらわす)

より

となる。

, とすれば、

プログラム化

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)