快速傅里叶算法模板
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了快速傅里叶算法模板,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2487字,纯文字阅读大概需要4分钟。
内容图文
![快速傅里叶算法模板](/upload/InfoBanner/zyjiaocheng/1132/8fe0f44e877b42ec9d66221d2469823c.jpg)
1 /* 2 algorithm : High-Precision FFT 3 4 */ 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 #include <algorithm> 9#define N 200005 10#define pi acos(-1.0) // PI值 11usingnamespace std; 12struct complex 13{ 14double r,i; 15 complex(double real=0.0,double image=0.0){ 16 r=real; i=image; 17 } 18// 以下为三种虚数运算的定义 19 complex operator + (const complex o){ 20return complex(r+o.r,i+o.i); 21 } 22 complex operator - (const complex o){ 23return complex(r-o.r,i-o.i); 24 } 25 complex operator * (const complex o){ 26return complex(r*o.r-i*o.i,r*o.i+i*o.r); 27 } 28}x1[N],x2[N]; 29char a[N/2],b[N/2]; 30int sum[N]; // 结果存在sum里 31void brc(complex *y,int l) // 二进制平摊反转置换 O(logn) 32{ 33 register int i,j,k; 34for(i=1,j=l/2;i<l-1;i++) 35 { 36if(i<j) swap(y[i],y[j]); // 交换互为下标反转的元素 37// i<j保证只交换一次 38 k=l/2; 39while(j>=k) // 由最高位检索,遇1变0,遇0变1,跳出 40 { 41 j-=k; 42 k/=2; 43 } 44if(j<k) j+=k; 45 } 46} 47void fft(complex *y,int l,double on) // FFT O(nlogn) 48// 其中on==1时为DFT,on==-1为IDFT 49{ 50 register int h,i,j,k; 51 complex u,t; 52 brc(y,l); // 调用反转置换 53for(h=2;h<=l;h<<=1) // 控制层数 54 { 55// 初始化单位复根 56 complex wn(cos(on*2*pi/h),sin(on*2*pi/h)); 57for(j=0;j<l;j+=h) // 控制起始下标 58 { 59 complex w(1,0); // 初始化螺旋因子 60for(k=j;k<j+h/2;k++) // 配对 61 { 62 u=y[k]; 63 t=w*y[k+h/2]; 64 y[k]=u+t; 65 y[k+h/2]=u-t; 66 w=w*wn; // 更新螺旋因子 67 } // 据说上面的操作叫蝴蝶操作… 68 } 69 } 70if(on==-1) for(i=0;i<l;i++) y[i].r/=l; // IDFT 71} 72int main(void){ 73int l1,l2,l; 74 register int i; 75while(scanf("%s%s",a,b)!=EOF){ 76 l1 = strlen(a),l2 = strlen(b); 77 l = 1; while(l < l1 * 2 || l < l2 * 2) l <<= 1; // 将次数界变成2^n 配合二分与反转置换 78for(i = 0 ; i < l1 ; i++){ // 倒置存入 79 x1[i].r = a[l1 - i - 1] - ‘0‘; 80 x1[i].i = 0.0; 81 } 82for( ; i < l ; i++) x1[i].r = x1[i].i = 0.0; 83// 将多余次数界初始化为0 84for(i = 0 ; i < l2 ; i++){ // same 85 x2[i].r = b[l2 - i - 1] - ‘0‘; 86 x2[i].i = 0.0; 87 } 88for( ; i < l ; i++) x2[i].r = x2[i].i = 0.0; 89 fft(x1,l,1); // DFT(a) 90 fft(x2,l,1); // DFT(b) 91for(i = 0 ; i < l ; i++) x1[i] = x1[i] * x2[i]; // 点乘结果存入a 92 fft(x1,l,-1); // IDFT(a*b) 93for(i = 0 ; i < l ; i++) sum[i] = x1[i].r + 0.5; // 四舍五入 94for(i = 0 ; i < l ; i++){ // 进位 95 sum[i + 1] += sum[i] / 10; 96 sum[i] %= 10; 97 } 98 l = l1 + l2 - 1; 99while(sum[l] <= 0 && l > 0) l--; // 检索最高位100for(i = l ; i >= 0 ; i--) putchar(sum[i] + ‘0‘); // 倒序输出101 putchar(‘\n‘); 102 } 103return0; 104 }
原文:http://www.cnblogs.com/cyb123456/p/5918062.html
内容总结
以上是互联网集市为您收集整理的快速傅里叶算法模板全部内容,希望文章能够帮你解决快速傅里叶算法模板所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。