Why is f.inverse() so slow?

[Peter Luschny]

Hi all,

I wanted to implement the Euler Transformation. 

https://oeis.org/wiki/Euler_transform

My first attempt was:

def EulerTransform(size, a):

    R.<x> = ZZ[[]]

    f = prod((1 - x^n)^a(n) for n in (1..size)) + O(x^size)

    return f.inverse().list()

print(EulerTransform(6, lambda n: factorial(n)))

Now try this with size = 30. I have no idea how long this 

takes because after 3 years I turned the computer off.

Am I doing something fundamentally wrong, or is f.inverse() 

hopelessly slow?

You can of course implement it differently, but that's not my 

question. For those who are interested in the transformation

here the fast variant:

def EulerTrans(a):

    @cached_function

    def b(n):

        if n == 0: return 1

        s = sum(sum(d*a(d) for d in divisors(j))*b(n-j) for j in (1..n))

        return s//n

    return b

    

b = EulerTrans(lambda n: factorial(n))

print([b(n) for n in range(30)])

Thanks

[Zachary Scherr]

Are you sure it's the inverse function which is slow? Just looking at the command 

f = prod((1 - x^n)^a(n) for n in (1..size)) + O(x^size)

I would guess that first the gigantic product is computed, and only then would the resulting polynomial be truncated by the O(x^size) part.

Maybe try to alter that via:

f = prod((1 - x^n + O(x^size))^a(n) for n in (1..size))

[Peter Luschny]

Maybe try to alter that via:

f = prod((1 - x^n + O(x^size))^a(n) for n in (1..size))

Yes, that is the solution. Thank you so much!