I did implemented this code before too. Its nice and shorter than Matrix exponentiation. I have found this on wikipedia Fibonacci Numbers.

F[2*n — 1] = F[n]*F[n] + F[n — 1]^2

F[2*n] = (F[n — 1] + F[n + 1])*F[n] = (2*F[n — 1] + F[n])*F[n]

I have a marvellous way to calculate fibonacci number using only TWO lines of code :P

See here.

Nice article. I wonder if you can you somehow invent a way to calculate k-inversions faster than ? for example.

Although the observation is interesting, I don't get what relevance it has in the above implementation. I would write pretty much the same code without the realizing that each depth has at max 4 states. Could you please clarify?

Forgive me but this does not strike me as anything special. It is basically just a poor man's version of the matrix multiplication + exponentiation by squaring anyway (the computed values should be the same). Plus, you are losing the insights from linear algebra, so it will be harder for you to see the solution for less trivial recurrence relations.

Computing Fibonacci numbers using matrix multiplication requires approximately the same amount of code as your approach:

MOD = 1000000007
def mul(A,B):
    return [ [ sum(A[r][i]*B[i][c] for i in range(2))%MOD for c in range(2) ] for r in range(2) ]

def exp(A,n):
    if n==0: return [ [1,0], [0,1] ]
    C = exp(A,n//2)
    C = mul(C,C)
    return mul(A,C) if n%2 else C

n = int( input() )
print( exp( [ [0,1], [1,1] ], n )[0][1] )

(And finally, the line "#define long long long" is both ugly and a really bad habit.)

cool. but can be cooler

void fib(ll n, ll&x, ll&y){
    if(n==0){
        x = 0;
        y = 1;
        return ;
    }
     
    if(n&1){
        fib(n-1, y, x);
        y=(y+x)%mod;
    }else{
        ll a, b;
        fib(n>>1, a, b);
        y = (a*a+b*b)%mod;
        x = (a*b + a*(b-a+mod))%mod;
    }
}

answer in x. no map, time — logN.

"Let's divide n into groups by depth, you will realize a special property: Each depths only contains at most 4 values of n." some1 can explain why? I think on each depth contain 4^h values

*

I don't undertand different in two initialization:

F[0]=1; F[1]=1; cout<<f(n);
///////////////////// F[0]=1; F[1]=2; cout<<f(n-1);

Is this better(efficient) than matrix exponentiation to calculate fibonacci??

please clarify me??

How to do it when there is variation in Fibonacci series. For ex — F(n) = 2*F(n-1) + 3*F(n-2)

How can we prove the complexity of this algorithm?

i want to know how many time author spent in coma , because author of this post tell such stupid and wide known facts

This Formula has been posted in Geek for Geek, hasn't it?

Can someone explain why this code gets wrong answer if $$$ n=10^{19} $$$.
Try this nth Fibonacci problem

I’m not sure if people have said it already, but this is actually the same solution as matrix multiplication (only an optimization for the particular form of the recurrence matrix). More specifically, you may notice that matrices of form $$$F(a, b) = [[a, b], [b, a+b]]$$$ form a subring of matrices.

• $$$F(a, b) + F(a’, b’) = F(a+a’, b + b’)$$$
• $$$F(a, b) * F(a’, b’) = F(a a’ + b b’, a b’ + b (a’ + b’))$$$

You can prove the above by arithmetic. In particular, identity is $$$F(1, 0)$$$, and Fibonacci matrix is $$$F(0, 1)$$$. This means that instead of storing the $$$2x2$$$ matrix, you could store just $$$a$$$ and $$$b$$$. This explains the formula and generalizes it.

Nice approach, We can also use Golden ratio stuff but it will give approx value, as we know that ratio of two consecutive fibonacci no. is nearly equal to golden-ratio.