FFT

高速フーリエ変換 (FFT : Fast Fourier Transform) とは, 離散フーリエ変換のサイズが 2 のべき乗の場合に, 高速に計算できるアルゴリズムのことです.

アルゴリズムの導出

離散フーリエ変換のサイズ ($N$) が 8 の場合を例に導出します.

$ \begin{eqnarray} X(k)=\sum_{n=0}^{N-1}x(n)\exp\left(\frac{-j2\pi kn}{N}\right) \end{eqnarray} $

離散フーリエ変換の公式は, 以下のように行列で表現することができます.

$ \begin{eqnarray} x(n)=\left[ \begin{array}{c} x(0) \\
x(1) \\
x(2) \\
x(3) \\
x(4) \\
x(5) \\
x(6) \\
x(7) \\
\end{array} \right] \end{eqnarray} $

$ \begin{eqnarray} X(k)=\left[ \begin{array}{c} X(0) \\
X(1) \\
X(2) \\
X(3) \\
X(4) \\
X(5) \\
X(6) \\
X(7) \\
\end{array} \right] \end{eqnarray} $

$ \begin{eqnarray} W_{8}=\exp\left(\frac{-j2\pi}{8}\right) \end{eqnarray} $

$ \begin{eqnarray} X(k)=\left[ \begin{array}{cccccccc} W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} \\
W^{0}_{8} & W^{1}_{8} & W^{2}_{8} & W^{3}_{8} & W^{4}_{8} & W^{5}_{8} & W^{6}_{8} & W^{7}_{8} \\
W^{0}_{8} & W^{2}_{8} & W^{4}_{8} & W^{6}_{8} & W^{8}_{8} & W^{10}_{8} & W^{12}_{8} & W^{14}_{8} \\
W^{0}_{8} & W^{3}_{8} & W^{6}_{8} & W^{9}_{8} & W^{12}_{8} & W^{15}_{8} & W^{18}_{8} & W^{21}_{8} \\
W^{0}_{8} & W^{4}_{8} & W^{8}_{8} & W^{12}_{8} & W^{16}_{8} & W^{20}_{8} & W^{24}_{8} & W^{28}_{8} \\
W^{0}_{8} & W^{5}_{8} & W^{10}_{8} & W^{15}_{8} & W^{20}_{8} & W^{25}_{8} & W^{30}_{8} & W^{35}_{8} \\
W^{0}_{8} & W^{6}_{8} & W^{12}_{8} & W^{18}_{8} & W^{24}_{8} & W^{30}_{8} & W^{36}_{8} & W^{42}_{8} \\
W^{0}_{8} & W^{7}_{8} & W^{14}_{8} & W^{21}_{8} & W^{28}_{8} & W^{35}_{8} & W^{42}_{8} & W^{49}_{8} \\
\end{array} \right]x(n) \end{eqnarray} $

ここで, 以下の関係 (オイラーの公式から導出できます) を考慮して, 行列を書き換えます.

$ \begin{eqnarray} W^{m}_{N}=W^{m(mod N)}_{N} \end{eqnarray} $

例えば, $W^{8}_{8}=W^{0}_{8}$, $W^{9}_{8}=W^{1}_{8}$, $W^{10}_{8}=W^{2}_{8}$ …

