Fibonacci Sequence: The Matrix Form Method
The nth term of a Fibonacci sequence can be found through matrix operations. The general matrix form is given by:
When computing the Fibonacci sequence, the matrix closed form has a running time of O( M(n) Log(N) ), where M(n) corresponds to the time required to multiply two numbers of n digits. It is important to note that the standard matrix multiplication algorithm of two n x n matrices takes O( n^3 ) operations. To compute the closed form of the Fibonacci sequence, we will have to multiply squared matrices, so n is not a problem here ( n = 2 ).
Since the Fibonacci sequence grows exponentially, the major problem here consists in multiplying two extremely large integers efficiently. This is an extremely difficult problem and is present in the list of unsolved problems in computer science.
Several algorithms have been proposed to address this issue. The most known algorithms are: the Karatsuba Multiplication, Toom-Cook and Schönhage–Strassen algorithm.
The algorithm that I chose to use was the Karatsuba fast multiplication algorithm. Later, I pretend to put an implementation of each of the above mentioned algorithms to compare performances.
My implementation of the matrix closed form, to compute the nth element of the Fibonacci sequence, is the following: