Calculating Fibonacci series

Formal Definition : The Fibonacci series is described recursively as:
                                       f(0) = 0, f(1) = 1
                                       f(n) = f(n-2) + f(n-1) if n>1
giving 0,1,1,2,3,5,8,13,21,34,55,89,144,....

Naive method : Just go on calculating blindly. There is a simple recursive solution. As the definition itself is recursive, to think it as it is much simpler.

Pseudo code:

Fib(n):
    if n < 2:
        return n
    else :
        return Fib(n-1) + Fib(n-2)

Time Complexity : O(Fib(n))
Space Complexity : O(Fib(n)) (may overflow recursion depth in large numbers)

That's all. It is the most simple way to do it.
Explanation:

This is how the recursion calls look like. But observe that Fib(2) , Fib(3) , Fib(1) , Fib(0) are called multiple times resulting into redundancy.
To over come this problem we can store the values that were calculated and use them later.

pseudo code:

Fib(n):
    if db[n] != NULL:
        return db[n]
    else:
        db[n] = Fib(n-1) + Fib(n-2)
        return db[n]

Time Complexity : O(n)
Space Complexity : O(n)

Explanation:

Now the Fib(1) is not required for left Fib(2) and Fib(4) does not calls Fib(3) and Fib(2) as they are already calculated. Thus reducing precious operation. The naive method uses 13 calls for calculating Fib(5) (or 8 terminal calls i.e. the leaves of the tree) which are themselves Fibonacci numbers but the optimised method just used 5 steps and got Fib(i) : i belongs to [1,5].

You may not believe but this was a simple example of Dynamic Programming paradigm. This involves brute force with some sense.

another implementation (Non-recursive) would be:

Fib(n):

    db = [0,1]
    for i in [2..n]:
        db[i] = db[i-1] + db[i-2]
    return db[n]

Simple enough to understand. :D

The actual Problem arises when n also rises to lengths such as n = 10^16. now how would you get the term. Doing a Linear time solution would not suffice. A general notion is that if the limit rises above 10^6 we generally think of a log(N) solution.So we dig in a little bit.

Pop fact: Did you know about an irrational number phi or the golden ratio



This is to do with some ratio mumbo-jumbo... But we find an interesting property here with Fibonacci numbers.

These relations can be used to prove almost all the identities that involve Fibonacci numbers.

But for our concern we were calculating all the numbers previous to our required number. How about if we could just find the required number and save lots of operations. Let us talk about a simple matrix.

Now we can see that F(n) A = F(n+1) .  and A^2 = F(2) taking terms from 1,2,3,5,8,13,..

thus we can conclude that F(n) = A^n. This is again a linear time operation, but we need faster. Remember the previous post on Binary Exponentiation. That will help on logarithmic complexity.

Pseudo Code:

Fib(n):
    A = [[1,1],[1,0]]
    F = [[1,0],[0,1]]
    while n>0:
        if n%2==1:
            F = F*A
        A = A*A
        n = n/2
    return F[0][0]

Python Implementation :

def mul(x,y):
    lst = [[0,0],[0,0]]
    lst[0][0] = x[0][0]*y[0][0] + x[0][1]*y[1][0]
    lst[0][1] = x[0][0]*y[0][1] + x[0][1]*y[1][1]
    lst[1][0] = x[1][0]*y[0][0] + x[1][1]*y[1][0]
    lst[1][1] = x[1][0]*y[0][1] + x[1][1]*y[1][1]
    return lst
def Fib(n):
    a = [[1,0],[0,1]]
    d = [[1,1],[1,0]]
    while n:
        if n&1:
            a = mul(a, d)
        d = mul(d,d)
        n >>= 1
    return a[0][0]

Most of the competitive programming questions are logic based and not on number crunching. So you would not find normally to get Fib(10^18) but you may find Fib(10^18) (mod N). Go ahead and just add a modulo operator in the mul(x,y) function to each multiplication and we are done.

Time Complexity : O(log(N))

Space Complexity : O(1)