$ \begin{eqnarray} X(k)=\left[ \begin{array}{cccccccc} W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} \\
W^{0}_{8} & W^{1}_{8} & W^{2}_{8} & W^{3}_{8} & W^{4}_{8} & W^{5}_{8} & W^{6}_{8} & W^{7}_{8} \\
W^{0}_{8} & W^{2}_{8} & W^{4}_{8} & W^{6}_{8} & W^{0}_{8} & W^{2}_{8} & W^{4}_{8} & W^{6}_{8} \\
W^{0}_{8} & W^{3}_{8} & W^{6}_{8} & W^{9}_{8} & W^{4}_{8} & W^{7}_{8} & W^{10}_{8} & W^{13}_{8} \\
W^{0}_{8} & W^{4}_{8} & W^{8}_{8} & W^{12}_{8} & W^{0}_{8} & W^{4}_{8} & W^{8}_{8} & W^{12}_{8} \\
W^{0}_{8} & W^{5}_{8} & W^{10}_{8} & W^{15}_{8} & W^{4}_{8} & W^{9}_{8} & W^{14}_{8} & W^{19}_{8} \\
W^{0}_{8} & W^{6}_{8} & W^{12}_{8} & W^{18}_{8} & W^{0}_{8} & W^{6}_{8} & W^{12}_{8} & W^{18}_{8} \\
W^{0}_{8} & W^{7}_{8} & W^{14}_{8} & W^{21}_{8} & W^{4}_{8} & W^{11}_{8} & W^{18}_{8} & W^{25}_{8} \\
\end{array} \right]x(n) \end{eqnarray} $

そして, 行列の行を偶奇にわけて, 並び替えます.

$ \begin{eqnarray} X(k)=\left[ \begin{array}{c} X(0) \\
X(4) \\
X(2) \\
X(6) \\
X(1) \\
X(5) \\
X(3) \\
X(7) \\
\end{array} \right] \end{eqnarray} $

$ \begin{eqnarray} X(k)=\left[ \begin{array}{cccccccc} W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} \\
W^{0}_{8} & W^{4}_{8} & W^{8}_{8} & W^{12}_{8} & W^{0}_{8} & W^{4}_{8} & W^{8}_{8} & W^{12}_{8} \\
W^{0}_{8} & W^{2}_{8} & W^{4}_{8} & W^{6}_{8} & W^{0}_{8} & W^{2}_{8} & W^{4}_{8} & W^{6}_{8} \\
W^{0}_{8} & W^{6}_{8} & W^{12}_{8} & W^{18}_{8} & W^{0}_{8} & W^{6}_{8} & W^{12}_{8} & W^{18}_{8} \\
W^{0}_{8} & W^{1}_{8} & W^{2}_{8} & W^{3}_{8} & W^{4}_{8} & W^{5}_{8} & W^{6}_{8} & W^{7}_{8} \\
W^{0}_{8} & W^{5}_{8} & W^{10}_{8} & W^{15}_{8} & W^{4}_{8} & W^{9}_{8} & W^{14}_{8} & W^{19}_{8} \\
W^{0}_{8} & W^{3}_{8} & W^{6}_{8} & W^{9}_{8} & W^{4}_{8} & W^{7}_{8} & W^{10}_{8} & W^{13}_{8} \\
W^{0}_{8} & W^{7}_{8} & W^{14}_{8} & W^{21}_{8} & W^{4}_{8} & W^{11}_{8} & W^{18}_{8} & W^{25}_{8} \\
\end{array} \right]x(n) \end{eqnarray} $

すると, 行列の列の中央を境目に, 偶数のインデックスの行は左右の周期が対称に, 奇数のインデックスの行は半周期 ($N=8$ なので 4 ずつずれている) ことがわかります.

そこで, 以下の関係を考慮します.

$ \begin{eqnarray} \begin{cases} W^{0}_{8}=1 \\
W^{4}_{8}=-1 \\
\end{cases} \end{eqnarray} $

$ \begin{eqnarray} X(k)=\left[ \begin{array}{rrrrrrrr} W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} \\
W^{0}_{8} & W^{4}_{8} & W^{8}_{8} & W^{12}_{8} & W^{0}_{8} & W^{4}_{8} & W^{8}_{8} & W^{12}_{8} \\
W^{0}_{8} & W^{2}_{8} & W^{4}_{8} & W^{6}_{8} & W^{0}_{8} & W^{2}_{8} & W^{4}_{8} & W^{6}_{8} \\
W^{0}_{8} & W^{6}_{8} & W^{12}_{8} & W^{18}_{8} & W^{0}_{8} & W^{6}_{8} & W^{12}_{8} & W^{18}_{8} \\
W^{0}_{8} & W^{1}_{8} & W^{2}_{8} & W^{3}_{8} & -W^{0}_{8} & -W^{1}_{8} & -W^{2}_{8} & -W^{3}_{8} \\
W^{0}_{8} & W^{5}_{8} & W^{10}_{8} & W^{15}_{8} & -W^{0}_{8} & -W^{5}_{8} & -W^{10}_{8} & -W^{15}_{8} \\
W^{0}_{8} & W^{3}_{8} & W^{6}_{8} & W^{9}_{8} & -W^{0}_{8} & -W^{3}_{8} & -W^{6}_{8} & -W^{9}_{8} \\
W^{0}_{8} & W^{7}_{8} & W^{14}_{8} & W^{21}_{8} & -W^{0}_{8} & -W^{7}_{8} & -W^{14}_{8} & -W^{21}_{8} \\
\end{array} \right]x(n) \end{eqnarray} $

そして,

$ \begin{eqnarray} W^{a}W^{b}=W^{a+b} \end{eqnarray} $

であるので,

$ \begin{eqnarray} X(k)=\left[ \begin{array}{rrrrrrrr} W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} \\
W^{0}_{8} & W^{4}_{8} & W^{8}_{8} & W^{12}_{8} & W^{0}_{8} & W^{4}_{8} & W^{8}_{8} & W^{12}_{8} \\
W^{0}_{8} & W^{2}_{8} & W^{4}_{8} & W^{6}_{8} & W^{0}_{8} & W^{2}_{8} & W^{4}_{8} & W^{6}_{8} \\
W^{0}_{8} & W^{6}_{8} & W^{12}_{8} & W^{18}_{8} & W^{0}_{8} & W^{6}_{8} & W^{12}_{8} & W^{18}_{8} \\
W^{0}_{8} & W^{1}_{8} & W^{2}_{8} & W^{3}_{8} & -W^{0}_{8}W^{0}_{8} & -W^{1}_{8}W^{0}_{8} & -W^{2}_{8}W^{0}_{8} & -W^{3}_{8}W^{0}_{8} \\
W^{0}_{8} & W^{5}_{8} & W^{10}_{8} & W^{15}_{8} & -W^{0}_{8}W^{0}_{8} & -W^{1}_{8}W^{4}_{8} & -W^{2}_{8}W^{8}_{8} & -W^{3}_{8}W^{12}_{8} \\
W^{0}_{8} & W^{3}_{8} & W^{6}_{8} & W^{9}_{8} & -W^{0}_{8}W^{0}_{8} & -W^{1}_{8}W^{2}_{8} & -W^{2}_{8}W^{4}_{8} & -W^{3}_{8}W^{6}_{8} \\
W^{0}_{8} & W^{7}_{8} & W^{14}_{8} & W^{21}_{8} & -W^{0}_{8}W^{0}_{8} & -W^{1}_{8}W^{6}_{8} & -W^{2}_{8}W^{12}_{8} & -W^{3}_{8}W^{18}_{8} \\
\end{array} \right]x(n) \end{eqnarray} $

時間ドメインの関数を以下のように置き換えて, 行列をさらに書き換えます.

$ \begin{eqnarray} x_{1}(n)=\left[ \begin{array}{l} x(0)+x(4) \\
x(1)+x(5) \\
x(2)+x(6) \\
x(3)+x(7) \\
W^{0}_{8}(x(0)-x(4)) \\
W^{1}_{8}(x(1)-x(5)) \\
W^{2}_{8}(x(2)-x(6)) \\
W^{3}_{8}(x(3)-x(7)) \\
\end{array} \right] \end{eqnarray} $

