We present the function AnyOrderRecurrence to compute the Nth term of any-order linear recurrence with less multiplications. Its running time for large N is much less than the built-in function LinearRecurrence. Mathematica. Version Number: 10.4.0.0
For example,
AbsoluteTiming[ AnyOrderRecurrence[{9, -77, 9, 90, 9, 909, 999}, {1, 1, 1, 7, 8, 88, 888}, 10000005];]
{4.04886, Null}
AbsoluteTiming[ LinearRecurrence[{1, 1, 1, 7, 8, 88, 888}, {8, -77, 9, 90, 9, 909, 999}, {10000006, 10000006}];]
{55176.7, Null}
Attachments: