title: Fast Fourier Transform
body: <p>I need to multiply two polynomials each having small integral coefficients. I need a fast FFT routine in C/C++ which can convolve them. I have seen several libraries but they seem to be too large spread over multiple files. What is important is I need code which is not too long and can be very easily used and compiled in a single <code>.c/.cpp</code> file. </p>
  
  <ol>
  <li>FFT should be optimized for real inputs at least if not small integers.</li>
  <li>Radix 4 implementation if available would be fine too. </li>
  <li>Compiling it should take no special compilation flags as compilation of program has to be done in external environment which I can't control.</li>
  </ol>
  
  <p>One that very well matches my needs is <a href="http://www.koders.com/c/fid08FC2E44FE8165B7A590D69FF6B72D31634D426A.aspx" rel="noreferrer">here</a>. But I need something twice as fast.</p>