在java算法（Scott robert ladd）中看到快速傅立叶变换，讲的很详细，摘录下来跟大家分享！
以下正文：
FFT或许是已知的最有效的算法，他应用范围广。从信号的处理到数据压缩到地震分析和图形放大，FFT通过领域间的信息转换
提供了一个强有力的工具，本节讲讨论FFT如何改进多项式乘法的性能：
 到目前为止，我用系数形式表示多项式，但有些应用程序最适合用point-value形式表示多项式，任何多项式都可被n个点值
 对来表示，这里，value是多项式在给定点point的值，许多数学应用要使用FFT实现点值和系数之间的快速变换。
    两个多项式A和B快速相乘的过程如下：
 1，用同一组值把A和B从十形式转换为点值形式pA和pB。
 2。pA和pB对应的点值相乘，得到pC。
 3。对pC进行插值得到系数多项式C，他等于A乘上B。
表面上看，上述算法比在mul中使用之际相乘并不高效－－却更复杂，选择合适的计算值可以使点－值乘法非常快。

public class PolynomialFFTextends polynomial
{
 //utility field
 final protected static Complex p|2|=new Complex(0.0D,6.283185307179586D);

 //utility methods
 protected static int log2(int n)
 {
  int x=1;
  int c=0;
  while(true)
  {
   if (x>=n) break;
   ++c;
   x<<=1;
   if (x==0) break;
   
  }
  return c;
 }
 protected static int FlipBits(int k,int bits)
 {
  int lm=1<<(bits-1);
  int rm=1;
  int r=0;
  while (lm != 0)
  {
   if ((k&rm)!=0)
   {
    r|=lm;
    lm>>=1;
    rm<<=1;
   }
  }
  return r;
 }
};

//increase degree to power of two
protected static PolynomialFFT stretchFFT(PolynomialFFT p)
{
 int n=1;
 int d=p.m_nDegree;
 while(true)
 {
  if (d<=n) break;
  n<<=1;
  if (n==0)
  {
   throw new ArithmeticException("StretchFFT failed");
  }
  n<<=1;
  return new PolynomialFFT(p.stretch(n));
 }
}

//待续