# Efficient algorithm for computing any-order linear recurrences

**URL:** <https://community.wolfram.com/t/efficient-algorithm-for-computing-any-order-linear-recurrences/9416>\
**Category:** Ideas\
**Tags:** computer-science, data-science, optimization\
**Created:** [October 12, 2016, 10:38pm UTC](https://community.wolfram.com/t/efficient-algorithm-for-computing-any-order-linear-recurrences/9416 "2016-10-12T22:38:06Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![khomovskij](https://avatars.discourse-cdn.com/v4/letter/k/0ea827/32.png) [@khomovskij](https://community.wolfram.com/u/khomovskij)\
**Post date:** [October 12, 2016, 10:38pm UTC](https://community.wolfram.com/t/efficient-algorithm-for-computing-any-order-linear-recurrences/9416/1 "2016-10-12T22:38:06Z")

</div>

We present the function **AnyOrderRecurrence** to compute the **N** th 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}

```