$ \begin{eqnarray} X(k)=\left[ \begin{array}{rrrrrrrr} W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & 0 & 0 & 0 & 0 \\
W^{0}_{8} & W^{4}_{8} & W^{8}_{8} & W^{12}_{8} & 0 & 0 & 0 & 0 \\
W^{0}_{8} & W^{2}_{8} & W^{4}_{8} & W^{6}_{8} & 0 & 0 & 0 & 0 \\
W^{0}_{8} & W^{6}_{8} & W^{12}_{8} & W^{18}_{8} & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} \\
0 & 0 & 0 & 0 & W^{0}_{8} & W^{4}_{8} & W^{8}_{8} & W^{12}_{8} \\
0 & 0 & 0 & 0 & W^{0}_{8} & W^{2}_{8} & W^{4}_{8} & W^{6}_{8} \\
0 & 0 & 0 & 0 & W^{0}_{8} & W^{6}_{8} & W^{12}_{8} & W^{18}_{8} \\
\end{array} \right]x_{1}(n) \end{eqnarray} $

最後に, 以下の関係を考慮して, 行列を書き換えます.

$ \begin{eqnarray} W^{m}_{N}=W^{m/2}_{N/2} \end{eqnarray} $

$ \begin{eqnarray} X(k)=\left[ \begin{array}{rrrrrrrr} W^{0}_{4} & W^{0}_{4} & W^{0}_{4} & W^{0}_{4} & 0 & 0 & 0 & 0 \\
W^{0}_{4} & W^{2}_{4} & W^{4}_{4} & W^{6}_{4} & 0 & 0 & 0 & 0 \\
W^{0}_{4} & W^{1}_{4} & W^{2}_{4} & W^{3}_{4} & 0 & 0 & 0 & 0 \\
W^{0}_{4} & W^{3}_{4} & W^{6}_{4} & W^{9}_{4} & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & W^{0}_{4} & W^{0}_{4} & W^{0}_{4} & W^{0}_{4} \\
0 & 0 & 0 & 0 & W^{0}_{4} & W^{2}_{4} & W^{4}_{4} & W^{6}_{4} \\
0 & 0 & 0 & 0 & W^{0}_{4} & W^{1}_{4} & W^{2}_{4} & W^{3}_{4} \\
0 & 0 & 0 & 0 & W^{0}_{4} & W^{3}_{4} & W^{6}_{4} & W^{9}_{4} \\
\end{array} \right]x_{1}(n) \end{eqnarray} $

この行列は, 離散フーリエ変換のサイズを $N=4$ に減らして高速化できることを意味します.

さらに, この行列をみると, 再帰的な構造があることがわかるので, 同様の手順で行列を書き換えます.

$ \begin{eqnarray} X(k)=\left[ \begin{array}{rrrrrrrr} W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & 0 & 0 & 0 & 0 \\
W^{0}_{8} & W^{4}_{8} & W^{0}_{8} & W^{4}_{8} & 0 & 0 & 0 & 0 \\
W^{0}_{8} & W^{2}_{8} & -W^{0}_{8} & -W^{2}_{8} & 0 & 0 & 0 & 0 \\
W^{0}_{8} & W^{6}_{8} & -W^{0}_{8} & -W^{6}_{8} & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} & W^{0}_{8} \\
0 & 0 & 0 & 0 & W^{0}_{8} & W^{4}_{8} & W^{0}_{8} & W^{4}_{8} \\
0 & 0 & 0 & 0 & W^{0}_{8} & W^{2}_{8} & -W^{0}_{8} & -W^{2}_{8} \\
0 & 0 & 0 & 0 & W^{0}_{8} & W^{6}_{8} & -W^{0}_{8} & -W^{6}_{8} \\
\end{array} \right]x_{1}(n) \end{eqnarray} $

$ \begin{eqnarray} x_{2}(n)=\left[ \begin{array}{l} x_{1}(0)+x_{1}(2) \\
x_{1}(1)+x_{1}(3) \\
W^{0}_{8}(x_{1}(0)-x_{1}(2)) \\
W^{2}_{8}(x_{1}(1)-x_{1}(3)) \\
x_{1}(4)+x_{1}(6) \\
x_{1}(5)+x_{1}(7) \\
W^{0}_{8}(x_{1}(4)-x_{1}(6)) \\
W^{2}_{8}(x_{1}(5)-x_{1}(7)) \\
\end{array} \right] \end{eqnarray} $

