Horner's rule and the computation of linear recurrences (Q1092939)

The authors adapt existing algorithms, which use \(O(k^ 2 \log (m/k))\) time and \(O(k^ 2)\) space, for evaluating a linear difference equation \[ f_ m=a_{k-1} f_{m-1}\quad +...+\quad a_ 1 f_{m-k+1}\quad +\quad a_ 0 f_{m-k}\quad for\quad m\geq k, \] for a given \(A=(a_ 0,a_ 1,...,a_{k-1})\) and \(F=(f_ 0,f_ 1,...,f_{k-1})\), to derive an algorithm using O(k) space and same time order. Their algorithm uses Horner's scheme for calculating powers of a matrix, and their space saving comes from observing that only one column of the \(k\times k\) matrix needs to be stored. The algorithm is described in pseudo-code.