hello, this is code to generate fibo numbers in log n time. it is giving o/p as "0", i dn't know where is error.

please help.

#include<stdio.h>



int (*(fibo)(int m[][2],int p))[2]
{
    int r[2][2]={0,0,0,0},d[2][2]={0,0,0,0};
    int (*l)[2];

    int i,j,k;

    if(p==1)
    return m; 

    l=fibo(m,p/2);



    for(i=0;i<2;i++)
    for(j=0;j<2;j++)
    {
                    r[i][j]=*((*l+i)+j);
    }     

      for(i=0;i<2;i++)
      for(j=0;j<2;j++)
      for(k=0;k<2;k++)
      {
                     d[i][j]+=(r[i][k]*r[k][j]);
      }

       for(i=0;i<2;i++)
       for(j=0;j<2;j++)
       r[i][j]=d[i][j];

         d[0][0]=d[0][1]=d[1][0]=d[1][1]=0;       

    if(p%2==0)
    {
               /*for(i=0;i<2;i++)
               for(j=0;j<2;j++)
               for(k=0;k<2;k++)
               r[i][j]+=m[i][k]+m[k][j];
               */

               return fibo(r,p/2);
    }
    else
    {
               for(i=0;i<2;i++)
               for(j=0;j<2;j++)
               for(k=0;k<2;k++)
               {
                               d[i][j]+=(r[i][k]*m[k][j]);

               }

               for(i=0;i<2;i++)
               for(j=0;j<2;j++)
               r[i][j]=d[i][j];

               return fibo(r,p/2);
    }
}



int main()
{
    int m[2][2]={
                    {1,1},
                    {1,0}
                };
              int i,j,k;  
    int f[2][2]={
                   {1,0},
                   {0,0}
                };
    int b[2][2]={0,0,0,0};

        int (*g)[2]=fibo(m,10);

        for(i=0;i<2;i++)
        for(j=0;j<2;j++)
        for(k=0;k<2;k++)
        {
              b[i][j]+=f[i][k]*(*((*g+k)+j));   
        }

     printf("%d\n",b[1][0]);
    getch();
    return 0;
}

any help is thankful.

I_m_rude
Deleted Member

Start over. I can't understand what you're doing at all. I've never seen such a complicated fibo program in my life! Most of them are about 5 lines of code.

Edited 4 Years Ago by WaltP

:'( Can you give me code to generate fibo numbers in logn time ? i am just doing that. it was done by matrix multiplication. please help me. it's a request to u now.

fibonacci series in matrix means .ur question is very strange can u eloborate what u trying to do.so it may even help me

Edited 4 Years Ago by rithish

Why complicate the procedure
I don't see any reason why you need to use 2d arrays for this, If you search the net on how this is done you'll see what I mean

@zeroloken i am evaluating fibo series in logn time. i am multiplying m matrix which is defined in main() n times by divide and conquer algorithm. so it will done in log n time. So this is what i am doing. please help now!!

@zerliken see in your post only. scroll down a little bit and you will find the matrix exponentiation method of fibo numbers. see and check it..

Okay since ya didn't answer my question I guess it's required for you to use a matrix

Now Sorry in advance because I don't have a lot on time on my hand. I'll probably be available next week but I don't think you'd want to wait that long. So I'll give a tip in debugging the prog.

to see where in your program causes the wrong computation, try to print the matrix on every line, at each pass to the function and at each loop to pinpoint exactly where the values go wrong

:'( but why others are not responding ? :(

It makes no sense to optimize fibonacci when using only standard precicions, as you can precompute the lookup table and do lookup in O(1) from the table.

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
1548008755920
2504730781961
4052739537881
6557470319842
10610209857723
17167680177565
27777890035288
44945570212853
72723460248141
117669030460994
190392490709135
308061521170129
498454011879264
806515533049393
1304969544928657
2111485077978050
3416454622906707
5527939700884757
8944394323791464
14472334024676221
23416728348467685
37889062373143906
61305790721611591
99194853094755497
160500643816367088
259695496911122585
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309
7540113804746346429
12200160415121876738

Edited 4 Years Ago by pyTony

using only standard precicions,

sir, please tell me how have u computed it in log n time ?

This article has been dead for over six months. Start a new discussion instead.