2. 기본 연산
2.1 덧셈
큰 수에 대한 덧셈을 구현해 본다.
앞장에서 계속 얘기한 바와 같이 '큰 수'란 프로그래밍 언어에서 기본으로 제공하는 가장 큰 자료형으로 표현할 수 없는 큰 수이다. 그리고 이 '큰 수'는 기본 자료형의 배열로서 표현하기로 했다.
이 큰 수에 대한 덧셈이라는 것은, 따라서, 배열로 표현된 일련의 값들을 서로 더해서, 다른 큰 수(=배열)에다 넣는것이 된다.
예를 들어 두 큰 수 a와 b를 더해서 c에다 넣는것을 생각해 보자.
a = 0x3333 4444 AABB CCDD (십진수로는 3689367581459467485)
b = 0x1122 3344 5566 7788 99AA BBCC
(가독성이 좋게하기위해서 4니블씩(=2바이트) 끊어서 표현하였다)
BIGINT로 표현하면 다음과 같은 배열이 될 것이다. (4바이트 unsigned long이 배열 기본 자료형이라고 가정함)
a[0] = 2 //크기
a[1] = 0xAABB CCDD
a[2] = 0x3333 4444
b[0] = 3
b[1] = 0x99AA BBCC
b[2] = 0x5566 7788
b[3] = 0x1122 3344
BIGINT로 표현할 때, 첫번째 배열값에는 크기정보가 들어간다. 따라서, 수 a가 8바이트를 차지하므로 4바이트 배열 2개로 가능. 따라서 a의 크기는 2
배열의 오른쪽에서 시작해서 왼쪽으로 값을 채워가기로 약속했으므로, 배열의 제일 오른쪽인 a[2]에 0x3333 4444가 들어가게 되고, 그 다음 a[1]에 0xAABB CCDD가 들어가게 된다. b에 대해서도 같은 원리.
이 두 배열의 합을 도식화해보면 다음과 같이 된다.
초등학교때 배우는, 손으로 푸는 덧셈과 유사한 형태가 되었다.
실제 프로그래밍으로 구현할 덧셈도, 이 손으로 푸는 덧셈의 방식을 사용할 것이다.
배열의 0번째는 크기정보가 들어가므로, [1]번째 부터 차례로 더하면 된다. 초등학교때 손으로 써서 푸는 덧셈처럼. 단, 다른 것은, 우리가 종이에 써서 덧셈을 할 때는, 큰 자릿수가 왼쪽에 있으므로, 가장 작은 자릿수인 제일 오른쪽부터 차례로 더하면서, 올림이 발생했을 때 다음 자리로(왼쪽으로) 올림을 하고 계속해서 왼쪽자리로 이동하면서 덧셈을 하는데 반해, 위 그림에서는 배열첨자가 작은 왼쪽에 가장 작은 자릿수가 들어가므로, [1]번째 두 수를 더하고, 이어서 오른쪽 편으로 더해가는 방식을 취하게 된다.
우리가 일상생활에서 사용하는 수는 십진수다. 이 십진수에 대한 덧셈은, 같은 자리의 두 수를 더했을 때 그 결과가 10이상이 되면 올림을 한다. 이것을 기수가 b인 수의 덧셈으로 일반화해보면, 두 수의 합이 기수 b이상이면 올림이 발생하는 것으로 확장할 수 있다.
우리가 BIGINT에서 사용하는 기수는 배열의 기본 자료형으로 정한 것이 나타낼 수 있는 최대값이다. 즉, 32비트 자료형을 사용하는 경우 232(=0x100000000)이다. 따라서, 두 배열에서 같은 자리에 있는 값을 더해서(두 long값의 합) 이 값이 0x100000000미만이면, 올림 없이 그대로 그 값이 결과값이 되고, 이상이면 1을 다음 자리로 올림하고, 합한 값에서 b를 뺀 값을 결과값으로 하면된다.
이제 위 내용을 정리해서, b를 기수(=밑수)로 하는 n자리 두 정수의 합을 구하는 알고리즘으로 일반화해보자.
덧셈 알고리즘1
이 알고리즘은, 음이 아닌 n자리 정수 U=(un-1...u1u0)b와 V=(vn-1...v1v0)b가 주어졌을 때, 정수U와 정수V의 합 W=(wnwn-1...w1w0)b을 구한다. (여기서 wn은 0 아니면 1이다.)
S1.[초기화]
j ← 0, k ← 0
S2.[숫자 더하기]
wj ← (uj + vj + k)mod b, k ← ⌊(uj + vj + k)/b⌋ (⌊ ⌋ :내림. floor)
S3. [j에 대한 루프]
j ← j + 1
if(j < n) goto S2
else wn ← k, goto END
END
S1.[초기화]
j는 0에서 n-1까지 루프를 돌리기 위한 변수. zero로 초기화
k는 올림값을 저장하기 위한 변수. 올림값은 항상 0 혹은 1
S2. [숫자 더하기]
두 수를 더해서, 더한 값이 기수 b보다 작으면 그대로 결과값으로 넣고, 더한 값이 기수 이상이면, 결과값으로는 더한값을 mod한 값(=더한값을 기수b로 나눈 후 나머지값)으로 하고, 올림은 더한값을 b로 나눈 후 가장 가까운 정수로 내림한 값으로 한다.
이 부분을 좀더 설명하자.
먼저, 두 수는 0~(b-1)까지의 임의의 수이다. 즉, 최소값은 0이고 최대값은 b-1
k는 올림수(carry)를 저장하게 되는데, 올림수는 항상 0 아니면 1이다.
따라서, (uj + vj + k)의 범위는 최소값은 0이고, 최대값은 (2b-1)이다. 왜냐면, u와 v의 최대값이 b-1이고, k의 최대값이 1이므로, 각 값의 최대값을 더했을 때가 최대값. 따라서, (b-1) + (b-1) + 1 = 2b -1
즉, (uj + vj + k)의 최대값이 2b-1로서, 알고리즘 구현시 (uj + vj + k)값을 저장한 변수는 2b-1까지 처리할 수 있도록 충분히 큰 변수라야 한다.
BIGINT에서 기본 자료형으로 long형 32비트를 사용한 경우, b는 0x100000000이다. 따라서 2b-1=1FFFFFFFF으로, 32비트 long형으로는 표현할 수 없다. 따라서, long형보다 더 큰 메모리를 가지는 8바이트의 long long형 변수로 이 부분을 처리해야 한다.
S3. [j에 대한 루프]
j를 증가시키면서 즉, 높은 자리로 하나씩 이동하면서 S2를 반복한다. 제일 마지막인 n-1에 와서는, 올림이 발생한 경우 즉, k==1인 경우에 wn은 1이되고, 올림이 없는 경우(k==0인 경우)에 wn은 존재하지 않게 된다.
이제 이 알고리즘을 좀 더 현실감있게(실제 C 프로그래밍에 적합하게) 보완해보자
(위의 알고리즘은 "The Art of Computer Programming"에서 제시된 것과 일치하는 것이고, 그것을 이 글에서 보완해서 프로그래밍 하자는 것)
보완된 사항은 세 가지.
- 음수에 대한 연산도 고려
- 더하려는 두 수의 자릿수 크기가 다른 경우 고려
- 두 수의 덧셈을 처리하는 임시변수 고려
- mod연산과 내림연산 대신에 보다 간단한 연산 적용
- overflow처리
보완된 덧셈 알고리즘
이 알고리즘은, n자리 정수 U=(um-1...u1u0)b와 V=(vn-1...v1v0)b가 주어졌을 때(양수, 음수 상관없음), 정수U와 정수V의 합 W=(wpwp-1...w1w0)b을 구한다. 여기서 p는 m과 n중에서 큰 값. 그리고 wp는 0 아니면 1이다.
S1. [크기 비교] 주어진 두 수 U, V의 자릿수 크기를 비교해서, 큰 쪽을 L로하고 작은 쪽을 S로 대치(L:Large S:Small)
if(m > n) L = U, S = V
else L = V, S = U
S2. [초기화]
k ← 0, j ← 0
S3. [더하기1]두 수의 합 구한다.
t = (lj + sj + k)
wj = t mod b
k = ⌊t/b⌋
S4. [루프: S] 작은 수인 S의 자릿수까지 j 증가
j ← j + 1
if(j < S자릿수) goto S3
else goto S5
S5. [더하기2]
t = (lj + k)
wj = t mod b
k = ⌊t/b⌋
S6. [루프: L] 큰 수인 L의 자릿수까지 j 증가
j ← j + 1
if(j < L자릿수) goto S5
else wp ← k, goto END
S7. [check carry] if(k>0) C의 자릿수 1증가
if(k>0)
if(C의 자릿수 == MAX) carry 무시
else C의 다음 자릿수에 1 지정
S8. [check overflow]
if( (A>0) and (B>0) and (C<0) ) then Overflow
if( (A<0) and (B<0) and (C>0) ) then Overflow
END
S1. [크기 비교]
덧셈에 대해 보완된 알고리즘을 보면, 가장 큰 특징은 두 수의 자릿수가 다른 경우에 대한 처리를 명시적으로 한 것이다. 자릿수 크기가 같은 경우는 문제가 없으나, 다른 경우는, 작은 수의 자릿수 범위내에서는 두 수가 존재해서 덧셈을 하게 되지만, 작은 수의 자릿수보다 큰 부분에 대해서는 큰 수와 올림(carry)만을 더해야할 것이다. 이렇게 큰 수와 작은 수의 구분이 필요하므로, 두 수를 비교해서 큰 수와 작은 수로 나누어 둔다.
S2. [초기화]
k는 올림(carry)용으로, j는 루프 증가용. 둘 다 zero로 초기화
S3. [더하기 1]
작은 수의 자릿수 범위내에서의 더하기이다. 예를 들어 5자리(=크기정보를 제외하고 5개 배열값을 가지는 수) 수 U와, 3자리 수 V를 더하는 경우, 3자리까지는 u + v + k를 한다. 3자리 V값에 대해 모두 더하고 난 다음에는 S5에서 u+k만을 더하게 된다.
변수 t는 u와 v의 합을 저장할 수 있게, 즉, (2b-1)값을 저장할 수 있는 큰 자료형으로 선언되어야 한다. 즉, u와 v의 자료형이 long이면 t의 자료형은 long long
S4. [루프 S]
작은 값인 S 자릿수 한도내에서 j값 증가
S5. [더하기 2]
작은 수 S보다 큰 자릿수에 대한 더하기를 한다. 더 이상 S의 값이 존재하지 않으므로, L과 k값만 더한다.
주의할 것은 L의 끝 자리까지 k를 계속해서 더해줘야 한다는 것이다. 왜냐하면 계속해서 올림이 발생할 수도 있기 때문이다. (십진수 덧셈에서 99998 + 7 을 하는 경우에 해당. 끝자리인 8과 7을 구하고 난 후, 올림이 발생하고 계속해서 끝자리까지 올림 발생)
S6. [루프 L]
큰 수의 L의 끝자리까지 j값을 증가시키며 루프를 돈다.
S7. [check carry] if(k>0) C의 자릿수 1증가
S6에서 L까지 루프를 돌았는데 carry가 남아 있는 경우에는, C의 다음 자리를 1로 만든다. 그런데 만약 C가 BIGINT의 최대자릿수에 도달했다면 C의 다음자리가 존재하지 않는다. 이때는 그냥 carry를 무시한다.
S8. [check overflow]
(양수 + 양수)를 했는데 결과값이 음수이거나, (음수 + 음수)를 했는데 결과값이 양수라면 잘못된 결과로 overflow를 리턴한다.
위 알고리즘을 좀 더 살펴보기 위해, 1바이트를 사용한 수 체계를 예로 살펴보자.
1바이트 수체계에서는 수는 0x00에서 0xFF까지 256가지 존재한다. 부호를 고려하고 음수를 2의 보수로 나타낸다면 앞 장에서 살펴봤던 바와 같이 다음과 같이 된다.
<1바이트 메모리에 대한 부호있는 값 표시방법>
| 메모리[16진수] | 값[10진수] |
| 00 | 0 |
| 01 | 1 |
| ... | ... |
| 7F | 127 |
| 80 | -128 |
| 81 | -127 |
| ... | ... |
| FE | -2 |
| FF | -1 |
여기서 127+(-2)의 덧셈을 고려해보자. 답은 125(0x7D)가 나와야할 것이다.
16진수로 나타내면 0x7F + 0xFE = 0x17D
위 알고리즘에서 언급한 바와 같이, 한 바이트를 초과한 '1'이 무시되면 '7D'가 되어 기대했던 값으로 계산됨
다른 경우로, 127+127을 고려해 보자. 127+127= 254로 부호가 있는 한 바이트 수체계에서는 표현할 수가 없다.
이 경우 알고리즘에선 어떻게 계산되는지를 보면,
0x7F + 0x7F = 0xFE = -2
16진수로 본다면 계산이 제대로 되었으나, 부호를 고려해서 표현한다면 잘못된 계산이다. 따라서, 위 알고리즘에서는 S8에 의해 overflow를 리턴하게 된다.
이/제 위 알고리즘대로 두 수에 대한 덧셈함수를 구현해 보자
//file: biging.c
/***************************************************************************************
두 수를 더함
만약 더한 두 수가 BIGINT의 최대자릿수를 넘어서는 경우는,
E_Overflow를 리턴하고, 결과에는 초과하는 부분을 절삭한 값 세팅
(음수 + 양수)의 경우에 해당
input: BIGINT A, BIGINT B
output: BIGINT C (C = A + B)
return: OK - if all ok
E_Overflow - 두 수를 더한 값이 BIGINT의 최대값을 넘어서는 경우
****************************************************************************************/
int add(BIGINT A, BIGINT B, BIGINT C){
INT *L, *S, *W; //w=sum
INT *LE, *SE ;
DINT t;
INT k;//carry
큰 수에 대한 연산은 bigint.c에 구현될 것이다. 헤더파일은 biging.h
함수명은 add로 하고, 파라미터로 더할 두 수 A, B와 더한값이 저장될 C를 받로록 한다.
BIGINT는 bigint.h에 typedef INT BIGINT[MAX_INT_LEN+1]로 정의되어 있다. 파라미터로 이렇게 크기가 확정된 배열로 받는 것은 비교적 작은 수에 대한 덧셈을 하는데 있어 메모리 낭비일 수 있겠다. 그런경우는 포인터변수로 받고 처리하는 것이 메모리 낭비를 줄일 수 있는 방법이지만 더한 값을 C에다 넣을 때 C의 크기가 두 수의 합을 넣을 수 있을만큼 충분한 메모리가 확보되어 있다는 것을 체크해야한다. (앞장에서도 설명) 따라서, 크기가 확정된 BIGINT타입으로 인자를 받도록 한다.
지역변수로 *L, *S, *W를 선언한다.
L은 두 수 A,B중에서 큰 수, S는 작은 수, W는 합이 저장될 C의 주소를 가르키게 될 것이다. (정확하게는 큰 수를 나타내는 배열의 두번째 인자 주소. 첫번째 인자는 크기를 나타내므로)
지역변수 *LE, *SE는 각각 해당 BIGINT의 마지막 위치를 나타내게 될 것이다.
t는 DINT로 정의한다. DINT는 INT형의 두 배 메모리를 차지한다. 즉, INT가 long타입으로 32비트이면 long long타입으로 64비트.
t의 존재이유는 두수의 합(정확하게는 두 수와 올림수의 합)을 계산할 중간 버퍼로 사용되기 위해서이다.
k는 올림수를 저장할 변수이다. 여기서 올림수는 항상 0 혹은 1이다. 따라서 1바이트 메모리로도 충분해서 char 혹은 short형으로 선언해도 무방하나, INT로 선언해도 그리 메모리 손실이 아니고, 어차피 INT형 수와 더하는 데 사용되면서 INT형으로 자동 형변환이 될 것이기에, INT로 선언한다.
//S1.[크기비교] large = (size(A) > size(B)) ==> A : B if(SIZE(A) > SIZE(B)){ L = A + 1; LE = A + SIZE(A); S = B + 1; SE = B + SIZE(B);SET_SIZE(C, SIZE(A)); }else{ L = B + 1; LE = B + SIZE(B); S = A + 1; SE = A + SIZE(A);
SET_SIZE(C, SIZE(A)); } W = C +1;
S1에서는 더할 두 수주에서 어느쪽이 큰 수인지 판단해서(정확하게는 어느쪽 자릿수가 큰지), L이 큰 수를 가르키게하고, S가 작은 수를 가르키게 한다.
BIGINT는, 배열의 첫번째 인자에 자신의 크기를 나타내도록 되어 있으므로, 큰 수인지의 판단은 첫벗째 배열값을 보면 된다.
매크로로 정의된 SIZE는 인자로 주어지는 변수의 처음 주소의 값을 읽게 되어있다.
#define SIZE(n) ((unsigned short)*(n))
L과 S는 BIGINT의 실제값이 시작되는 두번째 배열인자를 가르키게된다. BIGINT는 작은인자에 작은 자릿수 값이 들어가게 되므로, 두번째 배열인자부터 더하면서 큰 인자쪽으로 진행하게 되면, 우리가 손으로 써서 계산하는 방식인 작은자릿수 값부터 더하면서 올림하는 방식과 동일하게 된다.
LE와 SE에는 BIGINT의 제일 마지막 값을 가르킨다. 여기서 마지막 값은 BIGINT로 할당된 전체 배열의 끝이 아닌, 첫번째 배열인자에 명시되어 있는 BIGINT의 실제크기만큼에서의 제일 마지막 주소를 의미한다.
두 수의 합을 저장하게될 C의 크기는, A, B중 큰 수의 자릿수와 같아지거나 1 더 크게 된다. 즉, A가 5자리, B가 3자리이면, C는 5자리 혹은 6자리의 수가 된다. 따라서, C의 크기를 두 수 A, B중 큰 수의 자릿수로 일단 설정해 두고, 마지막 자리에 대한 계산이 끝났을 때 올림이 존재하는지 여부에 따라 C의 크기를 +1할지 안할지 결정하면 된다.
//S2.[초기화] k=0
k = (INT)0; S2.는 사용될 변수를 초기화 한다. k는 올림을 저장할 변수. 초기 올림값은 zero라야 하므로 0으로 초기화.
알고리즘에서는 루프 증가를 위해 변수j를 도입하고 초기화했으나, 실제 구현은 두 수를 가르키는 포인터변수값을 직접 확인하는 while루프로 구현하기에, 루프 증가용으로 변수 j 사용하지 않음
//S3. S4. 두 수 더하기. 오른쪽에서 왼쪽으로 until small_end while(S <= SE){ t = (DINT)*L++ + (DINT)*S++ + (DINT)k; *W++ = (INT)t; k = (INT)(t >> (sizeof(INT)*8) ); }
작은 수의 자릿수 내에서 덧셈을 수행한다.
먼저 DINT형 변수인 t에 두 수와 올림수를 더해 놓고, 최종 덧셈결과를 보관할 C의 주소를 가르키고 있는 W에는 t를 INT형에 해당하는 밑수로 modula연산한 값을, k는 t가 밑수보다 큰지 여부에 따라 1 혹은 0이 되게 한다.
먼저 t의 계산은, t가 DINT형이기에, 더할 INT형 변수들을 DINT로 캐스팅한 수 더해준다.
W에는 t mod 232을 한 값이 들어가게 될텐데, 간단하게 DINT변수인 t를 INT로 캐스팅해주면 동일한 효과를 볼수 있겠다. 즉, DINT가 8바이트이면, W에는 4바이트까지의 t값이 들어가게되는 것이고, 이는 modular연산과 동일하게 됨
k에는 1 또는 0값이 들어가게 되는데, (t-232)의 값이 양수이면 1 아니면 0으로 처리할 수도 있으나, (INT)(t/232)와 동일한 효과를 나타내는 t값을 INT형 비트만큼 오른쪽 쉬프트시키는 것으로 처리하는 것이 더 효율적일 것임
//S5. S6. large값에다 carry 더하기 while(L <= LE){ t = (DINT)*L++ + (DINT)k; *W++ = (INT)t; k = (INT)(t >> (sizeof(INT)*8) ); }//S7. if carry exist(k > 0), C의 자릿수 1 증가 if(k > 0){ if( (SIZE(C)+1) > MAX_INT_LEN){REMOVE_ZERO(C); }else{ *W = 1; SET_SIZE(C, (SIZE(C))+1); } }
S5. S6. 에서는 큰수의 자릿수내에서 덧셈 수행.
만약 두 수 A, B의 자릿수가 같다면, 이 부분은 수행되지 않는다. 왜냐하면 자릿수 크기가 같다면 (SE-S)==(LE-L)이되고, S3. S4 에서 while(S <= SE)될 때까지 L의 주소값이 증가되었기에, S5.S6. 스텝의 while(L <= LE)부분은 수행되지 않음
자릿수가 다른 경우는, 큰 수와 올림수만을 더해서 결과값 처리.
마지막 자리까지 계산이 다 된 후에는, 마지막 자리에 대한 올림이 발생했는지를 확인해서, 올림이 있다면(k>0), W값을 1로 하고, 합을 저장하게 되는 C의 크기를 1 증가시킨다. 이 때, C의 자릿수가 이미 MAX가 되어, 더 올림할 자릿수가 없을 때는 올림수를 무시한다.
올림수가 무시되는 경우는, 남아있는 가장 최대 자릿수의 수가 zero인지를 확인해서, zero가 아닌 수가 나올 때가지 자릿수 변경을 해줘야 한다.
REMOVE_ZERO매크로가 그 기능을 해주는데, REMOVE_ZERO는 bigint.h에 정의되어 있는 매크로로. zero로 채워져 있는 앞 부분을 정리하는 기능을 사지고 있다.
#define REMOVE_ZERO(n) while((SIZE(n)>0) && (*((n) + SIZE(n)) == 0)) --*(n);
//S8. Check overflow if((isPositive(A) == 1) && (isPositive(B) == 1) && (isPositive(C) == -1 )){ // (양수+양수) < 0 ==> overflow return E_Overflow; }else if((isPositive(A) == -1) && (isPositive(B) == -1) && (isPositive(C) == 1 )){ // (음수+음수) > 0 ==> overflow return E_Overflow; } return OK;
덧셈에 있어서 (양수 + 음수)의 경우는 overflow가 발생하지 않는다. 정확하게 얘기하면 계산과정에서는 가장 큰 자릿수를 넘어서는 carry가 발생할 수 있지만, 그 넘어서는 carry를 무시해버리면 나머지 결과값이 원하더 덧셈결과가 된다.
(1바이트 수 체계에서 127 + (-2) = 0x7F + 0xFE = 0x17D -> 0x7D = 125가 되는 것 처럼)
(양수 + 양수) 혹은 (음수 + 음수)의 경우, overflow가 발생할 수 있다. 이 경우, 16진수의 표현으로는 정확한 덧셈이 되는 것이지만, 부호를 고려한 표현을 한다면 의도했던 결과와 다르게 표현된다. 따라서, 이 경우 E_Overflow를 리턴한다.
isPositive함수는 주어진 BIGINT값이 음수인지 양수인지를 판별하여 그 결과를 알려주는 함수이다. 양수인 경우는 1을, 음수의 경우 -1을 리턴한다.
int isPositive(BIGINT A){ if( (*A == MAX_INT_LEN) && (*(A+MAX_INT_LEN) > MAX_POSITIVE)) return -1; else return 1; }
전체 소스(bigint.h bigint.c)
add함수만 담고 있는 biging.c와 biging.h 소스는 다음과 같다.
//bigint.h
//01. CPU, 컴파일러에 따라서 조정할 값들 #define MAX_BIT_LEN 4096 //최대 비트수
typedef unsigned char u8; typedef unsigned short u16; typedef unsigned long u32; typedef unsigned long long u64;
#define BASE_IS_4_BYTES #ifdef BASE_IS_4_BYTES typedef u32 INT; typedef u64 DINT; #define MAX_INT 0xffffffff #define BASE 0x100000000 #define MAX_DINT 0xffffffffffffffff #define MAX_POSITIVE 0x7fffffff #else typedef u16 INT; typedef u32 DINT; #define MAX_INT 0xffff #define BASE 0x10000 #define MAX_DINT 0xffffffff #define MAX_POSITIVE 0x7fff #endif
//02. 큰수(BIGINT)에 대한 정의들. CPU에 따라 재정의할 필요 없음 #define MAX_INT_LEN (MAX_BIT_LEN / (sizeof(INT) * 8) ) //INT자료형 최대 갯수 4096/32 = 128 typedef INT BIGINT[MAX_INT_LEN + 1]; //[0]위치에 크기정보 담고 있으므로 + 1
//03. 매크로들 #define SIZE(n) ((unsigned short)*(n)) #define SET_SIZE(n,m) (*(n) = (unsigned short)(m)) #define REMOVE_ZERO(n) while((SIZE(n)>0) && (*((n) + SIZE(n)) == 0)) --*(n);
//04. Error #define OK 0 #define E_Overflow -1 #define E_NotSupported -2 #define E_WrongFormat -3 #define E_ZeroLength -4 #define E_DivideByZero -5 #define E_Underflow -6
//05. 함수정의 int add(BIGINT A, BIGINT B, BIGINT C);
//biging.c
/************************************************************************** 주어진 BIGINT가 양수인지 판별 Input: @A: BIGINT to determine whether it's positive or not Returns : 1 if BIGINT is positive value including zero -1 if BIGINT is negative value. ***************************************************************************/ int isPositive(BIGINT A){ if( (*A == MAX_INT_LEN) && (*(A+MAX_INT_LEN) > MAX_POSITIVE)) return -1; else return 1; }
/*************************************************************************************** 두 수를 더함 만약 더한 두 수가 BIGINT의 최대자릿수를 넘어서는 경우는, E_Overflow를 리턴하고, 결과에는 초과하는 부분을 절삭한 값 세팅 (음수 + 양수)의 경우에 해당 input: BIGINT A, BIGINT B output: BIGINT C (C = A + B) return: OK - if all ok E_Overflow - 두 수를 더한 값이 BIGINT의 최대값을 넘어서는 경우 ****************************************************************************************/ int add(BIGINT A, BIGINT B, BIGINT C){ INT *L, *S, *W; //w=sum INT *LE, *SE ; DINT t; INT k;//carry //S1.[자릿수 크기비교] large = (size(A) > size(B)) ==> A : B if(SIZE(A) > SIZE(B)){ L = A + 1; LE = A + SIZE(A); S = B + 1; SE = B + SIZE(B); SET_SIZE(C, SIZE(A)); }else{ L = B + 1; LE = B + SIZE(B); S = A + 1; SE = A + SIZE(A); SET_SIZE(C, SIZE(B)); } W = C +1; //S2.[초기화] k=0 k = (INT)0; //S3. S4. 두 수 더하기. 오른쪽에서 왼쪽으로 until small_end while(S <= SE){ t = (DINT)*L++ + (DINT)*S++ + (DINT)k; *W++ = (INT)t; k = (INT)(t >> (sizeof(INT)*8) ); } //S5. S6. large값에다 carry 더하기 while(L <= LE){ t = (DINT)*L++ + (DINT)k; *W++ = (INT)t; k = (INT)(t >> (sizeof(INT)*8) ); } //S7. if carry exist(k > 0), C의 자릿수 1 증가 if(k > 0){ if( (SIZE(C)+1) > MAX_INT_LEN){ //max보다 큰 자릿수로 넘어가는 carry는 무시(즉, % BASE) REMOVE_ZERO(C); }else{ *W = 1; SET_SIZE(C, (SIZE(C))+1); } } //S8. Check overflow if((isPositive(A) == 1) && (isPositive(B) == 1) && (isPositive(C) == -1 )){ // (양수+양수) < 0 ==> overflow return E_Overflow; }else if((isPositive(A) == -1) && (isPositive(B) == -1) && (isPositive(C) == 1 )){ // (음수+음수) > 0 ==> overflow return E_Overflow; } return OK; }
Visual Studio용 프로젝트 파일; add함수용
001.Add.zip
* Visual Studio를 이용한 프로그래밍 방법이 궁금하다면, 부록2 참조.
부록2에서는 위의 add함수를 작성하고 테스트하는 것을, 스텝별로 자세히 설명함
* 만약에 bigint.c와 bigint.h만을 작성한 수 빌드했을 때, 다음과 같이 "진입점이 정의되어야 합니다'"라는 에러가 떴다면,
이것은 main함수가 정의되지 않어서 생기는 오류이다.
이 오류를 없애기 위해서는 1)main함수 작성 2)main함수가 없어도 오류가 뜨지않도록 세팅
2)번 해결안인 main함수가 없어도 오류가 뜨지 않도록 하기 위해서는 다음과 같이 하면 된다.
- 솔루션 속성에서(솔루션 탐색기에서 해당 솔루션 누르고 마우스 우클릭), "구성 속성/링커/고급"에서 '진입점 없음'을 "예"로 설정
- The Art of Computer Programming Volumn 2 4.3.1 [본문으로]
'암호화프로그래밍 > (Old)C-BIGINT' 카테고리의 다른 글
| 008. 테스트: 덧셈, 증가 (0) | 2013.07.30 |
|---|---|
| 007. 증가(increse) (0) | 2013.07.29 |
| 005. 큰 수에 대한 프로그래밍 (0) | 2013.06.19 |
| 004. 큰 수 (0) | 2013.06.19 |
| 003. 목차 (not fixed yet) (0) | 2013.06.19 |