/******************************************************
Sean Heber  (sean@fifthace.com)
http://www.bigzaphod.org/fibonacci/
September, 2006
License: public domain
******************************************************/

#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <sstream>
#include <stdlib.h>
using namespace std;

template <class T>
string to_string( const T& val )
{
        ostringstream buffer;
        buffer << val;
        return buffer.str();
}

//#define USE_64BIT_MATH
#ifdef USE_64BIT_MATH
	typedef uint64_t uint_t;
	typedef uint32_t digit_t;
	const uint_t BASE = 0xffffffffL;
	const uint_t STRBASE10 = 1000000000;
#else
	typedef uint32_t uint_t;
	typedef uint16_t digit_t;
	const uint_t BASE = 65535;
	const uint_t STRBASE10 = 10000;
#endif

class Number
{
	typedef vector<digit_t> dvt;
	dvt p;
	bool neg;

	void zero()			{ neg = false; p.clear(); }
	bool is_zero() const		{ return p.empty() || (p.size() == 1 && p.back() == 0); }
	void trim( dvt& p ) const	{ while( !p.empty() && p.back() == 0 ) p.pop_back(); }

	uint_t add( const dvt& v, dvt& u, const dvt::size_type lsd=0, dvt::size_type len=0 ) const {
		uint_t k = 0;
		if( len == 0 ) len = u.size();
		for( dvt::size_type j = 0; j < max(v.size(),len); j++ ) {
			const dvt::size_type uindex = lsd + j;
			const uint_t d = (uint_t)(j<len? u[uindex]: 0) + (uint_t)(j<v.size()? v[j]: 0) + k;
			k = d / BASE;
			u[uindex] = d % BASE;
		}

		return k;
	}

	bool subtract( const dvt& v, dvt& u, const dvt::size_type lsd=0, dvt::size_type len=0 ) const {
		uint_t k = 1;
		if( len == 0 ) len = u.size();
		for( dvt::size_type j = 0; j < max(v.size(),len); j++ ) {
			const dvt::size_type uindex = j + lsd;
			const uint_t d = k + (uint_t)(j<len? u[uindex]: 0) - (uint_t)(j<v.size()? v[j]: 0) + (BASE-1);
			k = d / BASE;
			u[uindex] = d % BASE;
		}
		return k == 0;	// true if there's a carry
	}

	// v == divsor,  u == dividend(this),  returns remainder
	// u = (int)(u / v)
	Number div( const Number& in ) {
		if( in.is_zero() ) throw( "div() :: division by zero" );
		if( is_zero() ) return Number();	// easy case - 0/anything == 0.

		dvt u = p;
		dvt v = in.p;
		dvt q;
		const dvt::size_type n = v.size();
		const dvt::size_type m = u.size() - n;
		q.resize( m+1, 0 );

		// D1 - normalize
		const uint_t d = (BASE-1) / (uint_t)(v[n-1]);
		u.push_back( 0 );
		if( d != 1 ) single_mult( u, d );
		single_mult( v, d );		// part of D1

		if( u.size() >= v.size() ) {
			// D2
			for( dvt::size_type j = m; ; j-- ) {
				// D3 - calc qh
				const uint_t t = (uint_t)u[j+n] * BASE + (uint_t)u[j+n-1];
				uint_t qh = t / (uint_t)v[n-1];
				uint_t rh = t % (uint_t)v[n-1];

				rh--; 

				while( (qh == BASE) || ((qh*(uint_t)v[n-2]) > (BASE*rh + (uint_t)u[j+n-2])) ) {
					qh--;
					rh += (uint_t)v[n-1];
					if( rh > BASE ) continue;
					break;
				}

				// D4 - mult and subtract
				dvt temp = v;
				single_mult( temp, qh );
				bool wasneg = subtract(temp, u, j, n+1);

				// D5
				q[j] = qh;

				// D6
				if( wasneg ) {
					q[j]--;
					add( v, u, j, n+j+1 );
				}

				// D7
				if( j == 0 ) break;
			}
		}

		p = q;

		// D8 - unnormalize
		Number rem;
		rem.p.resize( n, 0 );
		for( dvt::size_type i=0; i<n; i++ ) { rem.p[i] = u[i]; }
		single_div( rem.p, d );

		trim(p);
		trim(rem.p);
		return rem;
	}

	uint_t single_div( dvt& u, uint_t d ) const {
		uint_t r = 0;
		for( dvt::size_type j = u.size()-1; ; j-- ) {
			const uint_t t = (r * BASE) + (uint_t)u[j];
			u[j] = t / d;
			r = t % d;
			if( j == 0 ) break;
		}
		return r;
	}

