Operations on Formal Power Series

Revision en1, by 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

  • : Link

  • 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?

Tags fft

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rng_58 2017-12-17 20:07:08 1157 Initial revision (published)