#include "stdafx.h" #include "stdarg.h" #define BIGLEN 8 //■共通ルーチン(計算ではlongの下位16ビット(アンパック)で処理)--------------------- void printHexa(char str[], unsigned long A[], int N){//チェック用の表示関数 printf(str);printf("["); for(int i=0;iBのとき1,A=Bのとき0, A=0;i--) if(A[i]B[i]) return 1; return 0; } void B_Copy(unsigned long A[], unsigned long B[]){//配列コピー for(int i=0;i> 16 ; } } void B_Pack(unsigned long B[], unsigned long A[],int N){//16ビット単位のデータを詰める int NN=N/2+1; for(int i=0,ii=0;i>= 16; } } void B_Add(unsigned long A[], unsigned long B,unsigned long C[], unsigned long *overFlow){ B_Copy(A,C);*overFlow=A[0]+B; C[0]=(*overFlow) & 0xFFFF; (*overFlow)>>=16; for(int i=1;i>= 16; } } //■減算--------------------------------------------------------------------------------- void B_Sub(unsigned long A[], unsigned long B[],unsigned long C[],unsigned long *overFlow){ *overFlow=0;//減算 for(int i=0;i=(*overFlow)){ C[i]= A[i]-(*overFlow);*overFlow=0;} else { C[i]= (A[i] | 0x10000)-(*overFlow);*overFlow=1;} } } void B_Sub(unsigned long A[], unsigned long B,unsigned long C[],unsigned long *overFlow){ B_Copy(A,C);if(A[0]>=B) { C[0]=A[0]-B; return;}//上位からの借りがなければ終わってよい。 (*overFlow)=1; C[0]=(A[0] | 0x10000)-B; for(int i=1;i=(*overFlow)){C[i]= A[i]-(*overFlow);return;} C[i]= (A[i] | 0x10000)-(*overFlow); } } //■乗算(結果Cは2倍長であることに注意)C[BIGLEN*2]とすること----------------------- void B_Mult(unsigned long A[], unsigned long B[],unsigned long C[]){//乗算 for(int i=0;i>= 16; } C[j+BIGLEN] = AB; } } void B_Mult(unsigned long A[], unsigned long B,unsigned long C[]){//16ビット以下を乗算 for(int i=0;i>= 16; } C[BIGLEN] = AB; } //■除算---------------------------------------------------------------------------- void B_Div(unsigned long A[], unsigned long B,unsigned long C[],unsigned long *mod){ unsigned long AB=0,AA;//16ビット以下で除算 for(int i=BIGLEN-1;i>=0;i--){//上位除算の余りを下位の上位16ビットにして除算 AA=A[i]; AA |= (AB<<16); C[i] = AA / B; AB=AA % B; } *mod=AB; } //Big Number 除算(2分探索で処理。もっとうまいやり方があるかもしれない) void B_Div(unsigned long A[], unsigned long B[],unsigned long D[], unsigned long MD[]){ unsigned long mod; B_Copy(A,MD);B_Clear(D); int NA,NB;NA=NB=(BIGLEN-1); while(NA>=0 && A[NA]==0) NA--;if(NA<0) return;//0を除算 while(NB>=0 && B[NB]==0) NB--;if(NB<0) return;//0デバイドのとき無視 int k=NA-NB; if(k <0) return;//Aの方が小さいとき結果=0, if((k==0) && (A[NA]0)B[k-1]=1; // [例]100/9=11, 999/1=999 while(1){ B_Add(AA,BB,C,&mod); B_Div(C,(unsigned long)2,CC,&mod);/*CC=(AA+BB)/2*/ B_Mult(CC,B,SS); int cmp=B_Cmp(SS,A);/* CC*BとAの大小比較 */ if (cmp>=0) B_Copy(CC,AA); /* CC*B>AのときA=CC*/ else if(cmp==0) {B_Copy(CC,D);B_Clear(MD);return;}/* CC*B=Aのとき結果=CC*/ else{/*CC*B0){ B_Copy(CC,D);return;}// B>(A-(CC*B))のときCCが商 // B=(A-(CC*B))のとき(CC+1)が商,余り0 if(cmp==0){B_Add(CC,(unsigned long)1,D,&mod);B_Clear(MD);return;} B_Copy(CC,BB);/*余りが大きいときA-CC*B */ } } } //■10進数文字列変換--------------------------------------------------- int B_NotZero(unsigned long A[]){//Big Numberが0かどうかを比較する int N=BIGLEN-1; while(N>=0 && (A[N]==0))N--; if(N<0) return false; else return true; } int B_ToDecStr(unsigned long A[],char str[]){//Big Numberを文字列に変換する unsigned long C[500],mod,D[BIGLEN],C0[BIGLEN],AA[BIGLEN];B_Clear(C0);int N=0; B_Copy(A,AA); while(B_NotZero(AA)){//下位から10000の剰余(4桁ずつに区切る)を保管しておく B_Div(AA,(unsigned long)10000,D,&mod); C[N++]=mod; B_Copy(D,AA); } int i=N-1,j=0, X;//上位から4桁ずつ数字列に変換 if (C[i]>=1000) X=1000; else if(C[i]>= 100) X= 100; else if(C[i]>= 10) X= 10; else X= 1; for(int k=X; k>=1; k/=10){ str[j++]=(char)(C[i]/k)+'0'; C[i]%=k;} for(int i=N-2;i>=0;i--) for(int k=1000; k>=1; k/=10){str[j++]=(char)(C[i]/k)+'0'; C[i] = C[i] % k;} str[j++]=0; return j; } void B_StrToBig(char str[],unsigned long A[]){//文字列をBig Numberに変換する。 unsigned long D[BIGLEN*2],mod;B_Clear(A); for(int i=0;str[i]!=0;i++){ if(str[i]>='0' && str[i]<='9'){ B_Mult(A,(unsigned long)10,D); B_Add(D,(unsigned long)(str[i]-'0'),A, &mod); } } } //■テストメイン--------------------------------------------------- int _tmain(int argc, _TCHAR* argv[]) { unsigned long A[BIGLEN],B[BIGLEN], C[BIGLEN], D[BIGLEN*2],MD[BIGLEN]; unsigned long mod;char str[255]; B_Set(A, 8, 0x1234, 0x2345, 0x3456, 0x1234, 0x3456, 0x6789, 0x9BCD, 0xABCD); B_Set(B, 8, 0x7890, 0x2345, 0x3456, 0x1234, 0x3456, 0x6789, 0x9BCD, 0x0000); printHexa("\n A=",A,BIGLEN);printHexa("\n B=",B,BIGLEN); B_Add(A, B,C,&mod); printHexa("\n A+B=C\n C=",C,BIGLEN);printf("\n あふれ=%08X",mod); B_Add(A, (unsigned long)0xFFFF,C,&mod); printHexa("\n A+0xFFFF = C\n C=",C,BIGLEN);printf("\n あふれ=%08X",mod); B_Sub(A, B,C,&mod); printHexa("\n A-B=C\n C=",C,BIGLEN);printf("\n あふれ=%08X",mod); B_Sub(A, (unsigned long)0xA234,C,&mod); printHexa("\n A-0xA234 = C\n C=",C,BIGLEN);printf("\n あふれ=%08X",mod); B_Mult(A, B, D); printHexa("\n A*B=D\n D=",D,BIGLEN*2); B_Div(A, (unsigned long)0x1000, C,&mod); printHexa("\n A/0x1000=C\n C=",C,BIGLEN);printf("\n 余り=%08X",mod); B_Mult(C, (unsigned long)0x1000, D); printHexa("\n C*0x1000=D, A=D+余りを確認\n D =",D,BIGLEN*2); B_Set(B, 8, 0x7890, 0x2345, 0x3456, 0x1234,0x0000, 0x0000, 0x0000, 0x0000); B_Div(A, B, C, MD); printHexa("\n A/B=C 余り MD\n C=",C,BIGLEN);printHexa("\n M=",MD,BIGLEN); B_Mult(B, C, D); B_Add(D,MD,C,&mod); printHexa("\n除算確認 B * C + MD = C Aと等しいことを確認\n A=",C,BIGLEN); int N=B_ToDecStr(B, str); printf("\nBigNumを10進数数字列に\n 文字数=%d 数字列=%s",N, str); B_StrToBig("123456789012345",A); B_ToDecStr(A,str); printf("\n文字列\"123456789012345\"をBigNumに変換し,"); printf("それを文字列に変換。\n \"%s\"", str); getchar(); return 0; }