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]
New to topics? Read the docs here!