A Truly Exponential Speedup

Let's use this in our matrix exponentiation algorithm. I'm using numpy matrices so it's easier to read: note that @ is used for matrix multiplication (to distinguish it from element-wise multiplication).

We've really broken the barrier we were running into: this bad boy can handle computing F(10,000,000)F(10,000,000) without breaking a sweat! Considering it has over 2 million decimal digits, I think that's pretty impressive. One thing I want to highlight is how useful linear algebra has been already. It provides a very useful common language for all sorts of different problems—if you can phrase your problem using matrices, chances are someone's already figured out how to solve it and written the code for you. Here, just by using a matrix to write things out, we've stumbled into a massive speedup.

Now that we've gone from on the order of nn operations to compute F(n)F(n) to on the order of log⁡n\log n, let's explore some alternatives to matrix exponentiation by squaring that might shave some time off.

Code
Output
2,089,878

A Truly Exponential Speedup

Let's use this in our matrix exponentiation algorithm. I'm using numpy matrices so it's easier to read: note that @ is used for matrix multiplication (to distinguish it from element-wise multiplication).

We've really broken the barrier we were running into: this bad boy can handle computing F(10,000,000)F(10,000,000) without breaking a sweat! Considering it has over 2 million decimal digits, I think that's pretty impressive. One thing I want to highlight is how useful linear algebra has been already. It provides a very useful common language for all sorts of different problems—if you can phrase your problem using matrices, chances are someone's already figured out how to solve it and written the code for you. Here, just by using a matrix to write things out, we've stumbled into a massive speedup.

Now that we've gone from on the order of nn operations to compute F(n)F(n) to on the order of log⁡n\log n, let's explore some alternatives to matrix exponentiation by squaring that might shave some time off.

Code
Output
2,089,878