Computing Fibonacci NumbersBreaking Out the Big Guns: Applying Linear Algebra
We've essentially exhausted the speed gains we can get with our current approach. Lucky for us, computing a specific Fibonacci number doesn't actually require computing all of the previous ones! Our need for speed can only be satiated by completely changing our approach.
Consider other sequences besides the Fibonacci sequence that satisfy the recurrence equation . For example, another sequence could start 3, 1, 4, 5, 9, etc. I'll note two facts about these sequences:
- Multiplying all of the values in the sequence by a constant preserves the recurrence. For example, the sequence 0, 2, 2, 4, 6, 10, ... is the Fibonacci sequence doubled, and it obeys the rule as well.
- Adding two sequences to each other produces another valid sequence. For example, we can add the Fibonacci sequence to the one that started 3, 1, 4, ... to get 3, 2, 5, 7, 12, ..., and this new sequence still obeys the rule.
These two properties—preserving constant multiplication and preserving addition—have a special name. We say that the Fibonacci recurrence is linear. If you have two lines, and you add them together (e.g., applying this operation), you still get a line, hence the name.
Linearity rocks. Linear algebra provides us a fantastically useful set of tools that let us analyze the sequence in more detail, and this will lead us to far more efficient approaches for computing .
(A note to the reader: I'll be moving pretty quickly through the basics of linear algebra so as not to bore people who are more familiar with it, so if this is completely new to you it might be a little overwhelming. 3blue1brown has excellent resources for deepening your understanding if you want that, and if you're interested in programming and/or math it's highly recommended study material.)
Breaking Out the Big Guns: Applying Linear Algebra
We've essentially exhausted the speed gains we can get with our current approach. Lucky for us, computing a specific Fibonacci number doesn't actually require computing all of the previous ones! Our need for speed can only be satiated by completely changing our approach.
Consider other sequences besides the Fibonacci sequence that satisfy the recurrence equation . For example, another sequence could start 3, 1, 4, 5, 9, etc. I'll note two facts about these sequences:
- Multiplying all of the values in the sequence by a constant preserves the recurrence. For example, the sequence 0, 2, 2, 4, 6, 10, ... is the Fibonacci sequence doubled, and it obeys the rule as well.
- Adding two sequences to each other produces another valid sequence. For example, we can add the Fibonacci sequence to the one that started 3, 1, 4, ... to get 3, 2, 5, 7, 12, ..., and this new sequence still obeys the rule.
These two properties—preserving constant multiplication and preserving addition—have a special name. We say that the Fibonacci recurrence is linear. If you have two lines, and you add them together (e.g., applying this operation), you still get a line, hence the name.
Linearity rocks. Linear algebra provides us a fantastically useful set of tools that let us analyze the sequence in more detail, and this will lead us to far more efficient approaches for computing .
(A note to the reader: I'll be moving pretty quickly through the basics of linear algebra so as not to bore people who are more familiar with it, so if this is completely new to you it might be a little overwhelming. 3blue1brown has excellent resources for deepening your understanding if you want that, and if you're interested in programming and/or math it's highly recommended study material.)