O(n) and O(log(n)) calculation of Fibonacci numbers

fibonacci.cpp

#include <cstdint>
#include <cassert>
#include <cstdio>
#include <cstring>

/*
 * Regular O(n) calculation of n-th Fibonacci number
 */
uint_fast64_t fib_linear(uint_fast64_t n)
{
    if (n < 2 ) return n;

    uint_fast64_t fn2 = 0, fn1 = 1, res;
    n--;
    while(n--){
        res = fn1 + fn2;
        fn2 = fn1;
        fn1 = res;
    }
    return res;
}

#define MULTIPLY(r_, m1_, m2_) \
    r_[0] = m1_[0]*m2_[0] + m1_[2]*m2_[1];\
    r_[1] = m1_[1]*m2_[0] + m1_[3]*m2_[1];\
    r_[2] = m1_[0]*m2_[2] + m1_[2]*m2_[3];\
    r_[3] = m1_[1]*m2_[2] + m1_[3]*m2_[3];

#define COPY(d_, s_) d_[0] = s_[0]; d_[1] = s_[1];\
                     d_[2] = s_[2]; d_[3] = s_[3]; 

/*
 * O(log(n)) calculation of n-th Fibonacci number
 * using binary exponentiation of a matrix
 * https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
 * http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Example_implementations
 */
#define Integer typename
template<Integer A, Integer N>
A fib_log(N n)
{
    if (n < 2) return A(n);

    n--;
    /* [2x2] marix 
     * | a  b |
     * | c  d |
     *
     * is represented by array [a, c, b, d]
     */
    A res[4] = {1, 0, 0, 1};
    A mx[4] = {1, 1, 1, 0};
    A tmp[4] = {0};
    while(n){
        if (n & 1UL){
            MULTIPLY(tmp, res, mx);
            COPY(res, tmp);
        }
        MULTIPLY(tmp, mx, mx);
        COPY(mx, tmp);
        n >>= 1; 
    }
    return res[0];
}

int main(void)
{
    assert(fib_linear(20) == 6765);
    printf("%lu\n", fib_linear(20));

    for (int i = 0; i < 45; i++) {
        auto val = fib_log<uint_fast64_t, int>(i);
        printf("%lu\n", val );
        assert(val == fib_linear(i));
    }


    return 0;
}