Three algorithms for calculating fibbonaci numbers

fibbonaci.cpp

/*
 * Source: http://fmi.wikidot.com/daa1
 */

#include <iostream>
#include <time.h>
typedef unsigned long long ull;
#define a(n) m1.pts[n]
#define b(n) m2.pts[n]

const ull MOD = 1000000000;
struct ma3x
{
	ull pts[4];
};

int fib_mod(int n)
{
	if (n == 0 || n == 1)
		return 1;

	int a, b = 1, c = 1;
	n -= 2;

	do
	{
		a = (b + c) % MOD;
		c = b;
		b = a;
	} while (n--);

	return a;
}

ull fib_naive(ull n)
{
	if (n <= 2)
		return 1;
	else return fib_naive(n - 1) + fib_naive(n - 2);

}

void multiply(ma3x&, ma3x&);
ull fib_matrix(ull n)
{
	if (n < 2)
		return 1;
	n -= 2;

	struct ma3x res = { 1,1,1,0 };
	struct ma3x m = res;
	
	while (n)
	{
		if (n % 2)
			multiply(res, m);
		n /= 2;
		multiply(m, m);
	}

	return res.pts[0];
}

void multiply(ma3x& m1, ma3x& m2)
{
	ma3x tmp = { 0,0,0,0 };

	tmp.pts[0] = (a(0)*b(0) + a(1)*b(2)) % MOD;
	tmp.pts[1] = (a(0)*b(1) + a(1)*b(3)) % MOD;
	tmp.pts[2] = (a(2)*b(0) + a(3)*b(2)) % MOD;
	tmp.pts[3] = (a(2)*b(1) + a(3)*b(3)) % MOD;
	
	for (size_t i = 0; i < 4; ++i)
		a(i) = tmp.pts[i];
}
int main()
{ 
	clock_t start, end;
	for (ull i = ULLONG_MAX - 20; i < ULLONG_MAX - 10; i++)
	{
		start = clock();
		//Changing the function to fib_mod will take about 51 secons per calculation
		std::cout << i << ". " << fib_matrix(i);
		end = clock();
		std::cout << " (" << double(end - start) / CLOCKS_PER_SEC << "sec) \n";
	}


	return 0;
}