Can someone convert this pseudocode to MATLAB code?

Algorithm FFT(a, omega)

Input: An n-length coefficient vector a = [a_0,a_1,...,a_(n-1)]

and a primitive nth root of unity omega (n = a power of 2)

Output: A vector y of values of the polynomial for a at the nth roots of unity.

if n=1 then

return y = a.

end

// divide step

a_even = [a_0,a_2,a_4,...,a_(n-2)]

a_odd = [a_1,a_3,a_5,...,a_(n-1)]

// recursive calls with omega^2 as n/2th root of unity

y_even = FFT(a_even, omega^2)

y_odd = FFT(a_odd, omega^2)

x = 1 // storing powers of omega

// combine step, using x = omega^i

for (i=0;i<n/2,i++)

y[i] = y_even[i]+x*y_odd[i]

y[i+n/2] = y_even[i]-x*y_odd[i] // because of reflective prop.

x = x*omega

end

return y

end

[Rik]

Yes, you can.

If you have trouble implementing it, have a read here and here before posting your next question. It will greatly improve your chances of getting an answer.

Answer 1

[Voss]

function y = myFFT(a, omega)
%     Input: An n-length coefficient vector a = [a_0,a_1,...,a_(n-1)] 
%     and a primitive nth root of unity omega (n = a power of 2) 
%     Output: A vector y of values of the polynomial for a at the nth roots of unity. 
    n = numel(a);
    if n == 1
        y = a;
        return
    end
% divide step 
%     a_even = [a_0,a_2,a_4,...,a_(n-2)] 
%     a_odd = [a_1,a_3,a_5,...,a_(n-1)] 
    a_even = a(1:2:end);
    a_odd = a(2:2:end);
% recursive calls with omega^2 as n/2th root of unity 
    y_even = myFFT(a_even, omega^2);
    y_odd = myFFT(a_odd, omega^2);
    x = 1; % storing powers of omega 
% combine step, using x = omega^i 
    for i = 1:n/2
        y(i) = y_even(i)+x*y_odd(i);
        y(i+n/2) = y_even(i)-x*y_odd(i); % because of reflective prop.
        x = x*omega;
    end
end