title: Looking for help about a FFT template
body: <p>I am currently working on a problem that requires FFT for convolution, however when I brought in my FFT template from my archive I realize that there's something wrong with the output.</p>
  <p>eg:</p>
  <blockquote>
  <p>Input: (0, 0) (0, 0) (4166667, 0) (1, 0)</p>
  <p>Correct output: (4166668, 0) (-4166667, 1) (4166666, 0) (-4166667, -1)</p>
  <p>Template output: (4166668, 0) (-4166667, <strong>-1</strong>) (4166666, 0) (-4166667, <strong>1</strong>)</p>
  </blockquote>
  <p>The code:</p>
  <pre><code>#define MAXN 
  #define ld long double
  #define op operator
  
  struct base {
     typedef ld T; T re, im;
     base() :re(0), im(0) {}
     base(T re) :re(re), im(0) {}
     base(T re, T im) :re(re), im(im) {}
     base op + (const base&amp; o) const { return base(re + o.re, im + o.im); }
     base op - (const base&amp; o) const { return base(re - o.re, im - o.im); }
     base op * (const base&amp; o) const { return base(re * o.re - im * o.im, re * o.im + im * o.re); }
     base op * (ld k) const { return base(re * k, im * k); }
     base conj() const { return base(re, -im); }
  };
  
  base w[MAXN]; //omega lookup table
  int rev[MAXN]; //reverse lookup table
  
  void build_rev(int k) {
     static int rk = -1;
     if( k == rk )return ; rk = k;
     for(int i = 1; i &lt; (1&lt;&lt;k); i++) {
         int j = rev[i-1], t = k-1;
         while( t &gt;= 0 &amp;&amp; ((j&gt;&gt;t)&amp;1) ) { j ^= 1 &lt;&lt; t; --t; }
         if( t &gt;= 0 ) { j ^= 1 &lt;&lt; t; --t; }
         rev[i] = j;
     }
  }
  
  void fft(base *a, int k) {
     build_rev(k); int n = 1 &lt;&lt; k;
     for(int i = 0; i &lt; n; i++) if( rev[i] &gt; i ) swap(a[i], a[rev[i]]);
     for(int l = 2, lll = 1; l &lt;= n; l += l, lll += lll) {
         if( w[lll].re == 0 &amp;&amp; w[lll].im == 0 ) {
             ld angle = PI / lll;
             base ww( cosl(angle), sinl(angle) );
             if( lll &gt; 1 ) for(int j = 0; j &lt; lll; ++j) {
                 if( j &amp; 1 ) w[lll + j] = w[(lll+j)/2] * ww;
                 else w[lll + j] = w[(lll+j)/2];
             } else w[lll] = base(1, 0);
         }
         for(int i = 0; i &lt; n; i += l) 
           for(int j = 0; j &lt; lll; j++){
             base v = a[i + j], u = a[i + j + lll] * w[lll + j];
             a[i + j] = v + u; a[i + j + lll] = v - u;
              }
     }
  }
  
  //ideone compiled example: http://ideone.com/8PTjW5
  </code></pre>
  <p>I tried to check the bit reverse and the root of unity table yet I didn't find any problems in those two parts. I also checked some online materials to verify the steps but there's nothing odd looking to me.</p>
  <p>Would someone mind help me to find out what's the problem in this template?</p>
  <p>Thanks in advance.</p>
  <p>Edit: I decided to rely on another template at the end, thanks for all the reply from everyone.</p>