duckladydinh's blog

By duckladydinh, history, 4 weeks ago, In English

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

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

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})$$$.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Suppose we have

$$$a_0=c,\quad a_{n+1}=\sum_{i=0}^{n}a_i b_{n-i}$$$

Then the generating function A(x) satisfies A=ABx+c and therefore we may invert 1-Bx to find a in O(nlogn).

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The following Python code works for calculating Catalan using online FFT.

from numpy import *

def catalan(n: int):
    f = [0] * (n + 1)
    f[0] = 1

    # calculate the contribution of f[l1:r1+1]*f[l2:r2+1] => f[l:r+1]
    def contrib(l1, r1, l2, r2, l, r):
        if l1 + l2 + 1 > r or r1 + r2 + 1 < l or l1 > r1 or l2 > r2 or l > r:
            return
        u = f[l1 : r1 + 1]
        v = f[l2 : r2 + 1]
        res = convolve(u, v)
        for i in range(l, r + 1):
            if i - 1 - l1 - l2 in range(0, len(res)):
                f[i] += res[i - 1 - l1 - l2]

    # CDQ on [l, r]
    def work(l, r):
        if l == r:
            return
        mid: int = (l + r) // 2
        work(l, mid)
        t = min([r - l, l - 1])
        contrib(0, t, l, mid, mid + 1, r)
        contrib(l, mid, 0, t, mid + 1, r)  # same as contrib(0, t, l, mid, mid + 1, r)
        contrib(l, mid, l, mid, mid + 1, r)

        work(mid + 1, r)

    work(0, n)
    return list(map(int, f))

print(catalan(20))
  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by duckladydinh (previous revision, new revision, compare).