/******************************************
Advanced Algorithm Assignment 1

	by Ming Cao
	Jan. 2002 

  This program is coded to apply the large 
  Fibonacci numbers using the algorithm based on 
  Question 3 (Exercise 7.8). 
  
  It includes an implementation of large nonnegative 
  integers, a function for multiplying 2 by 2 matrices 
  and an O(log n) function for computing the nth power 
  of a 2 by 2 matrix. 

  Two classes were defined: class Integer and class Matrix 
  for nonnegative integers and and 2 by 2 matrices, 

*******************************************/

#include <stdio.h>
#include <string.h>
#include <iostream.h>
#include <io.h>

#define MAX 100
#define MAXDIGI 100
#define MAX_SIZE 100

class Integer {
private:
	char value[MAX_SIZE];
	int Intsize;

public:
	//initializer
	Integer();
    Integer(char *);
	
	//overridding the operator = 
        Integer& operator=(const Integer);
        Integer& operator=(const int);
        Integer& operator=(const char*);

	//overridding the operator +, * and == 
        friend Integer operator+ (Integer, Integer);
        friend Integer operator* (Integer, Integer);
        friend int operator==(Integer, Integer);
		friend ostream& operator<<(ostream&, const Integer);
		int len() {return Intsize;}
		int isEven() {
			return value[0]%2 == 0; 
		}
	//Half applies the n/2
		Integer Half() {
			Integer tmp=*this;
			for(int i=Intsize-1; i>0; i--) {
			tmp.value[i-1] += (tmp.value[i]%2)*10;
			tmp.value[i] /= 2;
			}
			tmp.value[0] /= 2;
		tmp.Intsize = tmp.value[Intsize-1]==0 ? Intsize-1 : Intsize;
		return tmp;
	}   
};
 
Integer::Integer()
{
	// initializer
	memset(value,0,sizeof(char)*MAX_SIZE);
	Intsize=1;
}

Integer::Integer(char *str)
{
	memset(value, 0, MAX_SIZE*sizeof(char));
	Intsize = strlen(str);
	for (int i=Intsize;i>0;i--)value[Intsize-i]=str[i-1]-48;
}


Integer& Integer::operator= (const Integer tmp)
//operator overridiing
{
	memset(value, 0, MAX_SIZE*sizeof(char));
	Intsize=tmp.Intsize;
	for(int i=0; i<Intsize; i++) value[i]=tmp.value[i];
	return *this;
}

Integer& Integer::operator= (const int digit)
//operator overridiing
{
	int tmp = digit;
	int i=0;

	memset(value, 0, sizeof(char)*MAX_SIZE);
	do {
		value[i++] = tmp%10;
		tmp /= 10;
	} while(tmp!=0);
	Intsize=i;
	return *this;
}

Integer& Integer::operator= (const char *str)
//operator overridiing
{
	memset(value, 0, MAX_SIZE*sizeof(char));
	Intsize = strlen(str);
	for (int i=Intsize; i>0; i--) value[Intsize-i] = str[i-1]-48;
	return *this;
}

Integer operator+ (Integer A, Integer B)
//operator overridiing
{
	Integer C;
	int largest = (A.Intsize>B.Intsize ? A.Intsize : B.Intsize);
	int result=0, carry=0;

	for (int i=0; i<largest; i++) {
		result = carry +
			( (i <= (A.Intsize-1)) ? A.value[i] : 0 ) +
			( (i <= (B.Intsize-1)) ? B.value[i] : 0 );
		if (result > 9) {
			result -= 10;
			carry = 1;
		} else  carry = 0;
		C.value[i] = result;
	}
	if (carry == 1 && largest<MAX) {
		C.value[largest] = 1;
		C.Intsize = largest + 1;
	}else   C.Intsize = C.value[largest-1]==0 ? largest-1 : largest;

	return C;

}

