Calculating Fibonacci numbers with matrices

fib3.cpp

/* Fibonacci Calculation using Matrices
 * Ameer Ayoub <ameer.ayoub@gmail.com>
 * Jun 13, 2011
 */
#include <iostream>
#include <math.h>
using namespace std;

const int fib_matrix_size = 2;

void fib_multiply_matrix(int fm1[][fib_matrix_size],
	 	int fm2[][fib_matrix_size], 
		int fmr[][fib_matrix_size]){
	/* Performs fib_matrix_size * fib_matrix_size matrix
	 * multiplication on the input matrices, putting the
	 * result into fmr (fib_matrix_result)
	 */
	fmr[0][0] = fm1[0][0] * fm2[0][0] + fm1[0][1] * fm2[1][0];
	fmr[0][1] = fm1[0][0] * fm2[0][1] + fm1[0][1] * fm2[1][1];
	fmr[1][0] = fm1[1][0] * fm2[0][0] + fm1[1][1] * fm2[1][0];
	fmr[1][1] = fm1[1][0] * fm2[0][1] + fm1[1][1] * fm2[1][1];
}

void fib_copy_matrix(int m1[][fib_matrix_size], int m2[][fib_matrix_size]){
	/* copies from m2 into m1, like strcpy param order */
	for(int i = 0; i < fib_matrix_size; i++)
		for(int j = 0; j < fib_matrix_size; j++)
			m1[i][j] = m2[i][j];
}

double log2(double x){
	return log10(x) / log10(2.0);
}

int calc_fib_matrix(int fmx[][fib_matrix_size], int n){
	int exp = (int)log2(n);
	int diff = n - exp;
	int fmir1[fib_matrix_size][fib_matrix_size];
	int fmir2[fib_matrix_size][fib_matrix_size];
	fib_copy_matrix(fmir2, fmx);
	for(;exp != 1; exp /= 2){
		fib_multiply_matrix(fmir2, fmir2, fmir1);
		fib_copy_matrix(fmir2, fmir1);
	}
	for(int i = 0; i < diff; ++i){
		// We can probably reduce this
		fib_multiply_matrix(fmir2, fmx, fmir1);
		fib_copy_matrix(fmir2, fmir1);
	}
	return fmir2[0][1];
}

int rfib(int n){
	return (n <= 1) ? n : rfib(n-1)+rfib(n-2);
}

int main(){
	int fm[fib_matrix_size][fib_matrix_size] = {{1, 1}, {1, 0}};
	int f6 = calc_fib_matrix(fm, 6);
	int rf6 = rfib(6);
	cout << "6th Fibonacci Number: " << f6 << " (expected: " << rf6 << ")" << endl;
	return 0;
}