Where f(0) = 0, f(1) = 1, f(2) = 2. I know there is a way to solve Fibonacci using matrix explanation.

And the solution is(credit: geeksforgeeks)

#include <stdio.h>
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if (n == 0)
    return 0;
power(F, n-1);
return F[0][0];
}
void power(int F[2][2], int n)
{
if( n == 0 || n == 1)
    return;
int M[2][2] = {{1,1},{1,0}};

power(F, n/2);
multiply(F, F);

if (n%2 != 0)
    multiply(F, M);
}

void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0]   F[0][1]*M[1][0];
int y = F[0][0]*M[0][1]   F[0][1]*M[1][1];
int z = F[1][0]*M[0][0]   F[1][1]*M[1][0];
int w = F[1][0]*M[0][1]   F[1][1]*M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
int main()
{
int n = 9;
printf("%d", fib(9));
getchar();
return 0;
}

But what will be the matrix for this (F(n) = F(n-3) F(n -2)) equation?

CodePudding user response：

As far as I understand, you need a matrix to calculate generalized Tribonacci values of described kind in log(n) time.

Writing dependences we can deduce such equations

[Fn 1]   [0    Fn-1   Fn-2]    [0  1  1]   [Fn]
[Fn  ] = [Fn    0      0  ] =  [0  1  1]   [Fn]
[Fn-1]   [0    Fn-2    0  ]    [0  1  0]   [Fn-2]

                                   ^
                                 matrix 

So you can use matrix above in corresponding power with [2,1,0] column

CodePudding user response：

Matrices?

int F( int n ) {
   int a[ n   1 ];
   a[ 0 ] = 0;
   a[ 1 ] = 1;
   a[ 2 ] = 2;
   for ( int i=3; i<=n;   i )
      a[ i ] = a[ i - 3 ]   a[ i - 2 ];

   return a[ n ];
}

You can even reuse the array between calls for further gains.

int *a = NULL;
int max_n = -1;

int F( int n ) {
   if ( max_n < n ) {
      a = realloc( a, sizeof( *a ) * n 1 );
      if ( max_n < 0 ) {
         a[ 0 ] = 0;
         a[ 1 ] = 1;
         a[ 2 ] = 2;
         max_n = 2;
      }

      for ( int i=max_n 1; i<=n;   i )
         a[ i ] = a[ i - 3 ]   a[ i - 2 ];

      max_n = n;
   }

   return a[ n ];
}