BigInteger를 구현해보자 - 2. 정의와 생성, 파괴, 덧셈

c++ 클래스를 이용하면 사용할 때 편리한데, 무거워지는 느낌이 있어서, 귀찮지만 c로 구현한다. 먼저 Big Integer를 위한 구조체를 다음과 같이 정의한다.

1 2 3 4

typedef struct tagbigint{     u4 len;     u4* dats; }bigint;

len은 dats배열의 길이를 나타내고, dats는 실제 숫자정보가 담겨있는 배열이다. (u4는 DWORD와 같다.)
자, 다음 함수는 bigint를 만들어주는 함수이다.

1 2 3 4 5 6 7

u4 bigint_create(u4 len, bigint *xi) {     xi->len=len;     xi->dats=(u4*)malloc(len*sizeof(u4));     if(xi->dats==NULL)return 0;     return len; }

다음 함수는 bigint를 지워주는 함수이다.

1 2 3 4 5

void bigint_release(bigint *xi) {     xi->len=0;     SAFE_DELETE(xi->dats); }

다음 함수는 bigint의 크기를 다시 설정해주는 함수이다.

1 2 3 4 5 6 7

u4 bigint_resize(u4 newsize, bigint *xi) {     xi->len=newsize;     xi->dats=(u4*)realloc(xi->dats,newsize*sizeof(u4));     if(xi->dats==NULL)return 0;     return newsize; }

이 함수는 bigint에 u4값을 대입하는 함수이다. 제일 아래자리에 src를 넣고 나머지 윗부분은 0으로 채워주면 된다.
(누락된것을 지적해주신 dor님 감사합니다.)

1 2 3 4 5

void bigint_setu4(bigint *dest, u4 src) {     dest->dats[0]=src;     memset(&dest->dats[1], 0, (dest->len-1)*sizeof(u4)); }

이함수는 bigint에 bigint를 대입하는 함수이다.

1 2 3 4 5

void bigint_set(bigint *dest, const bigint *src) {     memcpy(dest->dats,src->dats,         ((dest->len<src->len)?dest->len:src->len)*sizeof(u4)); }

여기까지는 설명할 것도 없이 간단하다.

이제 덧셈을 구현하기 위해 다음 함수들을 만든다.
두 u4배열을 받아서 차례대로 더해주는 함수이다. (자리올림이 발생할 경우 윗 자리로 받아올려준다, 최상위자리에서 자리올림이 발생했을경우 1을 리턴한다.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

inline u4 add_a(u4 len,u4*dest,u4*src) {     u4 carry=0;     for(u4 i=0;i<len;++i)     {         dest[i]+=src[i];         if(carry)         {             if(dest[i]>=src[i])carry=0;             if(dest[i]==0xFFFFFFFF)carry=1;             ++dest[i];         }         else         {             if(dest[i]<src[i])carry=1;         }     }     return carry; }

u4배열의 가장 아래자리에만 src를 더해주는 함수이다. (자리올림이 발생할 경우 윗 자리로 받아올려준다, 최상위자리에서 자리올림이 발생했을경우 1을 리턴한다.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

inline u4 add_u4(u4 len,u4*dest,u4 src) {     u4 carry=0;     dest[0]+=src;     if(dest[0]<src)carry=1;     for(u4 i=1;i<len;++i)     {         if(carry)         {             if(dest[i]!=0xFFFFFFFF)carry=0;             ++dest[i];         }         else         {             break;         }     }     return carry; }

자, 이제 이 함수들을 이용해서 두 bigint를 더하는 함수를 만든다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

void bigint_add(bigint *dest, const bigint *src) {     if(dest->len<src->len)     {         add_a(dest->len, dest->dats, src->dats);     }     else     {         if(add_a(src->len, dest->dats, src->dats))         {             add_u4(dest->len-src->len, &dest->dats[src->len], 1);         }     } }

dest의 길이와 src의 길이를 비교해서 dest의 길이가 긴 경우에는 src의 길이만큼 하위자리를 더해주고, 받아올림이 발생했을 경우 윗 자리에 더해준다. src가 더 긴 경우는 dest길이만큼만 더해주고, 넘치는 부분은 그냥 버린다. dest와 src의 길이가 n이라면, 자리올림이 하나도 발생하지 않을 경우 n회의 덧셈을 하게되고, 한 자리에서는 최대 한 번의 자리올림이 발생할 수 있으므로 최악의 경우에도 2n회의 덧셈을 하게 되므로 이 덧셈 함수의 시간 복잡도는 O(n)이 된다.

1 2 3 4 5

void bigint_addu4(bigint *dest, u4 src,u4 pos) {     if(dest->len<=pos)return;     add_u4(dest->len-pos,&dest->dats[pos],src); }

이 함수는 bigint의 특정 자리에 u4를 더하는 함수.

bigint는 다음과 같이 쓰면 된다.

1 2 3 4 5 6 7 8 9

int main() {     bigint a,b;     bigint_create(2, &a);     bigint_create(2, &b);     bigint_setu4(&a, 1234567890);     bigint_setu4(&b, 3692581470);     bigint_add(&a, &b); }