#include <iostream>
#include <vector>
#include <stdio.h>
#include <string>
using namespace std;


class BigInt{
	// Array with the parts of the big integer in little endian
	vector<int> value;
	int base;
	void add_most_significant(int);
	void add_most_significant_otherbig(BigInt*, int);
	public:
		BigInt(int begin=0, int _base=100): value({begin}), base(_base){ };
		BigInt(BigInt& other): value(other.value), base(other.base){ };
		~BigInt(){ };
		void add(int);
		void addBig(BigInt*);
		void print(ostream& output) const;
		static BigInt* fibonacci(int);
};

void BigInt::add_most_significant_otherbig(BigInt* other, int m){
	int carry = m, sum;
	for(int i = value.size(); i < other->value.size(); ++i){
		sum = other->value[i] + carry;
		value.push_back(sum % base);
		carry = sum/base;
	}
	while(carry){
		value.push_back(carry % base); 
		carry /= base;
	}
}

void BigInt::add(int a){
	int sum = 0, carry = a;
	for(int i = 0; i < value.size(); i++){
		sum = value[i] + carry;
		value[i] = sum % base;
		carry = sum/base;
	}
	if (carry)
		add_most_significant(carry);
}

void BigInt::add_most_significant(int m){
	int carry = m;
	while(carry){
		value.push_back(carry % base); 
		carry /= base;
	}
}

void BigInt::addBig(BigInt* other){
	if(base != other->base){ 	// Won't work if they have different base
		cerr << "Addition of BigInt objects with different base not implemented yet!" << endl;
		exit(1);
	}
	int sum = 0, carry = 0, i;
	for(i = 0; i < value.size() && i < other->value.size(); ++i){
		sum = value[i] + other->value[i] + carry;
		value[i] = sum % base;
		carry = sum/base;
	}
	for(; i < value.size() && carry;++i){
		sum = value[i] + carry;
		value[i] = sum % base;
		carry = sum/base;
	}
	add_most_significant_otherbig(other, carry);
}

ostream& operator<<(ostream& output, const BigInt bigint){
	bigint.print(output);
	return output;
}

void BigInt::print(ostream& output) const {
	// string of the format depends on the "size" of the base (trailing 0 in format => fill with zeros if needed when printing)
	int l_base = to_string(base-1).length();
	string format("%0" + to_string(l_base) + "d");
	
	// Begin with the most significant part: outside the loop because it doesn't need trailing zeros
	output << value[value.size() - 1];
	char* buf = new char[l_base+1];
	for(int i = value.size() - 2; i >= 0; i-- ){
		sprintf(buf, format.c_str(), value[i]);
		output << buf;
	}
	delete[] buf;
}

BigInt* BigInt::fibonacci(int n){
	if( n <= 0){
		return new BigInt(0);
	}

	BigInt* previous[] = {new BigInt(0), new BigInt(1)};
	for(int i = 2; i <= n; ++i){
		previous[i&1]->addBig(previous[(i-1)&1]);
	}
	//Result is in previous[i&1]
	// but first delete the other one: previous[!(i&1)]  -> ! will turn 0 into 1 and 1 into 0
	delete previous[!(n&1)];

	return previous[n&1];
}

int main() {
	int n = 10000;
	BigInt* bigint = BigInt::fibonacci(n);
	cout << *bigint << endl;
	delete bigint;
	return 0;
}