Operations on Formal Power Series

Правка en1, от rng_58, 2017-12-17 20:07:08

You are given the first n (or n + 1 if necessary) terms of a former power series P(x) = c0 + c1x + c2x2 + .... What operations can be performed efficiently?

• Obviously, P(x) + Q(x), P(x) - Q(x), P'(x), , kP(x) for a given constant k, can be done in O(n).

• P(x)Q(x) can be done in O(nlogn) by FFT.

• can be done in O(nlogn): Link, check problem E

• can be done in O(nlogn): Link, check problem E

• exp(P(x)) can be done in O(nlogn): Link, check Figure 1, left

• Open: Can we do more complicated operations like P(Q(x)), P(x)1 / k, sin(P(x)), arcsin(P(x)), etc.? Are there other important operations?

• Probably a bit related to the computation of : when we are given two big decimal number x and y, can we compute x / y?

#### История

Правки

Rev. Язык Кто Когда Δ Комментарий
en1 rng_58 2017-12-17 20:07:08 1157 Initial revision (published)