快速傅里叶变换(Fast Fourier Transform, FFT in short)
网上关于FFT的介绍很多,算导也有相关算法描述,但是原来读的时候很清楚,可是读完也不知道怎么实现.这次在机房膜拜了大神的代码后自己琢磨了一个初等数学描述的证明,并得到了一个比较简洁的实现方法.主要是For OIer,所以给出的证明是简洁而不失于严谨性的(融合了算导, 维基百科的证明和自己的理解).
离散卷积
对于两个多项式函数h(x)与g(x),[tex]h(x) = \sum_{i=0}^{n-1} a_i*x^i[/tex],[tex]g(x) = \sum_{i=0}^{n-1} b_i*x^i[/tex]定义离散卷积(以下均称卷积)[tex]f(x) = h(x) \otimes g(x) = \sum_{i = 0}^{2n-2} \sum_{j + k = i} a_j*b_k*x^i[/tex]
FFT解决的问题
两个多项式做卷积的时间复杂度是[tex]\mathcal{O}(n^2)[/tex].这里的FFT将提供一种在[tex]\mathcal{O}(n \log n)[/tex]时间内完成多项式乘法的方法.
DFT
将一个(n-1)次多项式f(x)看做系数组成的n维向量[tex]\mathbf{a} = (a_0,a_1,...,a_{n-1})[/tex],DFT是将这个向量[tex]\mathbf{a}[/tex],转化为一个新的复向量[tex]\tilde{\mathbf{a}}=(f(\omega_{n}^{0}),f(\omega_{n}^{1}),...,f(\omega_{n}^{n-1}))[/tex],这里的[tex]\omega_{n}[/tex]称作n次单位复根,定义为[tex]e^{i\frac{2\pi}{n}}[/tex].
我们怎样利用DFT
首先将两个函数的复向量求出,并进行点积,再利用[tex]{DFT}^{-1}[/tex],求出待求函数.
DFT的逆运算
下面我们证明DFT的逆运算,只需将DFT中的n次单位复根求一个相反数,其余同DFT即可.
（如果你是初学者，建议直接看下一节。下面是我自己的推导，叙述得比较混乱。建议学完算法后自己练习推导，也可从我这里获得些许灵感。）
我们讨论向量[tex]\mathbf{a}[/tex]的某一维[tex]a_k[/tex].注意到在复向量[tex]\tilde{\mathbf{a}}[/tex]中每一维均包含着[tex]a_k[/tex], 其中第j维包含[tex]a_k[/tex]那项为[tex]\omega_{n}^{j*k}a_k[/tex],做一个简单的变换就能发现,如果设[tex]\tilde{\mathbf{a}}[/tex]对应的多项式为l(x),则对于[tex]l(\omega_{n}^{-k})[/tex],所有[tex]a_k[/tex]被计算n次,这就相当于将[tex]a_k[/tex]提取出来.但是,我们还要考虑[tex]l(\omega_{n}^{-k})[/tex],对于[tex]a_l(l \ne k)[/tex]的影响.注意复向量[tex]\tilde{\mathbf{a}}[/tex],某一维j的[tex]a_l[/tex]成分为[tex]\omega_{n}^{j*l}a_l[/tex].故[tex]l(\omega_{n}^{-k})[/tex]对[tex]a_l[/tex]的影响为[tex]\sum_{i=0}^{n-1}\omega_{n}^{i*(l-k)}a_l[/tex],对于n次单位复根的幂,我们有[tex]\omega_{n}^{k}=\omega_{\frac{n}{(n,k)}}^{\frac{k}{(n,k)}}}[/tex],若将(l-k)与n的最大公因子消去,则对于每一个长度为[tex]\frac{n}{(n,k)}[/tex]的块,[tex]\omega_{n}[/tex]的指数将遍历这个块长度的剩余系,故此块内之和为零, 块数为整数,故[tex]l(\omega_{n}^{-k})[/tex]对[tex]a_l(l \ne k)[/tex]无影响,命题得证.
对DFT的简化运算
我们发现，如果直接按照公式[tex]\tilde{\mathbf{a}}=(f(\omega_{n}^{0}),f(\omega_{n}^{1}),...,f(\omega_{n}^{n-1}))[/tex]进行计算，计算出该复向量的复杂度仍然是[tex]\mathcal{O}(n^2)[/tex]的.事实上，求得这个复变量存在[tex]\mathcal{O}(n\log{n})[/tex]的方法。下面做一推导。
[tex]\begin{matrix}\tilde{\mathbf{a}}_k=\sum_{n=2t} \omega_{n}^{kn} x_n + \sum_{n=2t+1} \omega_{n}^{kn}x_n\\= \sum_{t} \omega_{\frac{n}{2}}^{kt}x_{2t} + \omega_{n}^{k}\sum_{t} \omega_{\frac{n}{2}}^{kt}x_{2t+1}\\= F_{even}(k) + \omega_{n}^{k}F_{odd}(k)&&&&&&(i\in\mathbb{Z})\end{matrix}[/tex]
这里的[tex]F(x)=f(\omega_{n}^{x})[/tex]
由上述推导，我们可以将复向量按奇数维和偶数维进行分治，再依据上述方法合并即可.利用n次单位复根的一个性质[tex]\omega_{n}^{k} = -\omega_{n}^{k+\frac{2}{n}}[/tex]可以很容易进行合并运算。
没有了？
没有了
上代码吧
#include<cstdio>
#include<cstring>
#include<complex>
#include<cmath>
#define maxn 1 << 20
using namespace std;
typedef complex<double> Comp;
const Comp I(0, 1);
Comp a[maxn], b[maxn], tmp[maxn];
int n;
void DFT(Comp *a, int n, int rev){
if(n == 1) return;
for(int i = 0;i<n;i++) tmp[i] = a[i];
for(int i = 0;i<n;i++) if(i & 1) a[i/2 + n/2] = tmp[i]; else a[i/2] = tmp[i];
Comp *a0 = a, *a1 = a + n/2;
DFT(a0, n/2, rev);
DFT(a1, n/2, rev);
Comp cur(1, 0);
double alpha = 2 * M_PI / n * rev;
Comp step = exp(I * alpha);
for(int i = 0;i<n/2;i++){
tmp[i] = a0[i] + cur * a1[i];
tmp[i + n/2] = a0[i] - cur * a1[i];
cur *= step;
}
for(int i = 0;i<n;i++) a[i] = tmp[i];
}
int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++) {
int t;
scanf("%d", &t);
a[i] = Comp(t, 0);
}
for(int i = 0;i<n;i++) {
int t;
scanf("%d", &t);
b[i] = Comp(t, 0);
}
DFT(a, 1 << 20, 1);
DFT(b, 1 << 20, 1);
for(int i = 0;i<(1 << 20);i++) a[i] *= b[i];
DFT(a, 1 << 20, -1);
for(int i = 0;i<(1 << 20);i++) {
a[i] /= (1 << 20);
}
for(int i = 0;i < (n << 1);i++) printf("%.3lf\n", a[i].real());
return 0;
}
2022年8月16日 20:27
Uttarakhand Board Model Paper 2023 Class 9 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams
2022年9月11日 16:59
Mathematics is one of the tough subjects and also an easy subject for class 10th standard students of TM, EM, AP 10th Maths Question Paper UM and HM studying at government and private schools of the state. Department of School Education and teaching staff of various institutions have designed and suggested the Mathematics question paper with solutions for all chapters topic wide for each lesson of the course, and the AP SSC Maths Model Paper 2023 Pdf designed based on the new revised syllabus and curriculum.
2024年1月02日 15:26
You truly make it look so normal with your presentation anyway I find this have an effect to be truly something which I figure I would never comprehend. It has all the earmarks of being unreasonably obfuscated and unbelievably wide for me. I'm looking forward for your next post, I'll endeavor to get its hang! This is such an extraordinary resource that you are giving and you part with it to no end. I love seeing site that fathom the value. Im glad to have found this post as it's anything but's a fascinating one! I'm by and large looking out for quality posts and articles so I accept im lucky to have found this! I believe you will add all the more later on.
2024年1月07日 14:28
Can I simply say what a reduction to search out someone who really is aware of what theyre talking about on the internet. You definitely know easy methods to carry a problem to mild and make it important. More people must read this and understand this aspect of the story. I cant believe youre no more popular because you definitely have the gift.
2024年1月07日 14:53
Today, I went to the beachfront with my kids. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is completely off topic but I had to tell someone!|
2024年1月07日 15:16
Good – I should certainly pronounce, impressed with your web site. I had no trouble navigating through all the tabs as well as related info ended up being truly simple to do to access. I recently found what I hoped for before you know it at all. Reasonably unusual. Is likely to appreciate it for those who add forums or anything, website theme . a tones way for your client to communicate. Nice task.
2024年1月07日 15:19
Greetings, I think your blog could be having internet browser compatibility issues. When I look at your website in Safari, it looks fine however, when opening in IE, it has some overlapping issues. I merely wanted to give you a quick heads up! Apart from that, great website!|
2024年1月07日 15:32
Does your blog have a contact page? I’m having a tough time locating it but, I’d like to shoot you an e-mail. I’ve got some ideas for your blog you might be interested in hearing. Either way, great blog and I look forward to seeing it grow over time.|
2024年1月07日 15:40
The vacation delivers on offer are : believed a selection of some of the most selected and additionally budget-friendly global. Any of these lodgings tend to be very used along units may accented by means of pretty shoreline supplying crystal-clear turbulent waters, concurrent with the Ocean. hotels packages
2024年1月07日 15:45
I’m impressed, I must say. Actually rarely do you encounter a blog that’s both educative and entertaining, and let me tell you, you’ve got hit the nail to the head. Your notion is outstanding; the issue is an issue that not enough people are speaking intelligently about. I am very happy that we found this at my look for something about it.
2024年1月07日 16:04
Today, I went to the beachfront with my kids. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is completely off topic but I had to tell someone!|
2024年1月07日 16:05
Just wish to say your article is as amazing. The clarity in your post is just nice and i could assume you are an expert on this subject. Fine with your permission allow me to grab your RSS feed to keep updated with forthcoming post. Thanks a million and please continue the rewarding work.|
2024年1月07日 16:12
We are a group of volunteers and starting a new scheme in our community. Your site provided us with helpful info to work on. You have performed a formidable activity and our entire neighborhood will be thankful to you.| I just want to mention I am new to blogging and site-building and really savored this blog site. Very likely I’m likely to bookmark your blog post . You surely come with tremendous article content. Appreciate it for sharing with us your web-site.
2024年1月07日 16:21
Hi there I am so excited I found your webpage, I really found you by error, while I was researching on Askjeeve for something else, Anyhow I am here now and would just like to say thank you for a incredible post and a all round interesting blog (I also love the theme/design), I don’t have time to look over it all at the minute but I have saved it and also added in your RSS feeds, so when I have time I will be back to read much more, Please do keep up the awesome work.|
2024年1月07日 16:29
Hi are using WordPress for your blog platform? I’m new to the blog world but I’m trying to get started and create my own. Do you require any coding knowledge to make your own blog? Any help would be really appreciated!| I have read so many posts concerning the blogger lovers however this paragraph is in fact a fastidious article, keep it up.|
2024年1月07日 16:40
Do you mind if I quote a couple of your articles as long as I provide credit and sources back to your website? My website is in the very same area of interest as yours and my users would certainly benefit from some of the information you provide here. Please let me know if this alright with you. Thanks a lot!|
2024年1月07日 16:42
Being grateful for for your post. I know that within today’s complicated world, folks have many beliefs and this has made it to be really hard for learners just like me. However, you have made the idea very easy for me to comprehend and I now know the correct thing. Your continued reputation among the top experts with this topic may be enhanced through words of appreciation from followers like me. Thanks, once more.
2024年1月07日 16:49
Hello, i read your blog occasionally and i own a similar one and i was just curious if you get a lot of spam responses? If so how do you stop it, any plugin or anything you can advise? I get so much lately it’s driving me crazy so any assistance is very much appreciated.|
2024年1月07日 17:03
was wondering if you ever thought of changing the page layout of your site? Its very well written; I love what youve got to say. But maybe you could a little more in the way of content so people could connect with it better. Youve got an awful lot of text for only having 1 or 2 images. Maybe you could space it out better?|
2024年1月07日 17:19
it is a really nice point of view. I usually meet people who rather say what they suppose others want to hear. Good and well written! I will come back to your site for sure!I was reading through some of your blog posts on this website and I conceive this website is rattling instructive! Retain posting.
2024年1月07日 17:21
Being grateful for for your post. I know that within today’s complicated world, folks have many beliefs and this has made it to be really hard for learners just like me. However, you have made the idea very easy for me to comprehend and I now know the correct thing. Your continued reputation among the top experts with this topic may be enhanced through words of appreciation from followers like me. Thanks, once more.
2024年1月07日 17:37
We are a group of volunteers and starting a new scheme in our community. Your site provided us with helpful info to work on. You have performed a formidable activity and our entire neighborhood will be thankful to you.| I just want to mention I am new to blogging and site-building and really savored this blog site. Very likely I’m likely to bookmark your blog post . You surely come with tremendous article content. Appreciate it for sharing with us your web-site.
2024年1月07日 17:47
Hi there I am so excited I found your webpage, I really found you by error, while I was researching on Askjeeve for something else, Anyhow I am here now and would just like to say thank you for a incredible post and a all round interesting blog (I also love the theme/design), I don’t have time to look over it all at the minute but I have saved it and also added in your RSS feeds, so when I have time I will be back to read much more, Please do keep up the awesome work.|
2024年1月07日 17:56
I am extremely impressed with your writing skills as well as with the layout on your weblog. Is this a paid theme or did you customize it yourself? Either way keep up the nice quality writing, it’s rare to see a great blog like this one these days.| Informative, pretty much as I had come to expect from this site.
2024年1月07日 17:56
Hi are using WordPress for your blog platform? I’m new to the blog world but I’m trying to get started and create my own. Do you require any coding knowledge to make your own blog? Any help would be really appreciated!| I have read so many posts concerning the blogger lovers however this paragraph is in fact a fastidious article, keep it up.|
2024年1月07日 18:04
Do you mind if I quote a couple of your articles as long as I provide credit and sources back to your website? My website is in the very same area of interest as yours and my users would certainly benefit from some of the information you provide here. Please let me know if this alright with you. Thanks a lot!|
2024年1月07日 18:13
Just wish to say your article is as amazing. The clarity in your post is just nice and i could assume you are an expert on this subject. Fine with your permission allow me to grab your RSS feed to keep updated with forthcoming post. Thanks a million and please continue the rewarding work.|
2024年1月07日 18:20
This is my first time i visit here. I found so many entertaining stuff in your blog, especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here! Keep up the good work.World Facts For Children… […]here are some links to sites that we link to because we think they are worth visiting[…]…
2024年1月07日 18:25
Hello, Neat post. There’s a problem along with your web site in internet explorer, would test this? IE nonetheless is the market leader and a huge element of folks will pass over your great writing due to this problem.|so I only wanted to offer a fast shout out and claim I genuinely enjoy studying your articles. Could you suggest any other blogs/websites/forums that will deal with the identical subjects? Thanks.
2024年1月07日 18:47
you’re actually a just right webmaster. The web site loading pace is incredible. It seems that you are doing any unique trick. Moreover, The contents are masterpiece. you have done a wonderful job on this matter! you’re in point of fact a excellent webmaster. The web site loading velocity is amazing. It sort of feels that you’re doing any unique trick. Also, The contents are masterpiece. you’ve done a wonderful job on this matter!
2024年1月07日 18:56
Sweet blog! I found it while browsing on Yahoo News. Do you have any tips on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Cheers| Hi. i think that you should add captcha to your blog.
2024年1月07日 19:07
it is a really nice point of view. I usually meet people who rather say what they suppose others want to hear. Good and well written! I will come back to your site for sure!I was reading through some of your blog posts on this website and I conceive this website is rattling instructive! Retain posting.
2024年1月07日 19:20
I think this is one of the most vital info for me. And i’m glad studying your article. However should observation on few general things, The web site style is perfect, the articles is in reality excellent : D. Just right activity, cheers| This is a topic which is near to my heart… Take care! Exactly where are your contact details though?|
2024年1月07日 19:26
Strong blog. I acquired several nice info. I?ve been keeping a watch on this technology for a few time. It?utes attention-grabbing the method it retains totally different, however many of the primary components remain a similar. have you observed a lot change since Search engines created their own latest purchase in the field?
2024年1月07日 19:34
Good – I should certainly pronounce, impressed with your web site. I had no trouble navigating through all the tabs as well as related info ended up being truly simple to do to access. I recently found what I hoped for before you know it at all. Reasonably unusual. Is likely to appreciate it for those who add forums or anything, website theme . a tones way for your client to communicate. Nice task.
2024年1月07日 19:42
After study several of the web sites for your website now, and that i truly such as your technique of blogging. I bookmarked it to my bookmark website list and are checking back soon. Pls consider my website at the same time and make me aware if you agree.
2024年1月07日 19:52
Hey there would you mind stating which blog platform you’re working with? I’m going to start my own blog soon but I’m having a difficult time choosing between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your design and style seems different then most blogs and I’m looking for something completely unique. P.S My apologies for getting off-topic but I had to ask!|
2024年1月07日 20:08
was wondering if you ever thought of changing the page layout of your site? Its very well written; I love what youve got to say. But maybe you could a little more in the way of content so people could connect with it better. Youve got an awful lot of text for only having 1 or 2 images. Maybe you could space it out better?|
2024年1月20日 14:03
I really appreciate the kind of topics you post here. Thanks for sharing information that is actually helpful. Good day! Want to know the steps to resolve
2024年1月20日 15:25
Extremely nice and informative article!
2024年1月20日 15:57
Extremely nice and informative article!
2024年1月20日 16:42
Couldn?t be created any better. Reading this post reminds me of my old room mate! He always kept talking about this. I will forward this report to him. Pretty certain he will possess a good read. Thanks for sharing!
2024年1月20日 17:31
This post is extremely easy to peruse and acknowledge without forgetting any subtle elements. Incredible work
2024年1月20日 18:06
This is exciting, nevertheless it is vital for you to visit this specific url:
2024年1月20日 18:39
Thanks for the blog post buddy! Keep them coming.
2024年1月20日 19:00
This unique appearances utterly suitable. Each one of modest data are prepared with the help of great number of experience practical knowledge. I'm keen it again very much
2024年1月20日 19:36
"This is a good tip especially to those fresh to the blogosphere.
Short but very precise information… Appreciate your sharing this
one. A must read post!"
2024年1月20日 20:22
If you are looking for more information about flat rate locksmith Las Vegas check that right away.
2024年1月20日 20:53
Brilliant demonstrated data. I thank you about that. Clearly it will be unbelievably helpful for my future endeavors. Should see some different posts on a practically identical subject!
2024年1月24日 19:35
I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work
2024年1月28日 13:39
This is my first time i visit here. I found so many entertaining stuff in your blog, especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the leisure here! Keep up the good work. I have been meaning to write something like this on my website and you have given me an idea.
2024年1月28日 13:59
Awesome and interesting article. Great things you've always shared with us. Thanks. Just continue composing this kind of post.
2024年1月28日 14:17
This is my first visit to your web journal! We are a group of volunteers and new activities in the same specialty. Website gave us helpful data to work.
2024年1月28日 14:32
This was among the best posts and episode from your team it let me learn many new things
2024年1月28日 14:39
게시물을 작성해 주셔서 감사합니다. 나는 귀하의 게시물이 마음에 들며 귀하가 우리와 공유하는 모든 것은 최신이며 매우 유익합니다. 멋진 일을 해냈으므로 페이지를 북마크하여 다시 읽을 수 있습니다
2024年1月28日 14:56
콘텐츠에 대한 내 생각을 설명하기는 힘들지만 여기에 있어야한다고 느꼈습니다. 귀하의 기사는 정말 훌륭합니다. 이 정보를 작성한 방식이 마음에 듭니다
2024年1月28日 15:10
게시물을 작성해 주셔서 감사합니다. 나는 귀하의 게시물이 마음에 들며 귀하가 우리와 공유하는 모든 것은 최신이며 매우 유익합니다. 멋진 일을 해냈으므로 페이지를 북마크하여 다시 읽을 수 있습니다
2024年1月28日 15:19
콘텐츠에 대한 내 생각을 설명하기는 힘들지만 여기에 있어야한다고 느꼈습니다. 귀하의 기사는 정말 훌륭합니다. 이 정보를 작성한 방식이 마음에 듭니다
2024年1月28日 15:29
게시물을 작성해 주셔서 감사합니다. 나는 귀하의 게시물이 마음에 들며 귀하가 우리와 공유하는 모든 것은 최신이며 매우 유익합니다. 멋진 일을 해냈으므로 페이지를 북마크하여 다시 읽을 수 있습니다