Fibonacci - Divide and conquer algorithm

Question

#include <iostream>
using namespace std;

int main() {
    int i=1;
    int j=0;
    int k=0;
    int h=1;
    int t=0;
    int n;
    cin>>n;

    while (n) {
        if (n%2) {
            t=j*h;
            j=i*h+j*k+t;
            i=ik+t;
        }

        t=h*h;
        h=2*k*h+t;
        k=k*k+t;
        n=n/2;
    }

    cout<<j;
    return 0;
}

This is the fastest algorithm for Fibonacci I found on the internet. Other algorithms I understand but this one doesn't make any sense to me.

I don't see how this algorithm is related to matrix multiplication or exponentiation by squaring. Can someone explain?

Answer 1

This is the standard matrix method for calculating fibonacci numbers. Variables h, i, j and k are the four elements of a matrix. The matrix arithmetic is written out "longhand".

Answer 2

The matrix solution is to take matrix

1 1
0 1

And raise it to the power equal to the fibonacci number you want. You can do that using log(n) steps. You use the binary format of the power. At each step you multiply the matrix with itself (equivalent to multiplying the exponent by 2) and multiply witht the original matrix if the bit is 1 (equivalent to adding 1 to the exponent).

Now check again the code. The variables encode the 4 cells in the matrix and there's some inlining of the multiplication logic, but it's still the same.