MarkZuckerberg's blog

[ Tutorial Request ] Fast Fourier Transform
By MarkZuckerberg, 4 years ago, In English

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: demoralizer 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.

  • Vote: I like it
  • -29
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
4 years ago, # |
  Vote: I like it +125 Vote: I do not like it

I don't know it myself. Probably best to leave it to the legends (e.g. the other people you mentioned).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -81 Vote: I do not like it

gand.jpg

→ Reply
»
4 years ago, # |
  Vote: I like it -45 Vote: I do not like it

you can refer this https://www.youtube.com/watch?v=qrGBpexbT-c&t=2810s lecture by kevin

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you can watch this : https://youtu.be/Xwu6rq41nE8 by Gaurav sen

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have watched this, but it's theoretical again. I have the understanding, I just need the implementation part

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +115 Vote: I do not like it

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.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    Name checks out

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    your toturial are very nice detail explained

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    galen_colin looks like you are not alone XD..I am also going to learn fft now (/^▽^)/

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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).

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I'm gonna change my handle to -is-this-suffix-automata- then

    → Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

You forgot the EDU guys, pashka and Aksenov239.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

This Chinese article is great I think. You can google translate it if you need it.

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Can you mention some problems where we really need to know FFT to solve them??

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Bold of you to assume that I know how FFT works (I don't)

→ Reply