  function P2()
  % Checks Twiddle
  
  % -1 if w a row vector
  % -1 if efficiency worse by a factor of more than 10
  % -2 if efficiency worse by a factor of more than 100
  
  clc
  % Check Accuracy...
  n = 2^10;
  wCVL = CVLTwiddle(n);
  wYou = Twiddle(n);
  w0 = ExactTwiddle(n);
  errCVL = norm(w0-wCVL)
  errYou = norm(w0-wYou)
  
  % Check Efficiency
  n = 2^21;
  tic
  wCVL = CVLTwiddle(n);
  tCVL = toc;
  n = 2^21;
  tic
  wYou = Twiddle(n);
  tYou = toc;
  tYouDIVtCVL = tYou/tCVL
  
  



  function w = CVLTwiddle(n)
% n is a positive power of 2.
% w is a column (n/2)-vector whose k-th component is omega^(k-1) where
%                        omega = exp(-2*pi*(k-1)/n).

  w = zeros(n/2,1);
  w(1) = 1;
  t = log2(n);
  omega = exp(-2*pi*sqrt(-1)/n);
  for m = 2.^(0:t-2)
      % w(1:m) is available.
      % Use the fact that w(m+1:2*m) = (omega_{n}^m)*w(1:m)
      
      w(m+1:2*m) = omega*w(1:m);
      omega = omega*omega;
  end
  
  % Note: for large n, omega_n is VERY close to 1. Bad numerical stuff
  % happens when this is repeatedly squared as the 10^-11 error shows.
  % If the w-update has the form
  %    w(m+1:2*m) = exp(-2*m*pi*sqrt(-1)/n)*w(1:m);
  % then CVLTwiddle  rivals ExactTwiddle in accuracy and only involve 
  % O(log n) calls to exp.
  
  
  function w = ExactTwiddle(n)
% w is a column (n/2)-vector whose k-th component is omega^(k-1) where
%                        omega = exp(-2*pi*(k-1)/n).
% This computes a w vector that is as accurate as possible
  w = zeros(n/2,1);
  for k=1:n/2
      w(k) = exp(-2*(k-1)*sqrt(-1)*pi/n);
  end
  
       
  
  