An Efficient Formula for Linear Recurrences
Author:
- 1 February 1985
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 14 (1) , 106-112
Abstract
The solutions to a scalar, homogeneous, constant-coefficient, linear recurrence are expressible in terms of the powers of a companion matrix. We show how to compute these powers efficiently via polynomial multiplication. The result is a simple expression for the solution, which does not involve the characteristic roots and which is valid for any module over any commutative ring. The formula yields the nth term of the solution to a kth order recurrence with $O(\mu (k) \cdot \log n)$ arithmetic operations, where $\mu (k)$ is the total number of arithmetic operations required to multiply two polynomials of degree $k - 1$. Thus if the ring supports a fast Fourier transform, then $O(k \cdot \log k \cdot \log n)$ operations are sufficient to compute the nth term.
Keywords
This publication has 2 references indexed in Scilit:
- Computing Fibonacci numbers (and similarly defined functions) in log timeInformation Processing Letters, 1980
- An O(log n) algorithm for computing the nth element of the solution of a difference equationInformation Processing Letters, 1980