# Is it possible to get an easy answer for $\int {\frac {p(x) (q(x)^{1/2})} {r(x) (s(x)^{1/2})}dx}$

Given four polynomials in $x$, called $p(x), q(x), r(x), s(x)$, such that $$\text{poly}(x) = \sum_{k=0}^N {c_k x^k},\qquad (c_k \in \mathbb{N}) \land (|c_k| \le N^2)$$

Is it possible to get an easy (which will be defined later) solution to $$\int {\frac {p(x) (q(x)^{1/2})} {r(x) (s(x)^{1/2})} dx}$$

We define an easy solution as a solution done in polynomial time with respect to $N$ (in other words, the time it takes to get a solution is a polynomial function of $N$) and either:

(1) We get a solution of the definite integral that has arbitrary limits of integration and is accurate to $N$ decimal places. The limits may be reals with an absolute value that doesn't exceed $N^2$.

(2) We get an exact solution to the indefinite integral.

My question is, can we find some way to get an easy solution, or prove that an easy solution is impossible/possible?

MOTIVATION

This question arises from this answer to this question.

I'm attempting to determine if this integral is a potential candidate for a one-way function. It could possibly be used as a new security measure, but that may be years and years away from actual use, if it ever happens.

-

Suppose the integrand has a pole of order $k > 1$. Then the antiderivative has a pole there of order $k-1$. If the pole is in the interval of integration, presumably your algorithm should return "undefined" or "infinity". But you could run into difficulties if the pole is close to the interval. You'll need to be able to find the poles accurately, and also you'll need the endpoints accurately. If you are only given decimal approximations of an endpoint, there's no guarantee that any particular approximation will be accurate enough to decide which side of a pole it's on. Even if you have the endpoint with arbitrary accuracy (in the sense that you can ask for, and be given, the first $M$ decimal digits for any desired $M$), if that endpoint happens to be equal to the pole there's no way to detect that fact.
EDIT: On the other hand, suppose the integrand $f(x)$ and interval $[a,b]$ are fixed, and the integrand is analytic in a neighbourhood of $[a,b]$. By finding the roots of $r(z)$ and $s(z)$ you can find $\epsilon > 0$ so that $f(z)$ is analytic in $\{z\in {\mathbb C}: \text{dist}(z,[a,b]) < \epsilon\}$. Take integer $n > (b-a)/\epsilon$, and $x_j = a + j(b-a)/n$ for $j = 0,1,\ldots n$. You can calculate the Taylor series of $f(z)$ about each $x_j$ and use it for the integral from $x_j$ to $x_{j+1}$. If $k$ terms are used, you will get an error bounded by $C r^k$ for some computable $C$ and $r$ with $0 <r<1$. Note that to calculate $k$ coefficients will take time polynomial in $k$, using the binomial series: if $g(x) = g(x_0) + h(x-x_0)$, $g(x)^\alpha = \sum_{j=0}^\infty {\alpha \choose j} g(x_0)^{\alpha - j} h(x-x_0)^j$. So you can get $N$-digit accuracy in time polynomial in $N$.