Python implementation of http://members3.jcom.home.ne.jp/zakii/fourie/32_implement_software.htm

fft.py

import cmath

def fft(data):
    data = data[:] # copy data to avoid side effect
    N = len(data)

    w = calc_coefficients(N)
    reorder_data(data)

    a = 1
    b = N / 2;
    while a < N:
        for k in xrange(a):
            for n in xrange(k, N, 2 * a):
                tmp = data[n + a] * w[b * k];
                data[n + a], data[n] = data[n] - tmp, data[n] + tmp

        a *= 2
        b /= 2

    return data


def calc_coefficients(N):
    # calc N coefficients
    return [cmath.exp(-2 * cmath.pi * 1j * n / N) for n in xrange(N)]


def calc_bitrev(N):
    # calc order of bit-reverses for N points data
    bitrev = [0] * N

    a = 1
    b = N / 2;
    while a < N:
        for k in xrange(a):
            bitrev[k + a] = bitrev[k] + b

        a *= 2
        b /= 2

    return bitrev


def reorder_data(data):
    # reorder data following bitrev
    
    N = len(data)
    bitrev = calc_bitrev(N)
    for n in xrange(N):
        if n < bitrev[n]:
            data[n], data[bitrev[n]] = data[bitrev[n]], data[n]


if __name__ == '__main__':
    data = [ cmath.sin(cmath.pi * 2 * x / 16.0) + 2 * cmath.sin(cmath.pi * 2 * x / 8.0) + 1 for x in xrange(16) ]
    for x in fft(data):
        print abs(x)