duckladydinh's blog

Can we use FFT to compute the first n values of a self-convolution form in O(nlogn)?
By duckladydinh, history, 36 hours ago, In English

Hi

I am learning FFT. ChatGPT told me that FFT could assist in solving self-convolution form like Catalan number where the (n+1)-th element is some convolution of the first n elements. For example:

c[n + 1] = sum(c[i][n — i]) for i in 0..n

Unfortunately, no matter where I look (and how hard I press ChatGPT), I couldn't find a single website/book/paper detailing this approach.

My Question: Is it actually possible to compute the first n elements of a self-convolution form like Catalan using FFT in, for example, O(nlogn) or less than O(n^2)?

Thanks a lot

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
36 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

→ Reply
»
36 hours ago, # |
  Vote: I like it +18 Vote: I do not like it

On Codeforces (and in competitive programming) this is usually known as 'Online FFT'. You should be able to find CF blog posts on this topic solving it in $$$O(n\log^2{n})$$$.

→ Reply
»
23 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Suppose we have

$$$a_0=c,\quad a_{n+1}=\sum_{i=0}^{n}a_i b_{n-i}$$$

Then the generating function A(x) satisfies A=ABx+c and therefore we may invert 1-Bx to find a in O(nlogn).

→ Reply