Efficiently Evaluating Recursively Defined Functions
In this blog post, I will share a technique I have used in the past to evaluate linear recurrence relations efficiently using a little bit of linear algebra. As a motivating example, assume you have a sequence of numbers that you want to know more about: 1, 2, 3, 7, 24, 100, 448, 2051, 9444, 43549, 200889, 926770, 4275598, 19725314, 91002117, 419835526. Can you spot a pattern (hint: it's a 3rd order linear recurrence relation with constant term and a dependence on \( n \), the index into the sequence)? Once you figure it out, check out my other blog post on finding recurrence relations from integer sequences to see if you came up with the same recurrence relation. By this point, you have figured out \( f(0) = 1 \), \( f(1) = 2 \), \( f(2) = 3 \), and \( f(n) = 5 f(n-1) - 2f(n-2) + f(n-3) - 2n + 1 \) for \( n \geq 3 \). Now let's say I want top compute the last \( 8 \) digits of \( f(10^{18}) \). A naive solution would be to write a for loop, but that would many orders