我的人生路  
日历
<2006年2月>
2930311234
567891011
12131415161718
19202122232425
2627281234
567891011
统计
  • 随笔 - 74
  • 文章 - 57
  • 评论 - 7
  • 引用 - 0

导航

常用链接

留言簿(5)

随笔分类

随笔档案

文章分类

文章档案

相册

颜色

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 

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

//待续



欢迎大家访问我的个人网站 萌萌的IT人
posted on 2006-02-16 10:16 一天一点爱恋 阅读(946) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航:
 
 
Copyright © 一天一点爱恋 Powered by: 博客园 模板提供:沪江博客