fibo number calculation(large)

hi....

Let F be the matrix
1 1
1 0
Then F^n (2x2 matrix multiplication) equals
F(n+1) F(n)
F(n)   F(n-1)
because:
(F(n+1) F(n)  ) (1 1) = ( F(n+1)+F(n)   F(n+1))
(F(n)   F(n-1)) (1 0) = ( F(n)+F(n-1)   F(n)  )

Can anybody tell me or give me the hint that how to develop this code. In this first problem is that 2-D martix return which i never done. Secondly, give me hints or link from which i can learn how to code these types of codes(2-D return and all). This is a method to calculate nth fibo number in logn time. here , F is a matrix and which is multiplied n-1 times to calculate f(n)th term.And this multiplication is done in exponentiation by squaring or say, Divide and conquer method, don't think that this is my homeowrk , it is part of my learning and want your help. thanks in advance.

[np complete]

No you can't pass a 2D array in function, but you can return a pointer pointing to your 2D array through which you can then access the elements from the calling function.

Also what about using the fibonacci formula (Closed form) for calculating n-th term, which can be found by solving this recurrsion f(n) = f(n-1) + f(n-2).

yes, f(n-1)+ f(n-2). how to implement that ?

[deceptikon]

http://www.ics.uci.edu/~eppstein/161/960109.html

That should help you boil it down to the task of handling matrix multiplication.

[rubberman]

The Fibonacci sequence. It is as np_complete said, with the addition that by definition Fib(0) == 0, Fib(1) == 1.

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

[deceptikon]

The Fibonacci sequence. It is as np_complete said, with the addition that by definition Fib(0) == 0, Fib(1) == 1.

It's been established that nitin is going for the O(log n) approach using matrix exponentiation. I think (hope!) he already understands the "usual" implementation.

yeah.. I have already found the fibo numbers using the DP, Normal recusrion,Dp recursion. All are O(n) and as James sir guessed, I understand all these ways nicely. But , I want to do it in O(logn) which is possible through matrix exponentiation.

Secondly, james sir, the link you have given have all the methods explained nicely, but matrix method is not well explained. sorry. :( thanks in advance to you.

[deceptikon]

but matrix method is not well explained

Then I'd wager you need to focus on understanding matrix multiplication independent of calculating fibonacci numbers, because that's really all it is. The given algorithm in that link (converted to actual C) is just this:

void fib_r(int n, long mat[2][2])
{
    long f[2][2] = {{1, 1}, {1, 0}};
    long tmp[2][2];

    if (n > 1) {
        fib_r(n / 2, mat);
        fib_multiply(tmp, mat, mat);
        fib_copy(mat, tmp);
    }

    if (n % 2) {
        fib_multiply(tmp, mat, f);
        fib_copy(mat, tmp);
    }
}

long fib(int n)
{
    long mat[2][2] = {{1, 0}, {0, 1}};

    fib_r(n - 1, mat);

    return mat[0][0];
}

Another way to do it without recursion might look like this:

long fib(int n)
{
    long f[2][2] = {{1, 1}, {1, 0}};
    long mat[2][2] = {{1, 0}, {0, 1}};
    long tmp[2][2];

    for (; n; n /= 2) {
        if (n % 2) {
            fib_multiply(tmp, mat, f);
            fib_copy(mat, tmp);
        }

        fib_multiply(tmp, f, f);
        fib_copy(f, tmp);
    }

    return mat[0][0];
}

In both cases the lion's share of work is done by the matrix multiplication, and understanding how that comes to the conclusion with a good paper run would be a good idea:

void fib_copy(long dst[2][2], long src[2][2])
{
    int i, j;

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++)
            dst[i][j] = src[i][j];
    }
}

void fib_multiply(long dst[2][2], long a[2][2], long b[2][2])
{
    int i, j, k;

    /* Clear the destination */
    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++)
            dst[i][j] = 0;
    }

    /* Perform the multiplication */
    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            for (k = 0; k < 2; k++)
                dst[i][j] += a[i][k] * b[k][j];
        }
    }
}