#include "stdio.h"
#include "math.h"
#include "string.h"
#define Base         100
#define MaxLen       504
typedef struct{
	int Sign; int Len; int Num[MaxLen+2];
}Bignum;
typedef struct {
	Bignum Q; Bignum R;
} QRData;
Bignum copyBignum(Bignum A){//複写
	static Bignum R;
	R.Sign=A.Sign; R.Len=A.Len;R.Num[0]=0;
	for(int i=1;i<=A.Len;i++)R.Num[i]=A.Num[i];
	return R;
}
Bignum intToBignum(int A){//整数値をBignumに変換
	static Bignum R;int AA=abs(A);	R.Sign=(A<0);R.Len=0;
	while(AA!=0){ R.Num[++R.Len]=AA % Base; AA/=Base;}
	return R;
}
// 最大桁位置に整数、その他を0設定
Bignum hightFigures(int Sign, int NumberOfFigures, int setValue){
	static Bignum R;int NN= NumberOfFigures;
	for(int i=1; i<=NN-1; i++) R.Num[i]=0;
	R.Num[NN] = setValue; R.Len=NN; R.Sign=Sign;
	return R;
}
// 整数配列をBignumに設定
Bignum integerArrayToBigNumber(int Sign, int num[], int N){
  static Bignum R; R.Len = N; R.Sign = Sign;  
  for(int i=1;i<=N;i++) R.Num[i] = num[i];
  return R;
}
void printBignum(Bignum A){//Bignumの印刷
	if(A.Len<=0) printf("0");
	else{
		if(A.Sign) printf("-");
		printf("%d",A.Num[A.Len]);
		for(int i=A.Len-1;i>=1;i--)
			printf("%d%d",A.Num[i]/10,A.Num[i]%10);
	}
}
int IndexOf(char str[], char C){  //文字が含まれて位置（先頭0）を検索
	int ID = 0;               //含まれていない場合-1を返却する
	for(int i=0; str[i]!=0; i++) if(str[i]==C) return i;
	return -1;  
} 
Bignum stringToBignum(char str[]){//stringをBignumに変換
	char nstr[2048]; Bignum R;R.Sign=false; int N=0;
	for(int i=0; str[i]!=0; i++) {//マイナス記号および数字以外を無視
		if(str[i]=='-') R.Sign=true;
		else if(str[i]>='0' && str[i]<='9') nstr[N++]=str[i];
	}
	int k=0, V;
	for(int i=N;i>0;i-=2){//下位から二桁ずつ変換
		if(i==1) V=nstr[0]-'0';
		else V=(nstr[i-2]-'0')*10+(nstr[i-1]-'0');
		R.Num[++k]=V;
	}
	R.Len=k; return R;
}
int bigToString(Bignum R, char str[], int Max){//Bignumを文字列に変換
	if(Max<=3) {printf("バッファは3以上を指定して下さい");return 0;}
	int M=R.Len;if(M<=0){str[0]='0';str[1]=0; return 1;}
	int N=0, V=R.Num[M]; if(R.Sign)str[N++]='-';
	if(V >= 10) str[N++] = (V / 10)+'0'; 
	if(V !=  0) str[N++] = (V % 10)+'0';
	for(int i=M-1; i>=1; i--){
		str[N++] = (R.Num[i] / 10)+'0';
		if(N>=(Max-1)) break;//バッファオーバのとき打ち切り
		str[N++] = (R.Num[i] % 10)+'0';
		if(N>=(Max-1)) break;
	}
	str[N++]=0; return N;
}
void printSeperate(Bignum A){//最上位桁を整数部,
	//それ以降を小数部とみなして5桁ずつ区切り、1行に50桁を表示
	//（π、ネイピア数(e)の計算結果表示用）
	char str[4096];	bigToString(A,str,2095);
	printf(" %c.",str[0]);
	for(int i=1, C=0;str[i];i++, C++){
		if(C % 50==0) printf("\n");
		else if(C % 5==0) printf(" ");
		printf("%c",str[i]);
	}
}
void omit(Bignum *X){//上位0の値を削除
	int N=X->Len;if(N<=0) { X->Sign=0; return;}
	while((X->Num[N])==0) N--;
	X->Len=N; if(N<=0) X->Sign=0;
}
int eq0(Bignum X){ omit(&X);return (X.Len==0);}// X==0の処理
Bignum addAbs(Bignum X, int N){//絶対値加算(小さな整数値(0〜99))加算
	static Bignum Y;Y=intToBignum(0);
	if(X.Len<=0){Y.Len=1; Y.Num[1]=N;}
	else{
		int T=X.Num[1]+N; int i=1;Y.Num[1]=T % Base;
		for(i=2;i<=X.Len;i++){
			T=(T/Base)+X.Num[i]; Y.Num[i]= T % Base;
		}
		if(T>=Base){
			if(i<MaxLen){Y.Len=X.Len+1;Y.Num[Y.Len]=1;}
			else{
				Y.Len=X.Len;Y.Num[i]=T-Base;
				printf("addAbsで桁あふれが起きました");
			}
		}
		else Y.Len=X.Len;
	}
	return Y;
}
Bignum addAbs(Bignum A, Bignum B){//Bignum同士の絶対値加算
	static Bignum X;X=intToBignum(0);
	if(A.Len<=0) return copyBignum(B);
	if(B.Len<=0) return copyBignum(A);
	int T=0,i,N1=A.Len, N2=B.Len, NN=N1;
	if(N2>NN) NN=N2;
	for(i=1;i<=NN;i++){
		if(i<=N1) T+=A.Num[i];
		if(i<=N2) T+=B.Num[i];
		if(T<Base) {X.Num[i]=T;T=0;}
		else {X.Num[i]=T-Base; T=1;}
	}
	if(T==0)X.Len=A.Len;
	else if (A.Len<MaxLen){	X.Len=A.Len+1; X.Num[i]=1;}
	else{
		X.Len=A.Len;
		printf("addAbsで桁あふれが起きました");
	}
	return X;

}
Bignum addAbs(int A, Bignum B){	return addAbs(B,A);}
Bignum Normalize(Bignum A){//omitと同処理だが副作用なし
	static Bignum X; X=intToBignum(0);int i=A.Len;
	while(A.Num[i]==0)i--;
	X.Len=i;
	for(int i=1;i<=X.Len;i++) X.Num[i]=A.Num[i];
	return X;
}
int compAbs(Bignum A,Bignum B){//絶対値の比較
	Bignum AA,BB;AA=Normalize(A), BB=Normalize(B);
	if(AA.Len>BB.Len) return 1;
	if(AA.Len<BB.Len) return -1;
	int i=AA.Len;
	while (i>0 && AA.Num[i]==BB.Num[i])i--;
	if(i==0) return 0;
	if(AA.Num[i]>BB.Num[i]) return 1;
	return -1;
}
Bignum subAbs(Bignum A, Bignum B){//絶対値減算　A >= Bのみ
	static Bignum AA,BB,X;
	if(B.Len<=0) return copyBignum(A);
	if(A.Len<=0) return copyBignum(B);
	AA=Normalize(A), BB=Normalize(B),X=intToBignum(0);
	int T=0, i;
	if(AA.Len>=BB.Len){
		for(i=1;i<=AA.Len;i++){
			T=A.Num[i]-T;
			if(i<=BB.Len) T-=BB.Num[i];
			if(T>=0){X.Num[i]=T; T=0;}
			else    {X.Num[i]=T+Base; T=1;}
		}
		X.Len=AA.Len;
		while(X.Num[X.Len]==0)X.Len--;
	}
	else T=1;
	if(T!=0) printf("subAbsで結果が負になりました");
	return X;
}
Bignum mulAbs(Bignum A, int N){//絶対値乗算(小さな整数0〜99)
	static Bignum X;X=intToBignum(0);
	if(N<=0) {X.Len=0; return X;}
	int T=0,i;
	for(i=1;i<=A.Len;i++){
		T=A.Num[i]*N+T;
		X.Num[i]=T % Base; T/=Base;
	}
	if(T==0) {X.Len=A.Len;return X;}
	if(A.Len<MaxLen){X.Len=A.Len+1; X.Num[X.Len]=T;return X;}
	printf("mulAbsで桁あふれが起きました");
	X.Len=A.Len;return X;
}
Bignum mulAbs(Bignum X,Bignum A,Bignum B){//Bignum同士の絶対値乗算
	// (X = X + A * B)
	int L, i,U,T;
	if(A.Len==0 || B.Len==0)return X;
	if(A.Len+B.Len>X.Len) L=A.Len+B.Len; else L=X.Len+1;
	if(L>MaxLen){
		printf("mulAbsで桁あふれが起きました");
		return X;
	}
	for(i=X.Len+1;i<=L;i++)X.Num[i]=0;
	for(int j=1;j<=B.Len;j++){
		U=B.Num[j];
		if(U!=0){
			T=0;
			for(i=j;i<=A.Len+j-1; i++){
				T=X.Num[i]+A.Num[i-j+1]*U+T;
				X.Num[i] = T % Base; T /= Base;
			}
			for(i=A.Len+j, T=X.Num[i]+T; T>=Base; i++, T=X.Num[i]+1) X.Num[i]=T-Base;
			X.Num[i]=T;
			if(X.Num[L]==0) X.Len=L-1;else X.Len=L;
		}
	}
	return X;
}
Bignum mulAbs(Bignum A,Bignum B){//絶対値乗算
	static Bignum X; X=intToBignum(0);
	return mulAbs(X,A,B);
}
Bignum mulAbs(int N,Bignum A){return mulAbs(A,N);}//絶対値乗算(N:0〜99)
Bignum divQRAbs(Bignum A, int N, int *R){//絶対値除算処理(N:0〜00)
	int T=0,i;static Bignum Q; Q=intToBignum(0);Q.Len=0;
	for(i=A.Len;i>=1;i--){
		T = T * Base+A.Num[i];
		Q.Num[i] = T/N; T %= N;
	}
	*R=T;Q.Len=A.Len; if(Q.Num[Q.Len]==0)Q.Len--;
	return Q;
}
//該当桁の除算値を求める（Vに被除数の上位桁の値を入れる）
//　なお、DtにQ1を乗じた結果を*Cに返却する。
int quot(int V, Bignum Dt,Bignum *C,Bignum R, int j){
	int lessThan=true, N2=Dt.Len, Q1=V/Dt.Num[N2];
	while(lessThan){// R < Q1 * Dt のとき繰り返す
		int T=0;
		for(int i=1;i<=N2;i++){// C = Q1*Dt
			T=Dt.Num[i]*Q1+T;C->Num[i]=T % Base; T/=Base;
		}
		C->Num[N2+1]=T; int K=j+N2+1; lessThan=false;
		for(int i=N2+1;i>=1;i--){// R < Q1 * Dt の比較
			if(R.Num[K]<C->Num[i]){	lessThan=true;Q1=Q1-1;}
			if(R.Num[K]!=C->Num[i])break;
			K=K-1;
		}
	}
	return Q1;
}
QRData divProc(Bignum A, Bignum B){//絶対値除算処理
	static QRData QR;//非除数を剰余に複写
	for(int i=1;i<=A.Len;i++) QR.R.Num[i]=A.Num[i];
	QR.R.Len=A.Len;
	static Bignum C;C.Len=0;// C = 0
	for(int i=1;i<=MaxLen;i++) C.Num[i]=0;
	int N2=B.Len, N=A.Len, K=N2, V=0;
	for(int j=N-N2+1; j>=0;j--){
		QR.Q.Num[j]=0;
		V=V*100+QR.R.Num[N2+j];//上位桁の値
		if(V>=B.Num[N2]){
			int Q1=quot(V, B,&C,QR.R, j), T=0, K=j+1;
			for(int i=1;i<=N2+1; i++){// 剰余からQ*B(=C)を差し引く
				QR.R.Num[K]-=(C.Num[i]+T); T=0;
				if(QR.R.Num[K]<0){ QR.R.Num[K] +=Base; T=1;}
				K++;
			}
            QR.Q.Num[j+1]=Q1; V=0;//該当桁の設定と上位桁の再設定
			for(int i=N+1; i>= (j+N2); i--)	V=V*Base+QR.R.Num[i];
		}
	}
	N2=N-N2+1;	while(QR.Q.Num[N2]==0)N2--;//商の長さ設定
	QR.Q.Len=N2;
	while(QR.R.Num[N]==0)N--;//剰余の長さ設定
	QR.R.Len=N;	return QR;
}


