Hi↵
↵
---↵
↵
#### Update 4↵
↵
[user:Andrycraft] has provided the solution 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↵
↵
```python↵
if l == r:↵
if l > 1:↵
f[l] += f[l - 1]↵
return↵
```↵
↵
#### 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 :()↵
↵
```python↵
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 [user:conqueror_of_tourist,2025-01-26], 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.↵
↵
```python↵
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
↵
---↵
↵
#### Update 4↵
↵
[user:Andrycraft] has provided the solution 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↵
↵
```python↵
if l == r:↵
if l > 1:↵
f[l] += f[l - 1]↵
return↵
```↵
↵
#### 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 :()↵
↵
```python↵
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 [user:conqueror_of_tourist,2025-01-26], 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.↵
↵
```python↵
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
