rng_58's blog

By rng_58, history, 5 weeks ago, In English,

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
 
 
 
 
  • Vote: I like it  
  • +319
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it +117 Vote: I do not like it
»
5 weeks ago, # |
Rev. 3   Vote: I like it +77 Vote: I do not like it

Composition can be computed in time (http://www.eecs.harvard.edu/~htk/publication/1978-jacm-brent-kung.pdf )

P(x)α can be computed as explog P(x))

arcsin(P(x)) can be computed in time O(n log2 n) using Newton's method (source : https://hal.archives-ouvertes.fr/AECF/ ).

»
5 weeks ago, # |
Rev. 2   Vote: I like it +91 Vote: I do not like it

I have never done this before, but seems to me that

and complex numbers can be implemented as pairs of residues modulo 998244353 or any other good number. Not sure that this will be fast, though.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    We don't even need pairs because  - 1 is a quadratic residue modulo p (if p if NTT-friendly).

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

I think calculating P(Q(x)) is not so hard and can be done in this way.
1. Calculate Q(x) for x = 0, 1, 2, 3, ... , 2n. We can use multi-point evaluation and it can be done in O(nlg2 n).
2. Calculate P(x) for x = Q(0), Q(1), Q(2), ..., Q(2n). Since you calculated the value of Q(0), Q(1), ... , Q(2n) in 1., so it can be done by multi-point evaluation of less than or equal to 2n + 1 points so it can be done in O(nlg2 n).
3. So now you have values of P(Q(0)), P(Q(1)), P(Q(2)), ... , P(Q(2n)). You can use interpolation method and you can get Lagrange polynomial in O(nlgn).
So I think overall operation is O(nlg2 n).

UPD: I was wrong, thanks Kaban-5 for pointing out.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 4   Vote: I like it +24 Vote: I do not like it

    Even if P and Q are just polynomials of degree n, you can't find first n terms of P(Q(x)) by interpolating it from values (at least not in any straightforward way), because there is little connection between values and first terms of polynomial.

    For example, let n = 3, P(x) = Q(x) = x3, then P(Q(x)) = x9. However, what last interpolation will give you is some polynomial of degree less than 7 that coincides with x9 in points 0, 1, ..., 6, which is obviously not what you expect (because it is not zero, hence, is not prefix of P(Q(x))).

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

I have seen power, composition and inverse used in problems involving generating functions, but haven't seen examples of using exp, log, sine, arcus sine. Have there been problems / can someone design a problem requiring the calculation of them in context of competitive programming? Maybe some kind of recurrence relation which produces a second order differential equation? I'm not certain how to fix the initial conditions, etc.

»
5 weeks ago, # |
Rev. 4   Vote: I like it +43 Vote: I do not like it

You can obtain most of functions over formal series using Newton's method.

For example,

(You may see corresponding section here)

Also Lagrange inversion theorem may be useful. For instance in case of equation

You can solve it as

And also

»
5 weeks ago, # |
  Vote: I like it -95 Vote: I do not like it

Just a show off aren't ya? So much rating, still wunt more contrib? You are the reason no girls code.