% DFT versus FFT
% DRB 2-Dec-2010
% for ECE4703

j = sqrt(-1);
N_test = 2.^[5:14];                % DFT/FFT lengths
results_clock = zeros(2,length(N_test));  % clocktime results

i1 = 0;
for N = N_test,
    i1 = i1+1;
    
    x = randn(1,N)+j*randn(1,N);        % random input
    WN = exp(-j*2*pi/N);                % twiddle factor
    W = WN.^[0:N-1];
    
    tic
    X1 = dft(x,W);
    results_clock(1,i1) = toc;
    
    tic
    X2 = fft(x);
    results_clock(2,i1) = toc;
    
end

% confirm FFT and DFT are giving the same result
max(abs(X1-X2))

semilogy(log2(N_test),results_clock(1,:),'b',log2(N_test),(N_test.^2)/5e6,'b--',log2(N_test),results_clock(2,:),'r',log2(N_test),N_test.*log2(N_test)/2E8,'r--');
xlabel('DFT/FFT size (log2(N))');
ylabel('clock time (seconds)');
grid on
legend('DFT','c1*N^2','FFT','c2*NlogN','Location','NorthWest');