$ \begin{eqnarray} X(k)=\left[ \begin{array}{rrrrrrrr} W^{0}_{8} & W^{0}_{8} & 0 & 0 & 0 & 0 & 0 & 0 \\
W^{0}_{8} & W^{4}_{8} & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & W^{0}_{8} & W^{0}_{8} & 0 & 0 & 0 & 0 \\
0 & 0 & W^{0}_{8} & W^{4}_{8} & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & W^{0}_{8} & W^{0}_{8} & 0 & 0 \\
0 & 0 & 0 & 0 & W^{0}_{8} & W^{4}_{8} & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & W^{0}_{8} & W^{0}_{8} \\
0 & 0 & 0 & 0 & 0 & 0 & W^{0}_{8} & W^{4}_{8} \\
\end{array} \right]x_{2}(n) \end{eqnarray} $

$W^{m}_{N}=W^{m/2}_{N/2}$ の関係があるので,

$ \begin{eqnarray} X(k)=\left[ \begin{array}{rrrrrrrr} W^{0}_{2} & W^{0}_{2} & 0 & 0 & 0 & 0 & 0 & 0 \\
W^{0}_{2} & W^{1}_{2} & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & W^{0}_{2} & W^{0}_{2} & 0 & 0 & 0 & 0 \\
0 & 0 & W^{0}_{2} & W^{1}_{2} & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & W^{0}_{2} & W^{0}_{2} & 0 & 0 \\
0 & 0 & 0 & 0 & W^{0}_{2} & W^{1}_{2} & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & W^{0}_{2} & W^{0}_{2} \\
0 & 0 & 0 & 0 & 0 & 0 & W^{0}_{2} & W^{1}_{2} \\
\end{array} \right]x_{3}(n) \end{eqnarray} $

$ \begin{eqnarray} x_{3}(n)=\left[ \begin{array}{l} x_{2}(0)+x_{2}(1) \\
x_{2}(0)+x_{2}(1) \\
x_{2}(2)+x_{2}(3) \\
x_{2}(2)+x_{2}(3) \\
x_{2}(4)+x_{2}(5) \\
x_{2}(4)+x_{2}(5) \\
x_{2}(6)+x_{2}(7) \\
x_{2}(6)+x_{2}(7) \\
\end{array} \right] \end{eqnarray} $

この行列は, 離散フーリエ変換のサイズを $N=2$ に減らして高速化できることを意味します.

ビットリバース

高速フーリエ変換のアルゴリズム導出のさいに, 行列の列を並び替えているので, $X(k)$ のインデックスを昇順に並び替える必要があります.

並び替えるまえと並び替えたあとのインデックスには, 以下の関係があります.

ビットリバース
$x(n)$ab$X(k)$
00000000
10011004
20100102
30111106
41000011
51011015
61100113
71111117

上記のテーブルより, 並び替えるまえのインデックスを 2 進数に変換し, そのビットをの並びを逆にして, 10 進数に変換したインデックスが並び替えたあとのインデックスということです. このアルゴリズムは, ビットリバースと呼ばれています.

計算量

行列の書き換え過程をダイアグラムにしたのが以下の図で, バタフライ計算と呼ばれています.

FFT (バタフライ計算)

離散フーリエ変換のサイズが $N$ の高速フーリエ変換は, $\log_{2}N$ 段で計算できます. このとき, 最後の段以外は $N/2$ 回の乗算と $N$ 回の加算, 最後の段は $N$ 回の加算となるので, 高速フーリエ変換のオーダーは, $N\log_{2}N$ となります. 離散フーリエ変換のオーダーが $N^{2}$ であることを考えると, $N$ が大きいほど, 高速フーリエ変換はより有効であると言えます.

実装

C++ で実装した, 高速フーリエ変換と逆高速フーリエ変換の関数です.

FFT

#include <vector>
#include <cmath>
#include <complex>

int pow2(int n) {
  if (n == 0) {
    return 1;
  }

  return 2 << (n - 1);
}

