How can we solve F(n) = F(n-3) F(n -2) equation in log(n) time?-CodePudding

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  ] =  [1  0  0]   [Fn-1]
[Fn-1]   [0    Fn-1    0  ]    [0  1  0]   [Fn-2]

                                   ^
                                 matrix

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

CodePudding user response：

You can compute this in log(n) time (arithmetic operations) without matrices, by noting that F(n) is the constant coefficient of x^n(x^2 2x) mod x^3-x-1.

It pretty much works the same as the matrix solution, except these degree-2 polynomials are a more compact representation of the particular matrices that appear in the 3x3 matrix solution, and their product can be calculated easily using 9 multiplications instead of 23-27 multiplications (depending on exactly how you're doing the 3x3 matrix multiply).

#include <stdint.h>
#include <stdio.h>

typedef struct poly_s {
    int64_t x0, x1, x2;
} poly_s;

poly_s mul(poly_s a, poly_s b) {
    return (poly_s){
        a.x0*b.x0   a.x2*b.x1   a.x1*b.x2,
        a.x1*b.x0   a.x0*b.x1   a.x2*b.x2   a.x2*b.x1   a.x1*b.x2,
        a.x2*b.x0   a.x1*b.x1   a.x0*b.x2   a.x2*b.x2
    };
}

poly_s polypow(poly_s x, int n) {
    poly_s r = {1, 0, 0};
    while(n) {
        if (n & 1) r = mul(r, x);
        x = mul(x, x);
        n >>= 1;
    }
    return r;
}

int main() {
    for (int i = 0; i < 30; i  ) {
        printf("%d: %ld\n", i, mul((poly_s){0, 2, 1}, polypow((poly_s){0, 1, 0}, i)).x0);
    }
}

Output: