BigInteger를 구현해보자 - 4. 곱셈과 부호 체크

두 u4배열의 곱셈은 다음과 같이 한다.

	a[2]	a[1]	a[0]
X		b[1]	b[0]
---------------------------------------------------------------------------------------
	a[2]*b[0]	a[1]*b[0]	a[0]*b[0]
a[2]*b[1]	a[1]*b[1]	a[0]*b[1]

두 수의 곱셈을 하듯이 두 u4배열을 곱해주면 된다. 이 때 u4*u4는 최대 약 2^64 까지 나올수 있으므로 일반적인 int형에는 저장할 수가 없다. 따라서 64비트 int의 부호없는 타입을 u8이라고 정의하고, u8로 받아야 한다.

먼저 bigint의 부호없는 곱셈을 하는 함수를 만든다.

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

void bigint_mul_i(bigint *dest, const bigint *src1, const bigint *src2) {     u8 res;     memset(dest->dats, 0, dest->len*sizeof(u4));     for(u4 i=0;i<src1->len;++i)     {         for(u4 j=0;j<src2->len;++j)         {             res=(u8)(src1->dats[i])*src2->dats[j];             bigint_addu4(dest, (u4)res, i+j);             bigint_addu4(dest, (u4)(res>>32), i+j+1);         }     } }

u8로 캐스팅하여 두 u4 정수를 곱한 후 자리수에 맞춰서 dest에 더해준다. 더하는 것은 앞에서 구현했던 bigint_addu4함수를 사용한다. 그래야지 덧셈에 따른 받아올림까지 정확하게 계산된다.

bigint와 u4간의 곱셈을 하는 함수를 만든다.

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

void bigint_mulu4(bigint *dest, u4 src) {     u8 res;     u4 tmp[dest->len];     memcpy(tmp, dest->dats, dest->len*sizeof(u4));     memset(dest->dats, 0, dest->len*sizeof(u4));     for(u4 i=0;i<dest->len;++i)     {         res=(u8)(tmp[i])*src;         bigint_addu4(dest, (u4)res, i);         bigint_addu4(dest, (u4)(res>>32), i+1);     } }

이 함수는 bigint에 u4를 곱해준다. 내부에서 c99용 문장을 사용했는데(u4 tmp[dest->len];) 문제가 있다면 동적할당으로 바꾸어주면 된다.

부호있는 곱셈 함수를 만들기 전에 0보다 크지 작은지를 판단하는 함수를 만들어 본다.

1 2 3 4 5 6 7 8 9 10

int bigint_sign(const bigint *xi) {     if(xi->len==0)return 0;     if(xi->dats[xi->len-1] & 0x80000000)return -1;     for(u4 i=0;i<xi->len;++i)     {         if(xi->dats[i]!=0)return 1;     }     return 0; }

이 함수는 xi가 0이면 0, 0보다 작으면 -1, 0보다 크면 1을 리턴한다. 이제 부호없는 곱셈 함수와 부호 판별 함수를 이용해 부호있는 곱셈 함수를 만든다.

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

void bigint_mul(bigint *dest, const bigint *src1, const bigint *src2) {     int s1=bigint_sign(src1)<0;     int s2=bigint_sign(src2)<0;     bigint src1n, src2n;     if(s1)     {         bigint_createnegcopy(&src1n, src1);         src1=&src1n;     }     if(s2)     {         bigint_createnegcopy(&src2n, src2);         src2=&src2n;     }     bigint_mul_i(dest, src1, src2);     if(s1^s2)bigint_neg(dest);     if(s1)bigint_release(&src1n);     if(s2)bigint_release(&src2n); }

방금 만든 부호확인하는 함수로 체크하여 음수일 경우 부호를 바꿔 양수로 만든 다음 곱하는 방법이다. src1의 길이가 n, src2의 길이가 m이라면 총 곱셈횟수는 n*m회가 되고, 덧셈은 2*n*m회가 되는데, 최악의 경우에 덧셈시마다 받아올림이 발생할 경우 대략 (n+m)*n*m회 덧셈을 할 수도 있다. 하지만 연산비용은 덧셈보다 곱셈이 비싸므로, 덧셈 연산량은 생략해도 무방하다. 따라서 시간복잡도는 n=m일때 O(n^2)