Getting Acquainted

We're leaving the land of abstract, general solutions. Our goal is to compute these powers more quickly. Let's take a second to get acquainted.

First off, MM and all of its powers are special in that the upper right and lower left values are equal. This makes squaring MM faster than a normal matrix, because we only need to compute three values instead of four. That's already a pretty big time save. But remember, these aren't just any numbers: they're Fibonacci numbers. So we know that, because F(n+1)=F(n)+F(n−1)F(n + 1) = F(n) + F(n - 1), we can write this in terms of only two numbers: a=F(n−1)a = F(n - 1) and b=F(n)b = F(n).

Getting Acquainted

We're leaving the land of abstract, general solutions. Our goal is to compute these powers more quickly. Let's take a second to get acquainted.

First off, MM and all of its powers are special in that the upper right and lower left values are equal. This makes squaring MM faster than a normal matrix, because we only need to compute three values instead of four. That's already a pretty big time save. But remember, these aren't just any numbers: they're Fibonacci numbers. So we know that, because F(n+1)=F(n)+F(n−1)F(n + 1) = F(n) + F(n - 1), we can write this in terms of only two numbers: a=F(n−1)a = F(n - 1) and b=F(n)b = F(n).