//Programmer: Alireza Shafaei
//Phi Calculation
#include <iostream>
#include <ctime>
#include <iomanip>
#include <fstream>
#include <conio.h>

using namespace std;
#define MAX 1000200 
//Maximum Decimal Place

struct bignum{
	int num[MAX];
	int len;
	bignum(){
		for(int i=0;i<MAX;i++)
			num[i]=0;
		len=0;
		//this function clears the number during initialization of it
	}
};
//a bignum structure is used to carry big number's data!

bignum ans,divi,buff,buff2,phi;
//ans div buff buff2 phi are 5 big numbers!

int DecPlace;
//used to carry decimal place data which user enters
void calc();
//this function calculates square root of 5
void multiply(bignum *in,bignum *out,int coef);
//this function multiplies Big number 'in' to coef and saves it in big number 'out'
bool isbigger(bignum *a,bignum *b);
//this function checks whether a > b or not
void diff(bignum *a,bignum *b,bignum *ans);
//this function returns | a - b | in ans which is a big number
void phifinalize();
//this function adds 1 to square root of five then divides it to 2 to calculate Phi

//this function cleans whole stored data of a BigNumber
void clean(bignum *a){
	for(int i=0;i<DecPlace+2;i++){
		a->num[i]=0;
		//for every index
	}
	a->len=0;
	//length of number must be zero
}

int main(){
	ans.num[0]=2;
	ans.len=1;
	//first number of SQRT is entered manually
	divi.num[0]=1;
	divi.len=3;
	cout<<"A.Sh Phi calculator\nbased on square root of 5\n";
	cout<<"Please enter maximum decimal place(s):";
	//Details which will be shown in the beginning of the program
	cin>>DecPlace;
	//gets decimal place data
	cout<<"\nCalculating the first "<<DecPlace<<" decimal place(s):"<<endl;
	clock_t start,end;
	start=clock();
	//Clock initialization to find overall time
	reverse(divi.num,divi.num+divi.len);
	calc();
	//SQRT(5) calculation
	cout<<"First "<<DecPlace<<" Decimal Place(s) of 5's square root is calculated"<<endl;
	phifinalize();
	//Phi calculation
	cout<<"\nPhi calculation is done!"<<endl;
	end=clock();
	//Clock stops
	double t1;
	t1=end-start;
	double dif=(t1)/CLOCKS_PER_SEC;
	cout<<"=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-"<<endl;
	for(int i=0;i<phi.len;i++){
		if(i==1)
			cout<<".";
		cout<<phi.num[phi.len-i-1];
	}
	//shows the result which is Phi
	cout<<"\n=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n";
	cout<<"Produced in "<<setprecision(3)<<fixed<<dif<<" Seconds"<<endl;
	//Shows the overall time
	cout<<"Save in a file?(y|n):";
	char in;
	cin>>in;
	if(in=='y'){
		cout<<"Enter file name:";
		string name;
		cin>>name;
		char buff[200];
		for(int i=0;i<name.length();i++){
			buff[i]=name[i];
		}
		buff[name.length()]='.';
		buff[name.length()+1]='t';
		buff[name.length()+2]='x';
		buff[name.length()+3]='t';
		buff[name.length()+4]='\0';
        ofstream fout;
		fout.open(buff);
		fout<<"Phi produced by A.Sh Phi calculator"<<endl;
		fout<<"Represnting the first "<<DecPlace<<" decimal place(s) of Phi"<<endl;
        fout<<"Produced in "<<setprecision(3)<<fixed<<dif<<" second(s)"<<endl;
		fout<<"______________________________________________________"<<endl;
		for(int i=0;i<phi.len;i++){
			if(i==1)
				fout<<".";
			fout<<phi.num[phi.len-i-1];
		}
		fout<<"\n______________________________________________________"<<endl;
		cout<<name<<".txt saved successfully!"<<endl;
	}
clock_t s,e;
time(&s);
time(&e);
//Waits for 3 seconds before closing the app
while(difftime(e,s)<3)
	time(&e);
return 0;	
}

void calc(){
	for(int found=0;found<DecPlace;found++){
	//For each decimal place to find
		buff.len=0;
		buff2.len=0;
		//Cleans first and second buffer
		multiply(&ans,&buff,20);
		//Multiplies ans to 2 and saves it in buff
		int best=0;
		while(best<9){
		//Findes best number to multply to(instead of writing Divide function :D)
			buff.num[0]=best+1;
			buff.len=buff.len;
			multiply(&buff,&buff2,best+1);
			if(isbigger(&divi,&buff2))
				best++;
			else
				break;
		}
	buff.num[0]=best;
	multiply(&buff,&buff,best);
	diff(&divi,&buff,&divi);
	reverse(divi.num,divi.num+divi.len);
	divi.len+=2;
	reverse(divi.num,divi.num+divi.len);
	reverse(ans.num,ans.num+ans.len);
	ans.num[ans.len]=best;
	ans.len++;
	reverse(ans.num,ans.num+ans.len);
	//SQRT Algorithm
	}
}

void multiply(bignum *in,bignum *out,int coef){
	//out=in*coef
	int i=0;
	if(coef==0){
		clean(out);
		out->len=1;
		return;
	}
	int temp=0;
	int len=in->len;
	while(i<len){
		out->num[i]=(in->num[i]*coef)+temp;
		temp=out->num[i]/10;
		out->num[i++]%=10;
	}
	if(i==len && temp!=0){
		out->num[i]=(in->num[i]*coef)+temp;
		temp=out->num[i]/10;
		out->num[i++]%=10;
	}
	out->len=i;
}

bool isbigger(bignum *a,bignum *b){
//checks whether  a > b or not
	if(a->len!=b->len)
		return (a->len>b->len);
	for(int i=0;i<a->len;i++)
		if(a->num[a->len-i-1]!=b->num[b->len-i-1])
			return a->num[a->len-i-1]>b->num[b->len-i-1];
	return false;
}

void balance(bignum *num,int i){
//It's used to make difference easier!
	if(num->num[i+1]==0){
		balance(num,i+1);
	}
	num->num[i+1]--;
	num->num[i]+=10;
	if(i==num->len-2 && num->num[num->len-1]==0)
		num->len--;
}

void diff(bignum *a,bignum *b,bignum *ans){
//ans=|a-b|
	bignum *a1,*a2;
	if(isbigger(a,b)){
		a1=a;
		a2=b;
	}else{
		a1=b;
		a2=a;
	}
	if(ans!=a1){
		for(int i=0;i<a->len;i++)
			ans->num[i]=a1->num[i];
		ans->len=a1->len;
	}
	for(int i=0;i<a2->len;i++){
		if(ans->num[i]<a2->num[i])
			balance(ans,i);
		ans->num[i]-=a2->num[i];
	}
	int i=0;
	while(ans->num[ans->len-i-1]==0)
		i++;
	ans->len-=i;
}

void phifinalize(){
//makes Phi
	int temp=0;
	ans.num[ans.len-1]+=1;
	phi.len=ans.len;
	for(int i=0;i<ans.len;i++){
		temp*=10;
		temp+=ans.num[ans.len-i-1];
		phi.num[phi.len-i-1]=temp/2;
		temp%=2;
	}
}