fibonacci_fast_doubling.cpp

// Fibonacci number using fast doubling method
// fib(0) = 0, fib(1) = 1
// Function returns a pair of number, fib(n),fib(n+1)
// Time complexity ---- O(log(n))


pair<int, int> fib (int n) {
    if (n == 0)
        return {0, 1};

    auto p = fib(n >> 1);
    int c = p.first * ( 2 * p.second - p.first);
    int d = ((p.first * p.first) + (p.second * p.second));
    if (n & 1)
        return {d, c + d};
    else
        return {c, d};
}