O(logn) Fibonacci using Matrix property

long long divide_conquer_fibonacci(long n) {
 long long i, h, j, k ,t;
 i = h = 1;
 j = k = 0;
 while( n > 0) {
     if(n % 2 == 1) {
         t = j * h;
         j = i * h + j * k + t;
         i = i * k + t;
     }
     t = h * h;
     h = 2 * k * h + t;
     k = k * k + t;
     n = (long) n / 2;
 }
 return j;
}

long long data type (-2^63-1 to 2^63-1] can hold until Fib(92).

1, 1
2, 1
3, 2
4, 3
5, 5
6, 8
7, 13
8, 21
9, 34
10, 55
11, 89
12, 144
13, 233
14, 377
15, 610
16, 987
17, 1597
18, 2584
19, 4181
20, 6765
.....
86, 420196140727489673
87, 679891637638612258
88, 1100087778366101931
89, 1779979416004714189
90, 2880067194370816120
91, 4660046610375530309
92, 7540113804746346429   ----- (19 digits)
93, -6246583658587674878  ----- (overflow)

Using the Fast exponentiation to solve linear recurrences, some similar problems follow here.

timeWatch:

#include "time.h"
unsigned int start = clock();
// .... your code
std::cout << "Time taken in millisecs: " << clock()-start;