function y = FFT23(x)
%
% perform FFT
% written by Ming Gu for Math 128B, Spring 2009
% it performs fast computation when the dimension of x 
% contains a factor of 2 or 3; otherwise it does direct
% matrix vector computation.
%
n = size(x,1);
if (n==1)
    y = x;
    return;
end
if (n==2)
    y = [x(1,:)+x(2,:);x(1,:)-x(2,:)];
    return;
end 
Fn= factor(n);
if (Fn(1)>3)
    A = exp(2*pi*sqrt(-1)/n*((0:n-1)'*(0:n-1)));
    y = A * x;
    return;
end
P = Fn(1);
m = n/P;
z = zeros(n,size(x,2));
for k=1:P
  z((k-1)*m+1:k*m,:)   = FFT23(x(P*(0:m-1)+k,:));
end
y = zeros(n,size(x,2));
for q = 1:P
  for t = 1:P
     w = repmat(exp((2*pi*sqrt(-1)/n*(t-1))*((q-1)*m+(0:m-1)')),1,size(y,2));
     y((q-1)*m+1:q*m,:) = y((q-1)*m+1:q*m,:) + w.* z((t-1)*m+1:t*m,:);
  end
end