fibo number problem

[nitin1]

#include<stdio.h>
#define MOD 100000009

#define REP(i, n) for(i = 0; i < n; ++i)

void mul(int a[2][2],int b[2][2])
{
    int i,j,k;
    int c[2][2];
    for(i=0;i<2;i++)
    {
         for(j=0;j<2;j++)
         {
                         c[i][j]=0;
                         for(k=0;k<2;k++)
                         {
                                         c[i][j]+=(a[i][k]*b[k][j]);

                         }
         }
    }                                              // matrix multiply

    i=0;j=0;

    REP(i,2)
    REP(j,2)
    b[i][j]=c[i][j];    // copying the value in back to b[][]

    return;
}

void calc(int a[2][2],int b[2][2],int p)
{
     int i,j,k;

      if(p==1)
      {
              REP(i,2)
              REP(j,2)
              b[i][j]=a[i][j];  
              return;       
      }

      if(p%2==0)
      {
              calc(a,b,p/2);
              mul(b,b);
      }
      else
      {
           calc(a,b,p/2);
             mul(b,b);
             mul(b,a);
      }

      return;
}

int main()
{
      int t[2][2]={
                     {0,1},
                     {1,1}
                };       

      int f[2][1]={
                   {1},
                   {1}             
                };
      int n=3;
      int i,j;
      int b[2][2];

      calc(t,b,n-1);


               REP(i,2) 
               REP(j,2)
      printf("%d ",b[i][j]);        

    /*  int g[2][1]={
                     {b[0][0]*f[0][0]+b[0][1]*f[1][0]},
                     {b[1][0]*f[0][0]+b[1][1]*f[1][0]}
                };      
      */
      getch();

    return 0;
}

this is a code for finding nth fibo number in logn time. I have multiplied a matrix T n-1 times. But the problem with code is that it is same output for n=3 and n=4 both. I am not able to figure out the error. thanks if you can help me in this.

Answer for n=3 and n=4 which it is giving: 1 1 1 2 which is wrong. So can you figure out where can be the problem ? And it is also giving wrong output some other cases also. I think there is some logical problem.thanks in advance.

[deceptikon]

When working out these problems, start by understanding what the expected result should be, then trace through your code in a debugger and find the place where the expected result differs from the actual result. That's where your logic error is likely to be.

Obviously this process can be difficult if you're using code you don't understand, which is why it's important to understand the problem fully and how the code goes about solving it. ;)

On a side note, there's a more elegant solution to this problem. It's described as an exercise here and solved/converted to C here:

#include <stdio.h>

long long fib_iter(long long a, long long b, long long p, long long q, int count)
{
    if (count <= 0)
        return b;

    if (count % 2 == 0) {
        long long p_next = (p * p) + (q * q);
        long long q_next = (2 * p * q) + (q * q);

        return fib_iter(a, b,  p_next,  q_next,  count / 2);
    }
    else {
        long long a_next = (b * q) + (a * q) + (a * p);
        long long b_next = (b * p) + (a * q);

        return fib_iter(a_next, b_next, p, q, count - 1);
    }
}

long long fib(int n)
{
    return fib_iter(1, 0, 0, 1, n);
}

int main(void)
{
    for (int n = 0; n < 10; ++n)
        printf("%lld ", fib(n));

    putchar('\n');

    return 0;
}

[nitin1]

hey deceptikon is it using logn time to evaluate a fibo numbers. i have traced it, but i may be wrong so that's why confirming with you ?

i don't know which GOOGLE you use :p i also search from that google.com from where you search, but i didn't get these things :-) and from where i can read the logic which is used in this ? like the terms they are using and all the logic behind this. this is an awesome and fantastic way to implement that. too easy to read! thanks please tell :)

[deceptikon]

hey deceptikon is it using logn time to evaluate a fibo numbers.

Yes. Or rather, it's O(nlogn) because I'm calculating the whole sequence. But for a single number yes, it's O(logn).

i don't know which GOOGLE you use :p

It's the special google for google-fu masters. But seriously, it's really just a matter of remembering things you've seen before, constructing a likely keyword search, and refining that search based on the results until you find something useful.

and from where i can read the logic which is used in this ?

Well...you could read the book that I linked to. The logarithmic Fibonacci algorithm is an exercise to a section on exponentiation (hint), and the exercise itself does a reasonably good job of explaining how the algorithm works.

It might also be instructive if you reverse engineered my solution to the exercise (computing p' and q' in terms of p and q), but I won't insist on it. ;) Merely tracing through the algorithm and noting the transformations to understand how it works should be sufficient.