QRData divQRAbs(Bignum A, Bignum B){//Bignum同士の乗算
	static QRData QR,C;
	if(B.Len<=0){
		printf("0では割れません");
		QR.Q.Len=0;QR.R.Len=0; return QR;
	}
	int chk; chk=compAbs(A,B);
	if(chk<0){ QR.Q.Len=0; QR.R=copyBignum(A); return QR;}//A<B
	if(chk==0){QR.Q.Len=1; QR.Q.Num[1]=1; QR.R.Len=0; return QR;}//A==B
	if(B.Len==1){//除数が1桁のとき
		QR.Q=divQRAbs(A, B.Num[1], &(QR.R.Num[1]));
		if(QR.R.Num[1]==0)QR.R.Len=0;else QR.R.Len=1;
		return QR;
	}
	return divProc(A,B);//除数が2桁以上のとき

}
Bignum divAbs(Bignum A, Bignum B){//商のみ返却
	static QRData QR; QR=divQRAbs(A,B);
	return QR.Q;
}
Bignum divAbs(Bignum A, int B){//商のみ返却(B:小さな整数0〜99)
	int R;
	static Bignum Q; Q=divQRAbs(A,B, &R);
	return Q;
}
Bignum modAbs(Bignum A, Bignum B){//剰余のみ返却
	static QRData QR; QR=divQRAbs(A,B);
	return QR.R;
}
Bignum modAbs(Bignum A, int B){//剰余のみ返却(B:小さな整数0〜99)
	int R;
	static Bignum Q; Q=divQRAbs(A,B, &R);
	return intToBignum(R);
}
Bignum minus(Bignum A){// -A の処理
	static Bignum R=A;
	if(R.Len==0) R.Sign=0; else R.Sign= !R.Sign;
	return R;
}
Bignum abs(Bignum A){// 絶対値
	static Bignum R=A; R.Sign= false;return R;
}
int eqBig(Bignum A, Bignum B){ // A==B
	if(A.Sign!=B.Sign) return false;
	if(A.Len==0 && B.Len==0) return true;
	return compAbs(A,B)==0;
}
int neqBig(Bignum A, Bignum B){return !eqBig(A,B);}// A!=B
int gtBig(Bignum A, Bignum B){// A > B
	if(!A.Sign && B.Sign) return true;
	if(A.Sign && !B.Sign) return false;
	if(!A.Sign && !B.Sign){
		if(A.Len==0 && B.Len==0) return false;
		return compAbs(A,B)>0;
	}
	if(A.Len==0 && B.Len==0) return false;
	return compAbs(A,B)<0;
}
int ltBig(Bignum A, Bignum B){return gtBig(B,A);}  // A < B
int geBig(Bignum A, Bignum B){return !ltBig(A,B);} // A >= B
int leBig(Bignum A, Bignum B){return !gtBig(A,B);} // A <= B
Bignum addBig(Bignum A, Bignum B){ // A + B
	if(A.Len==0) return copyBignum(B);// A == 0 のとき B
	if(B.Len==0) return copyBignum(A);// B == 0 のとき A
	static Bignum C;
	if(A.Sign==B.Sign){	C=addAbs(A,B);C.Sign=A.Sign;}//符号が同じとき
	else{//符号が異なるとき減算を行う
		int check=compAbs(A,B);
		if(check==0) C= intToBignum(0);
		else if(check>0){ C=subAbs(A,B);C.Sign=A.Sign;}
		else            { C=subAbs(B,A);C.Sign=B.Sign;}	
	}
	return C;
}
Bignum subBig(Bignum A,Bignum B){// A - B
	if(A.Len==0) return minus(copyBignum(B));//A==0 のとき -B
	if(B.Len==0) return copyBignum(A);// B==0のときA
	static Bignum C;
	if(A.Sign!=B.Sign){C=addAbs(A,B);C.Sign=A.Sign;}//符号が異なるとき加算
	else {//符号が同じとき減算
		int check=compAbs(A,B);
		if(check==0) C= intToBignum(0);
		else if(check>0){ C=subAbs(A,B);C.Sign=A.Sign;}
		else            { C=subAbs(B,A);C.Sign=!A.Sign;}
	}
	return C;
}
Bignum mulBig(Bignum A, Bignum B){// A * B
	static Bignum C; C=mulAbs(A,B);
	if(C.Len==0) C.Sign=0; //符号が同じとき正, 異なるとき負
	else if(A.Sign==B.Sign) C.Sign=0; else C.Sign=true;
	return C;
}
Bignum divBig(Bignum A, Bignum B){// A / B
	static Bignum C; C=divAbs(A,B);
	if(C.Len==0) C.Sign=0; //符号が同じとき正, 異なるとき負
	else if(A.Sign==B.Sign) C.Sign=0; else C.Sign=true;
	return C;
}
Bignum modBig(Bignum A, Bignum B){// A % B
	static Bignum C; C=modAbs(A,B);
	if(C.Len==0) C.Sign=0;  //符号が同じとき正, 異なるとき負
	else if(A.Sign==B.Sign) C.Sign=0; else C.Sign=true;
	return C;
}
Bignum compPi(int MX){ //マチンの公式によるπの計算。MXは計算桁数
// π=16(��(-1)^k / ((2k + 1)・5^(2k - 1)) -4(��(-1)^k / ((2k + 1)・239^(2k - 1)))
  int MXX;MXX = MX + 1; Bignum Pi,T,K,U;
  Pi = intToBignum(0);T = hightFigures(false, MXX, 16); T = divAbs(T, 5); //最上位桁を16とする
  K = intToBignum(1); U = copyBignum(T);
  do{
    Pi = addBig(Pi, U); T = divAbs(T, 25); K = addAbs(K, 2); U = divBig(T, K);
	Pi = subBig(Pi, U); T = divAbs(T, 25); K = addAbs(K, 2); U = divBig(T, K);
  }while (U.Len !=0);
  T = hightFigures(false, MXX, 4);
  Bignum N239, N239sq; N239 = intToBignum(239);N239sq = mulAbs(N239, N239);
  T = divAbs(T, N239); K = intToBignum(1); U = copyBignum(T);
  do{
    Pi = subBig(Pi, U); T = divBig(T, N239sq); K = addAbs(K, 2); U = divBig(T, K);
  	Pi = addBig(Pi, U); T = divBig(T, N239sq); K = addAbs(K, 2); U = divBig(T, K);
  } while(U.Len!=0);
  return Pi;
}
Bignum compE(int MX){ //自然対数の底(e:ネイピア数）の計算
// e^x = �肺^k / k! で x = 1として計算する
  int MXX;MXX = MX + 1; Bignum E,T,K;
   E = hightFigures(false, MXX, 1); T=E; K=intToBignum(1);
  do{
	  E=addBig(E,T); K=addAbs(K,1);T=divBig(T,K);
  } while(T.Len!=0);
  return E; 
}
int main(void){//テストメイン
	int numA[]={0,10,10,10};
	int numB[]={0,10,10};
	Bignum A=integerArrayToBigNumber(false, numA, 3);
    Bignum B=integerArrayToBigNumber(false, numB, 2);
	printf("\n stringToBignum = ");
	printBignum(stringToBignum("-12345678"));
	char str[256];
	int N= bigToString(stringToBignum("123456789"),str, 256);
	printf("\n bigToString =%s",str);
	printf("\n A = ");
	printBignum(A);
	printf("\n B = ");
	printBignum(B);
	int R;
    printf("\n A == A ");
	printf("%s", eqBig(A,A)?"true":"false");
    printf("\n A == B ");
	printf("%s", eqBig(A,B)?"true":"false");
	printf("\n A != A ");
	printf("%s", neqBig(A,A)?"true":"false");
    printf("\n A != B ");
	printf("%s", neqBig(A,B)?"true":"false");
    printf("\n A > A ");
	printf("%s", gtBig(A,A)?"true":"false");
    printf("\n A > B ");
	printf("%s", gtBig(A,B)?"true":"false");
	printf("\n B > A ");
	printf("%s", gtBig(B,A)?"true":"false");
	printf("\n A < A ");
	printf("%s", ltBig(A,A)?"true":"false");
    printf("\n A < B ");
	printf("%s", ltBig(A,B)?"true":"false");
	printf("\n B < A ");
	printf("%s", ltBig(B,A)?"true":"false");
	printf("\n A >= A ");
	printf("%s", geBig(A,A)?"true":"false");
    printf("\n A >= B ");
	printf("%s", geBig(A,B)?"true":"false");
	printf("\n B >= A ");
	printf("%s", geBig(B,A)?"true":"false");
	printf("\n A <= A ");
	printf("%s", leBig(A,A)?"true":"false");
    printf("\n A <= B ");
	printf("%s", leBig(A,B)?"true":"false");
	printf("\n B <= A ");
	printf("%s", leBig(B,A)?"true":"false");
	printf("\n - intToBigNum(65532) = ");
	printBignum(minus(intToBignum(65532)));

	printf("\n A+10=");
	printBignum(addAbs(A,10));
	printf("\n A+B=");
	printBignum(addAbs(A,B));
	printf("\n A*B=");
	printBignum(mulAbs(A,B));
	
	printf("\n %d", compAbs(A,B));
    printf("\n A-B=");
	printBignum(subAbs(A,B));
	 printf("\n B*99=");
	printBignum(mulAbs(B,99));
	 printf("\n A*B=");
	printBignum(mulAbs(A,B));
	printf("\nB+A*B=");
	printBignum(mulAbs(B,A,B));
	printf("\n");
	printBignum(divQRAbs(A,8,&R));
	printf("余り=%d",R);
	QRData QR=divQRAbs(A,B);
	printf("\n divQRAbs A/B 商　");
	printBignum(QR.Q);
	printf("\n divQRAbs A/B 余り　");
	printBignum(QR.R);
	QR.Q=divAbs(A,B);
	printf("\n divAbs A/B 商　");
	printBignum(QR.Q);
	QR.R=modAbs(A,B);
	printf("\n divAbs A/B 余り　");
	printBignum(QR.R);
	printf("\n π =　");
	printSeperate(compPi(503));//1000桁求めるには,1006桁で計算し後を無視
	printf("\n e =　");
	printSeperate(compE(503));//1000桁求めるには,1006桁で計算し後を無視
	getchar();
	return 0;
}