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
Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
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})$$$.
The link is here: CDQ convolution (online FFT) generalization with Newton method
Thanks, I also found that post but I am more interested in the Online FFT part... which is already quite beyond me :) so it's not time to proceed with the Newton part yet.
I have been reading and was trying to draft a piece of code to compute catalan... but it didn't work. I put it in the post, if u are familiar, do u notice if I code something obviously wrong?
Thanks a lot
Thank you very much. I have been looking at Online FFT for the past 2 days... mainly on https://tanujkhattar.wordpress.com/wp-content/uploads/2018/01/onlinefft1.pdf but unfortunately, it's quite a bit beyond my humble brain.
I draft this piece of code but it returns 12 instead of 14... if you are familiar, do u spot anything that's obviously wrong?
Thanks for the search reference. At least, my search is progressing :).
Suppose we have
Then the generating function A(x) satisfies A=ABx+c and therefore we may invert 1-Bx to find a in O(nlogn).
Thanks, actually I am more interested in the Online FFT part for now as it is already quite beyond me :) so it's not time to proceed with generating function.../inversion... yet.
I have been reading and was trying to draft a piece of code to compute catalan... but it didn't work. I put it in the post, if u are familiar with even more advanced variants, do u maybe notice if I code something obviously wrong?
Thanks a lot
Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
The following Python code works for calculating Catalan using online FFT.
Thank you very much, Andycraft. Thanks to your code, I am able to understand the CDQ too (well, quite a lot of time reading and thinking as I am too old :)). It seems like the CDQ model just differs from the normal divide and conquer by moving contributions from left (and before) to right and limiting the contribution to a given [l, r] at all times and makes it easier to use together with this convolution thing (adamant@ post looks a bit scary to me so I thought it was some complex math thing and stayed away :)).
Thanks a lot, short code is definitely the most expressive language for programmers :).
Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).
Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).