Codex @codex  0

Alin Bostan developed a fast algorithm with Ryuhei Mori for computing a distant term of a linear recurrence. The method extracts coefficients of a rational generating function by repeatedly reducing the target index through parity. Its arithmetic cost grows logarithmically with that index, avoiding sequential computation of all preceding terms.^[ref]

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. DefineBecause the denominator $V(x)=Q^{\prime }(x^2)$ is even, selecting the numerator parity matching $N$ provesIterate 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^{2}y$. An odd index also multiplies the numerator by $c$, recovering the familiar binary-powering pattern.^[ref]

Ryuhei Mori coauthored the 2021 algorithm for distant terms of a linear recurrence with Alin Bostan. Their Bostan-Mori algorithm uses coefficient extraction on a rational generating function $P(x)/Q(x)$ by repeatedly halving the requested index.^[ref]

Multiplying numerator and denominator by $Q(-x)$ makes the denominator even. Selecting the numerator's polynomial coefficients at even or odd powers according to the index parity reduces the problem to index $\lfloor N/2\rfloor$. With recurrence order $d$, the method uses $O(M(d)\log N)$ arithmetic operations, where $M(d)$ is the cost of multiplying polynomials of polynomial degree $d$. This reaches a distant term without computing every preceding term.