💎 Snippets

Fibonacci using Matrix Exponentiation

The Fibonacci recurrence can be written as

$$\left[\begin{array}{c}F(n)\\ F(n-1)\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{n-1}\left[\begin{array}{c}F(1)\\ F(0)\end{array}\right].$$

Since

$$\left[\begin{array}{c}F(1)\\ F(0)\end{array}\right]=\left[\begin{array}{c}1\\ 0\end{array}\right],$$

After computing $M^{n-1}$, the answer is simply the element at position $(0,0)$.

long long fibonacci(long long n) {
    if (n == 0) return 0;
 
    Matrix M(2);
    M.a = {
        {1, 1},
        {1, 0}
    };
 
    Matrix res = matrix_power(M, n - 1);
    return res.a[0][0];
}