	uint_t single_mult( dvt& u, uint_t d ) const {
		uint_t k = 0;
		for( dvt::size_type i = 0; i < u.size(); i++ ) {
			const uint_t t = (uint_t)u[i] * d + k;
			k = t / BASE;
			u[i] = t % BASE;
		}
		return k;
	}

public:
	Number()			{ zero(); }
	Number( const Number& n )	{ *this = n; }
	Number( uint_t n )		{ *this = n; }

	Number& operator=( const Number& n ) {
		p = n.p;
		neg = n.neg;
		return *this;
	}

	Number& operator=( uint_t n ) {
		zero();
		while( n ) {
			p.push_back( n % BASE );
			n /= BASE;
		}
		return *this;
	}

	Number& operator++() 				{ return (*this += 1); }
	Number operator++(int) 				{ Number c = *this; ++(*this); return c; }
	Number operator+( const Number& in ) const	{ Number a = *this; a += in; return a; }
	Number& operator+=( const Number& in )		{
		if( is_zero() ) {
			*this = in;
		} else if( !in.is_zero() ) {
			p.resize( max(p.size(),in.p.size()), 0 );
			uint_t k = add( in.p, p );
			if( k ) p.push_back(k);
		}
		return *this;
	}

	Number& operator-() 				{ neg = !neg; return *this; }
	Number operator-( const Number& in ) const 	{ Number a = *this; a -= in; return a; }
	Number& operator-=( const Number& in )		{
		if( in.is_zero() )	return *this;
		if( is_zero() )		return -(Number(in));
		dvt temp = p;
		if( subtract(in.p,temp) ) {
			temp = in.p;
			subtract( p, temp );
			neg = true;
		}
		p = temp;
		trim(p);
		return *this;
	}

	Number& operator*=( const Number& n )	{ return (*this = *this * n); }
	Number operator*( const Number& in ) const {
		Number w;

		if( !(is_zero() || in.is_zero()) ) {
			const dvt& u( p.size() <= in.p.size()? p: in.p );
			const dvt& v( p.size() > in.p.size()? p: in.p );
			const dvt::size_type m = u.size();
			const dvt::size_type n = v.size();

			w.p.resize( m+n, 0 );

			for( dvt::size_type j = 0; j < n; j++ ) {   // M6
				if( v[j] == 0 ) {
					// M2
					w.p[j+m] = 0;
				} else {
					// M3
					uint_t k = 0;
					for( dvt::size_type i = 0; i < m; i++ ) {	// M4
						const uint_t t = (uint_t)u[i] * (uint_t)v[j] + (uint_t)w.p[i+j] + k;
						k = t / BASE;
						w.p[i+j] = t % BASE;
					}

					w.p[j+m] = k;
				}
			}

			trim(w.p);
		}

		return w;
	}

	Number& operator/=( const Number& n )		{ div(n); return *this; }
	Number operator/( const Number& n ) const 	{ Number a = *this; a.div(n); return a; }
	Number& operator%=( const Number& n ) 		{ return (*this = *this % n); }
	Number operator%( const Number& n ) const 	{ Number a = *this; return a.div(n); }

	operator bool() const				{ return is_zero(); }

	operator string() const { return str(); }
	string str() const {
		if( is_zero() ) return "0";

		string str;
		dvt c = p;
		const string::size_type digits = to_string( STRBASE10 ).length() - 1;

		while( !c.empty() ) {
			string r = to_string( single_div(c,STRBASE10) );
			trim( c );
			if( !c.empty() ) { for( string::size_type z=0; z<r.length()-digits; z++ ) r = "0" + r; }
			str = r + str;
		}

		if( neg ) str = "-" + str;
		return str;
	}

	friend ostream& operator<<( ostream& os, const Number& n ) {
		os << n.str();
		return os;
	}

	uint32_t elements() const { return p.size(); }
	uint32_t bytes() const { return p.capacity() * sizeof(digit_t); }
	bool negative() const { return neg; }
};


void print_fib( uint32_t to ) {
	Number a( 0 );
	Number b( 1 );
	uint32_t counter = 0;

	for( ;; )
	{
		if( counter == to ) {
			cout << a << endl << "ELEMENTS: " << a.elements() << endl << "BYTES: " << a.bytes() << endl;
			break;
		}
		counter++;

		Number c = a + b;
		a = b;
		b = c;
	}
}


int main()
{
	print_fib( 10000000 );
	return 0;
}