Advanced Exercism • julia

FFT

Challenge Overview

Write a Fast Fourier Transform algorithm using complex numbers

Instructions

Your friend is a sound engineer who has asked you to help them code up a Fourier Transform for some proprietary software they are putting together. Since you want to get this right, you will first implement the Discrete Fourier Transform (DFT) in all its naive glory. This could then be used to test the correctness of your final objective, the Fast Fourier Transform (FFT).

1. DFT

Implement the DFT.

Note, that this is of O(n²) complexity because you get one k for a run through all n, and you’ll want a Xₖ vector that is the same length as the signal Xₙ vector (for invertibility), so n times through n points is O(n²).

2. FFT

Implement the FFT.

There are a lot of resources to find more detail on the particulars of this algorithm, so feel free to do some research.

Community Solutions

View Community Solutions

The following are the top 3 community solutions by stars:

Solution 1 by @a-lipin (⭐ 1) — View on Exercism
Solution 2 by @Itezos (⭐ 0) — View on Exercism
Solution 3 by @utullyca (⭐ 0) — View on Exercism

Source: Exercism julia/fft

💡 View Solution

function dft(x)
    N = length(x)
    [sum([el * cispi(-2(n-1)*(k-1)/N)  for (n, el) in enumerate(x)]) for k ∈ eachindex(x)]
end

function fft(x)
    N   = length(x)
    Ek  = dft([el for (k, el) ∈ enumerate(x) if !iseven(k)])
    Ok  = dft([el for (k, el) ∈ enumerate(x) if iseven(k)])
    mul = [cispi(-2(k-1)/N) for k in 1:N/2]