Bostan-Mori algorithm (source code)

= Bostan-Mori algorithm
{c}

= Bostan–Mori
{c}
{synonym}

The <Bostan-Mori algorithm> computes $[x^N]P(x)/Q(x)$ without expanding all preceding coefficients. Work over a <commutative ring> with $Q(0)$ a <unit>; then the quotient defines a <formal power series>.

<Set> $U(x)=P(x)Q(-x)$ and $V(x)=Q(x)Q(-x)$. The <polynomial> $V$ contains only even powers. Define
$$
P'(y)=\sum_{j\geq0}[x^{2j+(N\bmod2)}]U(x)\,y^j,\qquad Q'(y)=\sum_{j\geq0}[x^{2j}]V(x)\,y^j.
$$
Because the denominator $V(x)=Q'(x^2)$ is even, selecting the numerator parity matching $N$ proves
$$
[x^N]\frac{P(x)}{Q(x)}=[y^{\lfloor N/2\rfloor}]\frac{P'(y)}{Q'(y)}.
$$
Iterate until $N=0$, then return $P(0)/Q(0)$. With bounded numerator/denominator <polynomial degrees> $O(d)$, the <arithmetic complexity> is $O(M(d)\log(N+1))$, where $M(d)$ is the cost of multiplying degree-$d$ <polynomials>.

For $1/(1-cx)$, the denominator update is $1-c^2y$. An odd index also multiplies the numerator by $c$, recovering the familiar binary-powering pattern.<A Simple and Fast Algorithm for Computing the N-th Term of a Linearly Recurrent Sequence by Alin Bostan and Ryuhei Mori>[coefficient-extraction algorithm and parity identity]{ref}