在java算法（Scott robert ladd）中看到快速傅立葉變換，講的很詳細(xì)，摘錄下來跟大家分享！
以下正文：
FFT或許是已知的最有效的算法，他應(yīng)用范圍廣。從信號(hào)的處理到數(shù)據(jù)壓縮到地震分析和圖形放大，F(xiàn)FT通過領(lǐng)域間的信息轉(zhuǎn)換
提供了一個(gè)強(qiáng)有力的工具，本節(jié)講討論FFT如何改進(jìn)多項(xiàng)式乘法的性能：
 到目前為止，我用系數(shù)形式表示多項(xiàng)式，但有些應(yīng)用程序最適合用point-value形式表示多項(xiàng)式，任何多項(xiàng)式都可被n個(gè)點(diǎn)值
 對(duì)來表示，這里，value是多項(xiàng)式在給定點(diǎn)point的值，許多數(shù)學(xué)應(yīng)用要使用FFT實(shí)現(xiàn)點(diǎn)值和系數(shù)之間的快速變換。
    兩個(gè)多項(xiàng)式A和B快速相乘的過程如下：
 1，用同一組值把A和B從十形式轉(zhuǎn)換為點(diǎn)值形式pA和pB。
 2。pA和pB對(duì)應(yīng)的點(diǎn)值相乘，得到pC。
 3。對(duì)pC進(jìn)行插值得到系數(shù)多項(xiàng)式C，他等于A乘上B。
表面上看，上述算法比在mul中使用之際相乘并不高效－－卻更復(fù)雜，選擇合適的計(jì)算值可以使點(diǎn)－值乘法非常快。

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

//待續(xù)