Hi!
I started a blog recently, and one of my recent discussions on FFT led me to post a new blog post at https://nor-blog.codeberg.page/posts/2024-06-01-implementing-fft/ exploring some FFT algorithms — more specifically, alternate (potentially better) implementations that not many people are aware of. The contents of this post might be a bit well-known to people who write their own FFT templates, but having a good understanding of FFT should help others too.
Why a new blog?
nor orz
nor : Is there any reason why your page doesn't have an explicit comment section? I loved your blog on C++ lambdas btw ;)
I mean probably DISQUS is easiest to set up and requires auth (if you want to enforce), so I don't think there would be many spam messages either.
Hi! I'm glad you liked the post and hope you learnt something new from it.
As a personal choice, I did not want to have explicit comment sections, because sometimes comments drown out the main point of the post. I also like corresponding with people on topics of mutual interest, and would also be glad to receive comments over via email. So I started this as an experiment, partly inspired by this well-written blog post, and was pleasantly surprised that the quality of comments I receive over email is much higher and more productive than what I have received in comment sections. I plan on mentioning interesting things I learn from email correspondence with blog readers in my blog too (if they are fine with it, of course)! Plus, sometimes people care about their online footprint, and I don't really want to manage any content that is not my own, on my blog. I would much rather prefer that they comment on it on their own spaces, since it often leads to a more structured presentation, and in a format that they are comfortable with.
And for anyone who somehow did not figure out how to correspond with me related to blog content, feel free to get in touch with me via these instructions!
I thought I had lost your blogs forever! the web archive didn't open spoilers in your blogs either. Happy to see them again on your website :) nor orz
great work
Thank you for you blog! In 1975G - Zimpha Fan Club my solution 262609849 literally took 11952 ms out of TL = 12000 ms, so I'm really interested in having a much faster FFT in my weaponry.
In that case, I highly recommend looking at the AtCoder Library convolution implementation — it does a radix 4 transform instead of radix 2, which makes it quite fast. Note that removing the bit reversal will show results when your implementation is already decently optimized, and you can already go very far without resorting to SIMD.