Ronzii's Blog

Just your average geek's blog

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;
}
Advertisements

March 21, 2012 Posted by | C++ | , , , | Leave a comment

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

\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n =        \begin{pmatrix} F_{n+1} & F_n \\                        F_n     & F_{n-1} \end{pmatrix}.

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]);
}

July 9, 2011 Posted by | C++ | , , , | 4 Comments