void FFT(std::vector<std::complex<double>> &x, int N) {
  std::vector<int> index(N);

  int number_of_stages = std::log2(N);

  for (int stage = 1; stage <= number_of_stages; stage++) {
    for (int i = 0; i < pow2(stage - 1); i++) {
      int rest = number_of_stages - stage;

      for (int j = 0; j < pow2(rest); j++) {
        int n = i * pow2(rest + 1) + j;
        int m = pow2(rest) + n;
        int r = j * pow2(stage - 1);

        double a_real = x[n].real();
        double a_imag = x[n].imag();
        double b_real = x[m].real();
        double b_imag = x[m].imag();
        double c_real = std::cos((2.0 * M_PI * r) / N);
        double c_imag = -std::sin((2.0 * M_PI * r) / N);

        if (stage < number_of_stages) {
          x[n] = std::complex<double>((a_real + b_real), (a_imag + b_imag));
          x[m] = std::complex<double>((c_real * (a_real - b_real)) - (c_imag * (a_imag - b_imag)), (c_real * (a_imag - b_imag)) + (c_imag * (a_real - b_real)));
        } else {
          x[n] = std::complex<double>((a_real + b_real), (a_imag + b_imag));
          x[m] = std::complex<double>((a_real - b_real), (a_imag - b_imag));
        }
      }
    }
  }

  for (int stage = 1; stage <= number_of_stages; stage++) {
    int rest = number_of_stages - stage;

    for (int i = 0; i < pow2(stage - 1); i++) {
      index[pow2(stage - 1) + i] = index[i] + pow2(rest);
    }
  }

  for (int k = 0; k < N; k++) {
    if (index[k] <= k) {
      continue;
    }

    auto tmp    = x[index[k]];
    x[index[k]] = x[k];
    x[k]        = tmp;
  }
}

IFFT

#include <vector>
#include <cmath>
#include <complex>

int pow2(int n) {
  if (n == 0) {
    return 1;
  }

  return 2 << (n - 1);
}

void IFFT(std::vector<std::complex<double>> &x, int N) {
  std::vector<int> index(N);

  int number_of_stages = std::log2(N);

  for (int stage = 1; stage <= number_of_stages; stage++) {
    for (int i = 0; i < pow2(stage - 1); i++) {
      int rest = number_of_stages - stage;

      for (int j = 0; j < pow2(rest); j++) {
        int n = i * pow2(rest + 1) + j;
        int m = pow2(rest) + n;
        int r = j * pow2(stage - 1);

        double a_real = x[n].real();
        double a_imag = x[n].imag();
        double b_real = x[m].real();
        double b_imag = x[m].imag();
        double c_real = std::cos((2.0 * M_PI * r) / N);
        double c_imag = std::sin((2.0 * M_PI * r) / N);

        if (stage < number_of_stages) {
          x[n] = std::complex<double>((a_real + b_real), (a_imag + b_imag));
          x[m] = std::complex<double>((c_real * (a_real - b_real)) - (c_imag * (a_imag - b_imag)), (c_real * (a_imag - b_imag)) + (c_imag * (a_real - b_real)));
        } else {
          x[n] = std::complex<double>((a_real + b_real), (a_imag + b_imag));
          x[m] = std::complex<double>((a_real - b_real), (a_imag - b_imag));
        }
      }
    }
  }

  for (int stage = 1; stage <= number_of_stages; stage++) {
    int rest = number_of_stages - stage;

    for (int i = 0; i < pow2(stage - 1); i++) {
      index[pow2(stage - 1) + i] = index[i] + pow2(rest);
    }
  }

  for (int k = 0; k < N; k++) {
    if (index[k] <= k) {
      continue;
    }

    auto tmp    = x[index[k]];
    x[index[k]] = x[k];
    x[k]        = tmp;
  }

  for (int k = 0; k < N; k++) {
    x[k] = std::complex<double>((x[k].real() / N), (x[k].imag() / N));
  }
}

リファレンス

Share Comments
comments powered by Disqus