This site is supported by donations to The OEIS Foundation.

User talk:Peter Luschny/P-Transform

From OeisWiki
Jump to: navigation, search

G.f. and more efficient calculation

By considering a combinatorial interpretation for the binomial products, I was led to the form (ignoring the norm) .

Obviously this could equally be expressed as

This has two implications. Firstly, it suggests that it might be more natural to decompose this into two transformations: one which takes partial products of the original sequence, and one which maps to g.f. .

Secondly, it gives the alternative computation

def PartialPtransGF(n, f, norm = None):
    if n == 0:
        return [1]

    x = [1]
    for i in range(1, n+1):
        x.append(x[-1] * f(i))

    psr.<y> = PowerSeriesRing(x[-1].parent(), default_prec = n+1)
    R = [0]
    A = psr(0).O(n+1) - sum(y^i * x[i] for i in range(1, n+1))
    Apow = 1
    for i in range(1, n+1):
        Apow *= A
        R.append(Apow[n])

    return R if norm is None else [norm(n,k)*R[k] for k in (0..n)]

In my benchmarking this is considerably faster than PartialPtransRec, which is to be expected because it can use Karatsuba's algorithm to accelerate the polynomial multiplications. Peter J. Taylor (talk) 09:37, 9 July 2024 (EDT)