%This demo illustrates the Divide and Conquer approach
%to computing an N pt DFT when N=ML, where M and L are
%integers.   The N pt DFT is decomposed into L  M-pt DFT's,
%followed by N multiplications (done in the same for loop),
%followed by M  L-pt DFT's as per Sect. 6.1 in the Text
clear all
N=15; M=5; L=3;
%Here's where me make up the signal
x=randn(1,N);
temp=flops;
for l=1:L,
X(l,:)=exp(-j*(l-1)*2*pi*(0:M-1)/N).*fft(x(1,l:L:N),M);
end
for p=1:M,
XT(:,p)=fft(X(:,p),L);
end
CompF=flops-temp;
XT=XT.';   XN=XT(:).';
%Here's the N pt DFT computed directly (but note
%Matlab generally does this as efficiently as possible)
Xfft=fft(x,N);
%Look at difference to make sure they are the same
XN-Xfft
%Let's now do Direct Computation of N-pt DFT to
%compare the number of floating point operations (FLOPS)
temp=flops;
for k=1:N,
XD(1,k)=exp(-j*(k-1)*2*pi*(0:N-1)/N)*x.';
end
CompD=flops-temp;
%Here's the ratio of the computations needed
CompF/CompD