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)?".
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.)
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.