Integer operator* (Integer A, Integer B)
//operator * overridiing
{
	Integer intTmp;
	int tmp[MAX_SIZE],tmp2=0, tmp3=0;
	int i=0, j=0, k=0;

	memset(tmp, 0, MAX_SIZE * sizeof(int));

	for(i=0; i<B.Intsize; i++) {
		for(j=0; j<A.Intsize && i+j < MAX; j++) {
			tmp2 = B.value[i] * A.value[j];
			tmp[i+j] += tmp2;
			for(k=0; tmp[i+j+k]/10>0 && i+j+k < MAX; k++) { //need carriage
				if(i+j+k+1 < MAX) tmp[i+j+k+1] += tmp[i+j+k]/10;
				tmp[i+j+k] %= 10;
			}
		}
	}
	i = A.Intsize+B.Intsize>100 ? 100 : A.Intsize+B.Intsize;
	intTmp.Intsize = tmp[i-1] == 0 ? i-1 : i; //?
	for(i=0;i<intTmp.Intsize;i++) intTmp.value[i]=tmp[i];
	return intTmp;
}

int operator== (Integer n, Integer intTmp)
//operator == overridiing
{
	Integer tmp=intTmp;
	if(n.Intsize == intTmp.Intsize) {
		for(int i=0; i<n.Intsize; i++)
			if(n.value[i] != intTmp.value[i]) return 0;
		return 1;
	}
	return 0;
}

ostream& operator<< (ostream& out, const Integer intTmp)
//operator << overriding
{
	int i;
	for (i=intTmp.Intsize; i>0; i--) out << (char)(intTmp.value[i-1]+48);
	return out;
}




/****************************** 
  Matrix definition
 *****************************/

class Matrix {
private:
	Integer m2x2[2][2];

public:
	Matrix();
	Matrix(const int A, const int B, const int C, const int D);
	Matrix& operator=(const Matrix);
        friend Matrix operator* (Matrix, Matrix);

	void print() {
		cout<<endl<<m2x2[0][0]<<"\t"<<m2x2[0][1]<<endl;
		cout<<m2x2[1][0]<<"\t"<<m2x2[1][1]<<endl<<endl;
	}
	void print_final() {
 		cout<<"digits in f(n+1): "<<m2x2[1][1].len()<<endl;
		cout<<"f( n )="<<m2x2[0][1]<<endl;
		cout<<"f(n+1)="<<m2x2[1][1]<<endl<<endl;
	}
};

Matrix::Matrix()
{
	for(int i=0; i<2; i++)
		for(int j=0; j<2; j++) m2x2[i][j]=0;
}

Matrix::Matrix(const int a, const int b, const int c, const int d)
{
	m2x2[0][0]=a; 
	m2x2[0][1]=b; 
	m2x2[1][0]=c; 
	m2x2[1][1]=d;
}

Matrix& Matrix::operator= (const Matrix A)
{
	for (int i=0; i<2; i++) 
		for (int j=0; j<2; j++) m2x2[i][j]=A.m2x2[i][j];
	return *this;
}


void matrixMultiply2x2(Integer C[][2], Integer A[][2], Integer B[][2])
{
	int i,j,k;
	for(i=0; i<2; i++) //row #
		for(j=0; j<2; j++) {//col #
			C[i][j] = 0;
			for(k=0; k<2; k++) C[i][j] = C[i][j] + A[i][k] * B[k][j];
		}
}

Matrix operator* (Matrix A, Matrix B)
{
	Matrix C;
	matrixMultiply2x2(C.m2x2, A.m2x2, B.m2x2);
	return C;
}


Matrix MAT1(1,0,0,1);
Matrix MAT2(0,1,1,1);

Integer intInit0("0");
Integer intOne ("1");

/*************************************************** 

Function power() applies Matrix A powered by n.

*****************************************************/
Matrix power(Integer n)
{
	Matrix pow;
	if (n==intInit0) return MAT1;
	if (n==intOne) return MAT2;
	pow = power(n.Half());
	if (n.isEven()) return pow*pow;
	else return pow*pow*MAT2;
}


int main()
{

	Integer Fab; //define a fab number container
	Matrix F; // define a Fab computing seed
	char n[MAXDIGI]; // max input of 100 digits;
	cout<<"Please enter (press -1 to quit):"<<endl;
	while(scanf("%s",n)) 
	{
		// repeatedly get digits and output fab numbers.
		if(strcmp(n,"-1")==0) break;
		Fab=n;
		F = power(Fab);
		cout << "Fab=" << Fab;
		F.print_final();
		cout<<"Please enter (press -1 to quit): "<<endl;

	}
	cout<<"thanks ... bye ..."<<endl;
	return 0;
}