Hi
Update 4
Andycraft has provided the solution here computing Catalan using FFT + CDQ which is actually not very scary.
Bonus: For a slightly different self full convolution where f[n + 1] = f[i]f[j] for i + j <= n, it could be achieved by adding a simple change to his code
if l == r:
if l > 1:
f[l] += f[l - 1]
return
I can't wait looking how to expand this.
Update 3
Actually no, the below code is at least O(n^2logn), not O(N(logN)^2), back to 0, then :(.
Update 2
Finally, after some desperate struggling, I am able to do it (I feel so old for challenges already :()
import numpy as np
def catalan(n: int):
f = np.zeros(n + 1).astype(int)
g = np.zeros(n + 1).astype(int)
f[0] = 1
for i in range(n):
two_pow = 1
while True:
ay = i + 1 - two_pow
ax = max(0, ay - two_pow + 1)
bx = two_pow - 1
by = min(i, bx + two_pow - 1)
c = np.convolve(f[ax : ay + 1], f[bx : by + 1])
g[i] += c[i - (ax + bx)]
if ax == 0: break
two_pow *= 2
f[i + 1] = g[i]
return f[:n]
print(catalan(12))
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
