Skip to main content
Clearance.
Source Link
user2468
user2468

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 r(x) dx$, and use$\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) andto compute $\rho(b) - \rho(a).$


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

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 r(x) dx$, and use fast integration methods, or simply fast evaluation methods (e.g. Horner) and compute $\rho(b) - \rho(a).$


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

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

Source Link
user2468
user2468

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 r(x) dx$, and use fast integration methods, or simply fast evaluation methods (e.g. Horner) and compute $\rho(b) - \rho(a).$


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