在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));
 }
}

//待續