= Ryuhei Mori
{c}
<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.<A Simple and Fast Algorithm for Computing the N-th Term of a Linearly Recurrent Sequence by Alin Bostan and Ryuhei Mori>[§2 and Algorithm1]{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.
Back to article page
