#include <stdio.h>
#include "numbers.h"

#define N 10000 // Largest Fibonacci number that can be computed

void Fib_loop();
void Fib_rec();
void Fib_rec_imp();

Number F[N]; // Stores Fibonacci sequence
int m = 1; // First m Fibonacci numbers have been computed


int main(int argc, char *argv[])
{
	int n;
	int method; // represents the method of computation
	Number number; // stores the nth Fibonacci number

	if (argc != 3) {
		printf("ERROR: Usage is\nFib <number> <method>\n");
		return 0;
	}

	sscanf(argv[1], "%d", &n);
	sscanf(argv[2], "%d", &method);

	set_number_size(n);

	printf("Fibonacci number #%d = ", n);

	number = allocate_space();

	if (method == 1) {
		Fib_loop(n, number);
		output_number(number);
	}
	else if (method == 2) {
		Fib_rec(n, number);
		output_number(number);
	}
	else {
		Fib_rec_imp(n);
		output_number(F[n]);
	}

	free_space(number);
}


/* Computes nth Fibonacci number using a loop and stores the
 * result in num.
 */
void Fib_loop(int n, Number num)
{
	Number F[N]; // Stores first N Fibonacci numbers

	for (int m = 0; m <= n; m++)
		F[m] = allocate_space();

	set_number(F[0], 1); // Set the first two numbers
	set_number(F[1], 1);

	for (int m = 2; m <= n; m++)
		add_numbers(F[m-1], F[m-2], F[m]);

	copy_number(num, F[n]);

	for (int m = 0; m <= n; m++)
		free_space(F[m]);
}


/* Computes nth Fibonacci number using recursion */
void Fib_rec(int n, Number num)
{
	Number num1;
	Number num2;

	if ((n == 0) || (n == 1)) { // first two numbers
		set_number(num, 1);
		return;
	}

	num1 = allocate_space();
	num2 = allocate_space();

	Fib_rec(n-1, num1);
	Fib_rec(n-2, num2);
	add_numbers(num1, num2, num);

	free_space(num1);
	free_space(num2);
}
	

/* Computes nth Fibonacci number using recursion.
 * Does not compute a number computed already.
 */
void Fib_rec_imp(int n)
{
	if ((n == 0) || (n == 1)) {
		F[n] = allocate_space();
		set_number(F[n], 1);
		return;
	}

	if (n > m) { // F[n] not computed yet

		F[n] = allocate_space();
		Fib_rec_imp(n-1);
		Fib_rec_imp(n-2);
		add_numbers(F[n-1], F[n-2], F[n]);
		m = n;
	}
}