O(log(N)) Fibonacci computation

fibs.cpp

/* Computation of the Nth Fibonacci number in O(log(N)) time.
 *
 * clang++ -o fibs -pedantic -Wall fibs.cpp
 *
 * The program prints a sequence of lines each containing three values: an
 * integer index, the Fibonacci number at that index, and the number of matrix
 * multiplications required to compute the number.
 *
 * This code uses an arbitrary-precision integer type from Boost, just because
 * it's fun to play with big numbers, but you can remove the #include, and
 * typedef long cpp_int (or some other big integer type) if you don't Boost.
 */

#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;

typedef cpp_int matrix[2][2];

const matrix identity = {
    { 1, 0 },
    { 0, 1 }
};

void copy(matrix r, const matrix m)
{
    r[0][0] = m[0][0];
    r[0][1] = m[0][1];
    r[1][0] = m[1][0];
    r[1][1] = m[1][1];
}

int mult_count = 0;

void mult(matrix r, const matrix m)
{
    matrix t = {
      { r[0][0] * m[0][0] + r[0][1] * m[1][0],
        r[0][0] * m[0][1] + r[0][1] * m[1][1] },
      { r[1][0] * m[0][0] + r[1][1] * m[1][0],
        r[1][0] * m[0][1] + r[1][1] * m[1][1] }
    };
    copy(r, t);
    ++mult_count;
}

void pow(matrix r, int n)
{
    if (n == 0) {
        copy(r, identity);
    } else if (n == 1) {
        /* Do nothing. */
    } else if (n % 2 == 0) {
        pow(r, n / 2);
        mult(r, r);
    } else {
        matrix t;
        copy(t, r);
        pow(r, n - 1);
        mult(r, t);
    }
}

const matrix seed = {
    { 0, 0 },
    { 0, 1 }
};

const matrix factor = {
    { 0, 1 },
    { 1, 1 }
};

cpp_int fib(int n)
{
    matrix a, r;
    copy(a, seed);
    copy(r, factor);
    pow(r, n);
    mult(a, r);
    return a[1][0];
}

#include <iostream>

int main()
{
    for (int i = 0; i < 100; ++i) {
        mult_count = 0;
        cpp_int v = fib(i);
        std::cout << i << '\t' << v << '\t' << mult_count << '\n';
    }
}