Cognitame

'I learned from my dad that when you walk in front of an audience, they are the kings and queens, and you're but the jester - and if you don't think that way, you're going to get very, very conceited.' -Jerry Lewis

Finding Fibonacci's with Strassen Algorithm

by Ethan Glover, Wed, Dec 31, 2014 - (Edited) Fri, Sep 15, 2017

Finding the nth Fibonacci number can be a taxing process for a computer. Sure a simple algorithm that calculates the numbers one by one may be linear, but what if you could increase the speed to (Theta(lgn))? This is exactly what Strassen's Algorithm can help to do, and that's what I hope to show how to do here.

Please note that today is the first time I heard of Strassen's Algorithm and I don't guarantee that my implementation here is 100% correct. I'm getting the right answers and I am sure I've completed my goal of learning this method, but if you find anything wrong, please let me know by contacting me on any of the social services listed to the left (including email, or the comment section where this was posted).

Now for the fun stuff. The method I finally came to in calculating Fibonacci numbers involves recursively squaring the matrix {1,1,1,0} n times, n being the nth Fibonacci number (starting from 1 rather than 0). To get to this I created three programs, each getting me progressively closer to my goal.

The first program simply multiplies two 2x2 matrices from user input using the Strassen Algorithm which is at the heart of the final program. I think the program can speak for itself. Matrix 1 (made up of a, b, c, d) is multiplied by Matrix 2 (e, f, g, h) to get Matrix 3 (I, j, k, l).

In order to reduce this from 8 multiplications to 7 multiplications (a small but important difference) i, j, k, and l are calculated in the complex fashion you see them being calculated in below.

Strassen Algorithm

See the full program here.

Next, I wrote a linear time program that uses this Stassen method to find the nth Fibonacci number by using a simple for loop to square the matrix n times. The implementation is basically the same as above.

Linear Strassen Fibonacci Algorithm

See the full program here.

From there, it wasn't a big jump to get to recursion. From below you can tell I had to do some moving around to keep the recursion clean. For instance, replacing e-h with elements in an array that's passed to the function. The array that is used (list) also keeps n as its first element for easier calculation (and is decremented on each function call), but again Strassen's method remains at the heart of the program.

Recursive Strassen Fibonacci Algorithm

See the full program here.