상세 컨텐츠

본문 제목

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

프로그래밍/Multi precision

by ∫2tdt=t²+c 2009. 3. 29. 23:35

본문

두 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의 부호없는 곱셈을 하는 함수를 만든다.

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

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

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

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


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

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

관련글 더보기

댓글 영역