ackermann.c

#include <stdio.h>
#include <stdlib.h>

#ifdef _MSC_VER
    unsigned long __stdcall GetTickCount(void);
#else
#	include <sys/time.h>

	unsigned long GetTickCount(void)
	{
		struct timeval tv;
		if(gettimeofday(&tv, NULL) != 0)
				return 0;

		return (unsigned long)((tv.tv_sec * 1000) + (tv.tv_usec / 1000));
	}
#endif

static unsigned int calls;

unsigned int naive_ackermann(unsigned int m, unsigned int n) {
	calls++;
	if (m == 0)
	return n + 1;
	else if (n == 0)
	return naive_ackermann(m - 1, 1);
	else
	return naive_ackermann(m - 1, naive_ackermann(m, n - 1));
}

unsigned int iterative_ackermann(unsigned int m, unsigned int n) {
	calls++;
	while (m != 0) {
		if (n == 0) {
			n = 1;
		} else {
			n = iterative_ackermann(m, n - 1);
		}
		m--;
	}
	return n + 1;
}

int main(int argc, char* argv[]) {
	unsigned int m = 3, n = 12, result;
	unsigned long tA, tB;

	calls = 0;
	tA = GetTickCount();
	result = naive_ackermann(m, n);
	tB = GetTickCount();
	printf("Native: %u (%u calls)\n", result, calls);
	printf("Ticks: %lu\n\n", tB - tA);

	calls = 0;
	tA = GetTickCount();
	result = iterative_ackermann(m, n);
	tB = GetTickCount();
	printf("Iterative: %u (%u calls)\n", result, calls);
	printf("Ticks: %lu\n\n", tB - tA);
	printf("Press any key...");
	getchar();
	return 0;
}