### MaheshBhatt's blog

By MaheshBhatt, 14 months ago,

I want to request all the popular CP YouTubers like SecondThread, galen_colin, tmwilliamlin168, Errichto and all others (these are my favourite).

Can you guys please make a proper tutorial on FFT, with C++/Java/Python Code implementation as well? I know there are blogs on it but a topic like this seriously needs a video tutorial, it becomes tougher if you do it by text. We learned a mathematical/theoretical version in college i guess, but there is no code it it.

While there are certainly some paid courses which teaches them (not sure) but i don't think i can afford them anyways, so i look up to you all orz. This topic is rare af, and no one has a proper video tutorial on web with code.

UPD: HealthyUG orz ! looks like my man is gonna do it ! wishing him 69 years of luck !!

P.S — Don't judge by the ratings on this handle, i use it to shitpost. I really want to learn FFT.

• -29

 » 14 months ago, # |   +125 I don't know it myself. Probably best to leave it to the legends (e.g. the other people you mentioned).
 » 14 months ago, # | ← Rev. 2 →   -81
•  » » 14 months ago, # ^ |   -82
•  » » 14 months ago, # ^ |   -43 XD XD XD XD XD
 » 14 months ago, # |   -45 you can refer this https://www.youtube.com/watch?v=qrGBpexbT-c&t=2810s lecture by kevin
 » 14 months ago, # |   0 you can watch this : https://youtu.be/Xwu6rq41nE8 by Gaurav sen
•  » » 14 months ago, # ^ |   0 I have watched this, but it's theoretical again. I have the understanding, I just need the implementation part
 » 14 months ago, # | ← Rev. 4 →   +115 How I learned FFT ("shitpost tutorial"): Remember that FFT is more or less a black box that does the following: $C[k] = \sum_{i + j = k} A[i] \cdot B[j] \iff \hat{C}[k] = \hat{A}[k] \cdot \hat{B}[k].$(for all valid $i, j, k$; $i + j$ is calculated modulo the length but that last bit is often irrelevant). If you need to use it for something, copy FFT from somewhere.
•  » » 14 months ago, # ^ |   +39 Name checks out
•  » » 14 months ago, # ^ |   +10 your toturial are very nice detail explained
•  » » 14 months ago, # ^ |   +10 galen_colin looks like you are not alone XD..I am also going to learn fft now (/^▽^)/
•  » » 14 months ago, # ^ |   +10 Even though that's not enough for harder problems, that's enough for most problems (and probably the way most people including me "learned" it at first).
•  » » 14 months ago, # ^ |   +13 I'm gonna change my handle to -is-this-suffix-automata- then
 » 14 months ago, # |   -23 karangreat_234 is a good person to ask this from.
 » 14 months ago, # |   -6 You forgot the EDU guys, pashka and Aksenov239.
•  » » 14 months ago, # ^ |   0 Really hope that they would make videos on this as well
 » 14 months ago, # |   +8 This Chinese article is great I think. You can google translate it if you need it.
•  » » 14 months ago, # ^ |   0 can you suggest some Chinese article for algorithm....as like it?
 » 14 months ago, # |   +11 Can you mention some problems where we really need to know FFT to solve them??
•  » » 14 months ago, # ^ |   +3 I solved https://open.kattis.com/problems/polymul2 with the code from https://cp-algorithms.com/algebra/fft.html
•  » » » 14 months ago, # ^ |   0 Thank You!!
•  » » 14 months ago, # ^ | ← Rev. 2 →   +57 https://codeforces.com/problemset/problem/1103/Ehttps://www.codechef.com/OCT17/problems/XORTREEHhttps://www.codechef.com/problems/POLYEVALthere are more problems like that but these are the ones I can remember/find easily.
•  » » » 14 months ago, # ^ |   0 Thank You!!
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Now I see, these problems are quite rare but can be a gamechanger in some important competition.Thanks for this blogpost.
 » 14 months ago, # | ← Rev. 2 →   +30 Although my name isn't in the blog and I'm nowhere even near the people mentioned, but if none of them do it within a week, I'm doing it. And this one I'll do in English, cuz as you pointed out, it's not available in English either.
•  » » 14 months ago, # ^ |   -16 Bro, you are an absolute legend! Hoping to see you red soon!
 » 14 months ago, # |   +20 Bold of you to assume that I know how FFT works (I don't)