The link is here: CDQ convolution (online FFT) generalization with Newton method

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?

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))

Thanks for the search reference. At least, my search is progressing :).

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

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 :).

no one asked me

Since it seems that nobody has answered the question about FFT being used to solve catalan-like self convolutions in $$$O(n \log n)$$$: Yes, it can!

Basically you have to find the generating function then use FFT to compute it fast.

Let's say $$$H = \sum\limits_i \text{C}_i \cdot x^i$$$. We know that $$$\text{C}_n= \sum\limits_{ i \lt n} \text{C}_i \cdot \text{C}_{n-i-1}$$$.

$$$H^2 \cdot x = \sum\limits_{1 \le i} \sum\limits_ {j \lt i} \text{C}_j \cdot \text{C}_{i-j-1} \cdot x^i$$$ which is close to $$$H$$$.

$$$H^2 \cdot x = \sum\limits_{1 \le i} \text{C}_i \cdot x^i$$$. Thus $$$H^2 \cdot x + 1 = H$$$.

From here it's a matter of simplifying it: $$$H^2 \cdot x - H + 1 = 0$$$ ==> $$$ H = \frac{1 ± \sqrt{1 - 4x}}{2x}$$$. We chose the solution that satisfies our conditions. Since $$$\lim\limits_{x→0} \frac{1 -\sqrt{1 - 4x}}{2x}$$$ is $$$0$$$ and $$$\lim\limits_{x→0} \frac{1 + \sqrt{1 — 4}}{2x} = 1$$$, we take the second solution. Reminder that when we evaluate something at $$$0$$$ we take the value of the coeficient of $$$x^0$$$ of its power series which in this case should be $$$C_0$$$ which is $$$1$$$.

After this, you can compute $$$\sqrt{F(x)}$$$ in $$$O(n\log n)$$$ using FFT as explained in the editorial of the problem I linked below. You can read more details on https://cp-algorithms.com/algebra/polynomial.html#newtons-method although it doesn't explain exactly how to do it for sqrt.

This result is well known, it's even in wikipedia https://en.wikipedia.org/wiki/Catalan_number#First_proof and if you want a similar but harder/more dynamic exercise then solve https://mirror.codeforces.com/problemset/problem/438/E