## Project Euler Problem 2

#include <cstdio> #include <iostream> #include <numeric> #include <vector> using namespace std; int main() { vector<int> v; int a =0,b=1,c; while(1) { if(a+b>4000000) break; c = a+b; a = b; b = c; if(c%2==0) v.push_back(c); } int sum = accumulate(v.begin(),v.end(),0); cout<<sum; return 0; }

## Using Matrix Exponentiation to calculate the Nth Fibonacci Number

Fibonacci numbers have always been interesting since ancient times. The initial puzzle that Fibonacci posed was: how many pairs of rabbits will there be in one year if all of them can mate with each other. There is also a problem on SPOJ related to this.

Now this is the **recursive** solution. As you can see there are a lot of calls to the function and has exponential time complexity.

int fib(int x) { if (x == 0) return 0; if (x == 1) return 1; return fib(x-1)+fib(x-2); }

**Dynamic Programming**

The time complexity of this solution is O(n).

int fib(int n) { int a = 1, b = 1,i; for (i = 3; i <n;i++) { int c = a + b; a = b; b = c; } return b; }

**Matrix Exponetiation**

Now, there is a method to calculate the nth fibonacci number in O(log(n)) time. For this you need the basics of matrix exponentiation. Check out the following matrix

The nth fibonacci number can be found using this matrix also if we apply repeated squaring to this matrix, the solution is reduced to O(log(n))

long long fibonacci(int n) { long long fib[2][2]= {{1,1},{1,0}},ret[2][2]= {{1,0},{0,1}},tmp[2][2]= {{0,0},{0,0}}; int i,j,k; while(n) { if(n&1) { memset(tmp,0,sizeof tmp); for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++) tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j]); for(i=0; i<2; i++) for(j=0; j<2; j++) ret[i][j]=tmp[i][j]; } memset(tmp,0,sizeof tmp); for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++) tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j]); for(i=0; i<2; i++) for(j=0; j<2; j++) fib[i][j]=tmp[i][j]; n/=2; } return (ret[0][1]); }