Given a K-term constant-coefficient linear recurrence for F _i, the nth solution F _n can be computed in any ring supporting a fast Fourier transform in O( k &dundot; log ( k ) log ( n ) ) time. Using “companion matrices,” the approach does not employ the standard approach using characteristic roots. The method provides a practical, efficient method for solving linear recurrences.