상세 컨텐츠

본문 제목

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

프로그래밍/Multi precision

by ∫2tdt=t²+c 2009. 3. 29. 00:47

본문

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


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

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

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

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

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


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

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


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


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

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


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

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


관련글 더보기

댓글 영역