Suppose we have two integers $a$ and $b$, and a polynomial in $x$, $p(x)$.

What's the fastest way to get an exact value for $\int_a^b{(p(x))^n dx}$, with $n$ large?

This is a more complicated version of this question, but an easier version of "What's the fastest way to get an exact value for a product of (powers of polynomials)?".

  • $\begingroup$ I have what I believe is a neat trick to do this, and I'll probably post it in a few days or so. $\endgroup$ – Matt Groff Feb 19 '12 at 16:31
  • $\begingroup$ You seem to be testing us.... $\endgroup$ – Pedro Tamaroff Feb 19 '12 at 18:13
  • $\begingroup$ @Peter: No, sorry. I just thought that it would distract from having more answers. Now I don't even think it will work. $\endgroup$ – Matt Groff Feb 19 '12 at 19:15

I'm assuming $p(x) \in \mathbb{R}[x]$. If $\deg p(x) \le d$, then $\deg p(x)^n \le nd$. Let $r(x) = p(x)^n$.

To compute $r(x)$, you can either multiply $p(x)$ with itself $\log n$ times. Or, you can interpolate $r(x)$ at $nd+1$ points, which would require first evaluating $p(x_i)$ and then computing $p(x_i)^n$, for $0 \le i \le nd$. Finally you interpolate $r(x_i)$ This is presumably faster than multiplication.

Once you have an expression for $r(x) = r_0 + r_1 x + \ldots + r_{nd-1} x^{nd-1}$ then you can easily construct $\rho(x) = \int_a^b r(x) dx$ using fast integration methods, or simply construct $\rho(x) = \int r(x) dx$ as a close form expression in the straightforward way, and use fast evaluation methods (e.g. Horner) to compute $\rho(b) - \rho(a).$

(This a naive approach but I guess it is worth writing.)

  • 1
    $\begingroup$ I was considering only integer coefficients. But this is interesting. $\endgroup$ – Matt Groff Feb 19 '12 at 16:58
  • $\begingroup$ @MattGroff then please remove the tag numerical-methods, and add the tag algorithms. Your question is then in the realm of computer algebra methods. $\endgroup$ – user2468 Feb 19 '12 at 17:16

I'm a little scared to post this, I'm not sure this is correct, and I believe there are better approaches than this, but I'll post this. Consider doing an "illegal move": Integrate over a field (even though fields have measure zero and therefore can't be integrated over)

The idea is that we are going to use numbers modulo a prime $p$. So to do so, we do calculations modulo $p(p-1)$. Here's why: when calculating a value in a field, all of the powers in a field modulo $p$ are taken modulo $p-1$, so that's why we add the $p-1$ factor. We only need $O(\log n)$ multiplication operations modulo $p(p-1)$ to come up with a pseudoresult (before integration). We then integrate modulo $p(p-1)$. From this result we can easily get a value modulo $p$, which should then be correct, but not complete.

We note that multiplying will give us a fraction, with a denominator approximately $(\deg p(x)\cdot n)!$. So we must do a bunch of the same integration technique described above in different fields. This will allow us to use Chinese Remainder Theorem to recover the exact value. We note that the numerator of the fraction is multiplied by the reciprocal of the denominator in each field. So we multiply appropriately to cancel this out in each field, and then CRT gives us the denominator.

This may be very confusing and far from being carefully checked, but then again it just may work.

  • $\begingroup$ This sounds fascinating. I can't quite imagine it, though. Have you tried it on some simple example, perhaps? $\endgroup$ – Dejan Govc Feb 19 '12 at 23:31
  • $\begingroup$ @Dejan Govc: Thanks. I've tried this on single variables to various powers, but that's as far as I got. $\endgroup$ – Matt Groff Feb 20 '12 at 2:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.