# $O(\text{polylog}(1/\epsilon))$-time Algorithm for Numerical Integration to Within Additive $\epsilon$?

I'm trying to approximate a 1D definite integral to within an additive $\epsilon$ for a given $\epsilon$. I was wondering whether there is an $O(\text{polylog}(1/\epsilon))$-time algorithm for this. The usual numerical methods (trapezoidal, Simpson's, etc) seem to yield only $O(\text{poly}(1/\epsilon))$ time.

EDIT: Maybe I should flesh out my thinking a little bit. If $I=\int_a^bf(x)dx$ and $I_T$ is the rectangular approximation with $n$ points, then for some $c_i$s each in $(a+(i-1)\Delta,a+i\Delta)$ (where $\Delta=(b-a)/n$), we have:

\begin{align*} |I-I_T| &= \sum_{i=1}^n \frac{(b-a)^2}{2n^2}|f'(c_i)| \\ &\leqslant \frac{(b-a)^2}{2n}\max_{x'\in(a,b)}|f'(x')| \leqslant \epsilon. \end{align*}

which requires an order of $1/\epsilon$ points. I don't know if this makes...

Using $n$ values on a segment $[a,b]$ one can numerically compute $\int_a^n f(x) dx$ with a gaussian rule with $n$ nodes. That rule would have an error of magnitude $$\epsilon_n = \frac{(b-a)^{2n+1} (n!)^4}{(2n+1)[(2n)!]^3}f^{(2n)}(\xi)\\ \log |\epsilon_n| = (2n+1)\log (b-a) + 4\log n!-\log(2n+1)-3\log(2n)! + \log |f^{(2n)}(\xi)| = \\ = (2n+1)\log(b-a)+4n(\log n-1)-\log2 + \log n-6n(\log n + \log 2-1) + \log |f^{(2n)}(\xi)| + O(n^{-1}) = \\ = -2n\log n +\log |f^{(2n)}(\xi)| + 2n\left[\log(b-a) +1-3\log 2\right] + O(1)$$ For not too fast growing $f(x)$, for examlpe $\max_\xi |f^{2n}(\xi)| = O(n!)$ $$\log |\epsilon_n| = -n \log n + O(n).$$ So that means that error decays at least as fast as $n^{-n}$ which itself decays faster that $e^{-n}$. So $$n = O(\log 1/\epsilon_n).$$