Hi

Update 1

Thanks to conqueror_of_tourist, the search term is Online FFT.

Unfortunately... it's quite beyond me to understand it. I have been reading and this is the best code I could draft but it's not working (returning 12 instead of 14). Anyone familiar, can you spot anything wrong? Thanks.

import numpy as np


def catalan(n: int):
  f = np.zeros(n + 1).astype(int)
  f[0] = 1
  for i in range(n - 1):
    f[i + 1] += f[i]
    f[i + 2] += f[i]
    two_pow = 2
    while i > 0 and i % two_pow == 0:
      a = f[i - two_pow : i]
      b = f[two_pow : min(n, two_pow * 2)]
      two_pow *= 2

      contrib = np.convolve(a, b)
      for j in range(min(len(contrib), n - i)):
        f[i + j + 1] += contrib[j]

  return f[:n]


print(catalan(10))

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