高速フーリエ変換
以下は、高速フーリエ変換のプログラムを Q = 4 の場合にMicrosoft Visual Basicの文法を用いて書いた例である。
この例では、最深部 (For k、Next k の間の部分)の繰り返し回数が Ndeg log4 Ndeg となっている。
高速フーリエ変換(こうそくフーリエへんかん、英: fast Fourier transform, FFT)は、離散フーリエ変換(英: discrete Fourier transform, DFT)を計算機上で高速に計算するアルゴリズムである。高速フーリエ変換の逆変換を逆高速フーリエ変換(英: inverse fast Fourier transform, IFFT)と呼ぶ。