009. 뺄셈(subtract)

암호화프로그래밍/(Old)C-BIGINT

009. 뺄셈(subtract)

산을좋아한라쯔 2013. 7. 30. 10:55

2.3 뺄셈

앞 장에서 큰 수에 대한 첫 번째 연산으로 덧셈을 알아 봤다. 이번 장은 뺄셈이다.

뺄셈에 대한 알고리즘은 덧셈과 유사하다. 같은 자리끼리 더하는 것 대신에 빼주면 되고, 덧셈에서 올림이 발생한 반면, 뺄셈에서는 빌림(borrow)이 발생하는 것이 차이다.

뺄셈 알고리즘¹

이 알고리즘은, 음이 아닌 n자리 정수 U=(u_n-1...u₁u₀)_b와 V=(v_n-1...v₁v₀)_b가 주어졌을 때, 정수U와 정수V의 차 W=(w_n-1...w₁w₀)_b을 구한다.

S1.[초기화]

j ← 0, k ← 0

S2.[두 수 빼기]

w_j ← (u_j - v_j + k)mod b, k ← ⌊(u_j + v_j + k)/b⌋ (⌊ ⌋ :내림. floor)

S3. [j에 대한 루프]

j ← j + 1

if(j < n) goto S2

else w_n ← k, goto END

END

S1.[초기화]

j는 0에서 n-1까지 루프를 돌리기 위한 변수. zero로 초기화

k는 빌림값을 저장하기 위한 변수. 빌림값은 항상 0 혹은 -1

S2. [두 수 빼기]

두 수는 0~(b-1)까지의 임의의 수이다. 즉, 최소값은 0이고 최대값은 b-1

k는 빌림수(borrow)를 저장하게 되는데, 내림수는 항상 0 아니면 -1이다.

(u_j - v_j + k)의 범위를 구해보면, 최소값은 u와 k가 최소이고 v가 최대일때의 값이므로, (0 - (b-1) + (-1)) = -b

최대값은 u와 k가 최대이고 v가 최소일때의 값이므로, ((b-1) - 0 + 0) = b-1

따라서, -b < (u_j - v_j + k) < b

+b를 더해주면 0 < (u_j - v_j + k + b) < 2b 가 되고, 따라서, 이 부분을 코딩할 때는 2b-1까지 처리할 수 있는 변수 필요

두 수를 뺀 후 borrow를 더한 값(borrow가 0 혹은 -1이므로, 사실은 borrow를 뺀다는 표현이 더 적절)이 기수 b보다 작으면 그대로 결과값으로 넣고, 더한 값이 기수 이상이면 기수 b로 mod한 값(=기수b로 나눈 후 나머지값)으로 한다.

빌림값 k는, 계산된 값을 b로 나눈 후 가장 가까운 정수로 내림한다.

S3. [j에 대한 루프]

j를 증가시키면서 즉, 높은 자리로 하나씩 이동하면서 n-1까지 S2를 반복한다. 제일 마지막인 n-1에 와서는, 빌림값 k는 항상 0이다. 왜냐하면 u > v라고 가정했기 때문.

이제 이 알고리즘을 좀 더 현실감있게(실제 C 프로그래밍에 적합하게) 보완해보자

(위의 알고리즘은 "The Art of Computer Programming"에서 제시된 것과 일치하는 것이고, 그것을 이 글에서 보완해서 프로그래밍 하자는 것)

보완된 사항은 세 가지.

더하려는 두 수의 자릿수 크기가 다른 경우 고려
두 수의 뺄셈을 처리하는 임시변수 고려
mod연산과 내림연산 대신에 보다 간단한 연산 적용
음수에 대한 계산도 고려

보완된 뺄셈 알고리즘

이 알고리즘은, n자리 정수 U=(u_m-1...u₁u₀)_b와 V=(v_n-1...v₁v₀)_b가 주어졌을 때, 정수U와 정수V의 차 W=(w_p-1...w₁w₀)_b을 구한다. 여기서 p는 m과 n중에서 큰 값.

[조건1] U와 V의 부호가 다른 경우: 덧셈으로 계산

[조건2] U와 V의 부호가 같을 경우

S1. [크기 비교]

주어진 두 수 U, V의 크기를 비교해서(자릿수 만이 아닌 실제 크기 비교), 큰 쪽을 L로하고 작은 쪽을 S로 대치

(L:Large S:Small) 만약 크기가 같다면 결과값은 zero가 되고 알고리즘 종료

if(m > n) L = U, S = V

else if(m < n) L = V, S = U, S7실행

else 결과값=0, goto END

S2. [초기화]

k ← 0, j ← 0

S3. [뺄셈: S 자릿수 내]

t = (l_j - s_j - k) ;-k 했음에 유의. 즉, k=0 혹은 1

w_j = t mod b

k = ⌊t/b⌋

S4. [루프: S] 작은 수인 S의 자릿수까지 j 증가

j ← j + 1

if(j < S자릿수) goto S3

else goto S5

S5. [뺄셈: L 자릿수 내]

t = (l_j - k)

w_j = t mod b

k = ⌊t/b⌋

S6. [루프: L] 큰 수인 L의 자릿수까지 j 증가

j ← j + 1

if(j < L자릿수) goto S5

else w_p ← k, goto END

S7. [부호변경]

만약 [(양수U, 양수V)이고 (|U| < |V|)] 혹은 [(음수U, 음수V) 이고 (|U| > |V|)]이면 결과값을 음수로 변환

END

[조건1] U와 V의 부호가 다른 경우: 덧셈으로 계산

음수를 고려하지 않고 U와 V가 둘 다 양수라면 알고리즘은 좀 더 간단하지만, 음수를 고려해야하기에 다음과 같은 경우의 수를 나눠서 알고리즘을 구현한다.

U	V	\|U\| ? \|V\|	C	예				프로그래밍
U	V	\|U\| ? \|V\|	C	U	V	U-V	C	프로그래밍
양수	음수	N/A	양수	3	-4(0xFC)	3-(-4)	7	(U+V)
음수	양수	N/A	음수	-3(0xFD)	4	(-3)-(4)	-7	-((-U)+(-V))
양수	양수	>	양수	4	3	4-3	1	U-V
양수	양수	<	음수	3	4	3-4	-1	-(V-U)
음수	음수	>	음수	-4(0xFC)	-3(0xFD)	(-4)-(-3)=FC-FD	-1	-(V-U)=-(FD-FC)
음수	음수	<	양수	-3(0xFD)	-4(0xFC)	(-3)-(-4)	1	(U-V)=(FD-FC)

U가 양수, V가 음수의 경우 U-V는 U + |V|와 같기에, V를 양수값으로 바꾸고 덧셈으로 계산한다.

U가 음수, V가 양수의 경우는, U를 양수값으로 바꿔서 합을 구한 후, 결과값을 음수로 변환한다.

두 수의 부호가 다른 경우는 절대값이 큰 쪽에서 작은쪽으로 뺄셈을 하고 난 후, [(양수,양수) && ( |U| < |V|)]의 경우와 [(음수,음수) && ( |U| > |V|)]의 경우에 결과값에 대해 음수처리 해준다.

아래는, 이 경우의 상세 알고리즘이다.

[조건2] U와 V의 부호가 같을 경우S1. [크기 비교]

주어진 두 수 m과 n의 크기를 비교한다. 덧셈의 경우 자릿수 크기만을 비교해도 충분하나, 뺄셈의 경우는 자릿수 뿐만 아니라, 실제 크기를 비교한다.

크기가 같다면 두 수의 차는 zero가 될 것이고 바로 알고리즘이 종료된다.

S2. [초기화]

k는 빌림(borrow)용으로, j는 루프 증가용. 둘 다 zero로 초기화

S3. [뺄셈: S 자릿수 내]

S4. [루프: S] 작은 수인 S의 자릿수까지 j 증가

작은 수의 자릿수 범위내에서의 빼기.

여기서 (l - v - k)의 범위를 보면 -b < (l - v - k) < b 이므로, 구현할 때는 이 범위를 처리할 수 있는 큰 변수로 선언하는 것 유의

S5. [뺄셈: L 자릿수 내]

S6. [루프: L] 큰 수인 L의 자릿수까지 j 증가

작은 수 S보다 큰 자릿수에 대한 더하기를 한다. 더 이상 S의 값이 존재하지 않으므로, L에서 k값만 뺀다.

주의할 것은 L의 끝 자리까지 k를 계속해서 빼줘야 한다는 것이다. 왜냐하면 계속해서 빌림이 발생할 수도 있기 때문이다.

S7. [부호변경]

만약 [(양수U, 양수V)이고 (|U| < |V|)] 혹은 [(음수U, 음수V) 이고 (|U| > |V|)]이면 결과값을 음수로 변환

이제 위 알고리즘대로 두 수에 대한 뺄셈함수를 구현해 보자

//file: biging.c

/***************************************************************************************
두 수의 차를 구함
input:	BIGINT A, BIGINT B
output: BIGINT C (C = A - B)
return:	OK - if all ok
		E_Overflow - 두 수를 뺀 값이 BigInt로 표현할 수 있는 수 범위를 벗어난 경우
****************************************************************************************/
int subtract(BIGINT A, BIGINT B, BIGINT C){	
	INT *L, *S, *W;	
	INT *LE, *SE;
	DINT t;
	INT k;//borrow
	int ret, cmpResult = 0;	
	int signA, signB;

함수명은 subtract로 하고, 파라미터로 두 수 A, B와, 두 수를 뺀 결과값이 저장될 C를 받도록 한다.

(add함수와 동일한 구조)

지역변수로 *L, *S, *W를 선언한다.

L은 두 수 A,B중에서 큰 수, S는 작은 수, W는 결과값 저장될 C의 주소를 가르키게 될 것이다. (정확하게는 큰 수를 나타내는 배열의 두번째 인자 주소. 첫번째 인자는 크기를 나타내므로)

지역변수 *LE, *SE는 각각 해당 BIGINT의 마지막 위치를 나타내게 될 것이다.

t는 DINT로 정의한다. DINT는 INT형의 두 배 메모리를 차지한다. 즉, INT가 long타입으로 32비트이면 long long타입으로 64비트.

t의 존재이유는 두수의 차(정확하게는 두 수의 차와, 빌림수의 차)을 계산할 중간 버퍼로 사용되기 위해서이다.

k는 빌림수(borrow)를 저장할 변수이다. 여기서 빌림수는 항상 0 혹은 1이다. 따라서 1바이트 메모리로도 충분해서 char 혹은 short형으로 선언해도 무방하나, INT로 선언해도 그리 메모리 손실이 아니고, 어차피 INT형 수와 더하는 데 사용되면서 INT형으로 자동 형변환이 될 것이기에, INT로 선언한다.

(add함수에서 올림수와 유사)

signA, signB는 A와 B의 부호값을 저장하는데 사용된다.

        //부호가 다른 경우는 add로 계산
	signA = isPositive(A);
	signB = isPositive(B);
	if((signA * signB) < 0){ //부호가 다른경우
		if(signA == 1) { //양수 - 음수 -> 양수 + 양수
			positive(B);
			return add(A,B,C);
		}else{ //음수 - 양수 = -[양수+양수]
			positive(A);
			ret = add(A,B,C);			
			negative(C);
			return ret;
		}
	}

두 수의 부호를 알아내서 signA와 signB에 저장해 둔다. 부호는 isPositive함수로 알아낼 수 있는데, 이 부호값이 함수내에서 여러번 사용되므로 다시 알아내는 수고를 덜하기 위해 변수로 저장해 두자

isPositive함수는 다음과 같이, 양수이면 1을, 음수이면 -1을 리턴한다.

BigInt에서 음수를 2의 보수로 나타내기로 했기에, 음수는 항상 BigInt의 최대 길이를 가지면 가장 상위의 값이 MAX_POSITIVE(=0x7fffffff)보다 큰 값을 가지게 된다. 이를 이용해서 음수인지 양수인지를 판별한다. (1바이트 수 체계에서 음수는 0x7f보다 큰 경우임을 생각하면 이해하기 쉽다.)

int isPositive(BIGINT A){
	if( (*A == MAX_INT_LEN) && (*(A+MAX_INT_LEN) > MAX_POSITIVE))
		return -1;
	else
		return 1;	
}

두 수의 부호가 다른 경우는, 두 수의 부호값을 곱했을 때 음수인 경우이다.

이 경우는 두 수의 덧셈을 이용해서 계산해야 한다.

예를 들어, A가 양수, B가 음수의 경우, A-B의 결과값은 항상 양수가 된다. 예를 들어 4 - (-3) = 4 + 3 = 7

따라서, 음수B를 양수로 만들고 난 후 A와의 합을 하면 결과값이 된다.

A가 음수, B가 양수의 경우는 A-B의 결과값은 항상 음수가 된다. 예를 들어 (-4) - 3 = -7

따라서 A를 양수로 바꾸고 B와 더한 다음에, 나온 결과값을 음수로 바꿔주면 되겠다.

여기서 주어진 BigInt값을 양수로 바꾸는 함수는 positive, 음수로 바꾸는 함수는 negative인데, 구현은 다음과 같이 된다.

/***************************************************************************************
주어진 BIGINT값을 음수로 변환
이 때 음수의 표현은 2의 보수 형태
즉,
00101 -> 11010 -> 11011
input:	BIGINT A 음수로 변환할 BIGINT값
output: BIGINT A 2의보수 형태로 변환된 값
return:	OK	
****************************************************************************************/
int negative(BIGINT A){
	INT *a = A;
	INT *ae = A + SIZE(A);
	//1. if zero --> do nothing
	if(*(a+1) == 0) return OK;
	//2. 1's complement
	while(++a <= ae){
		*a = ~(*a);
	}
	//3. +1
	//앞에서 zero인 경우에 대해서 처리했기에, 1의 보수에 의해 MAX된 후, 
        //increse에 의해 overflow가 발생되는 경우 없음
	increse(A);
	//4. fill with FF upto the MAX
	SET_SIZE(A,MAX_INT_LEN);
	while(++ae <= (A+MAX_INT_LEN)){
		*ae = MAX_INT;
	}
	return OK;
}

/***************************************************************************************
주어진 음수BIGINT값을 양수로 변환
이 때 음수의 표현은 2의 보수 형태
즉,
11011 -> 00100 -> 00101
input:	BIGINT A 양수로 변환할 음수BIGINT값
output: BIGINT A 2의보수 형태로 변환된 값
return:	OK	
****************************************************************************************/
int positive(BIGINT A){
	INT *a = A;
	INT *ae = A + SIZE(A);
	//1. if zero --> do nothing
	if(*(a+1) == 0) return OK;
  
	//2. 1's complement
	while(++a <= ae){
		*a = ~(*a);
	}
  
	//3. +1
	//앞에서 zero인 경우에 대해서 처리했기에, 1의 보수에 의해 MAX된 후, 
        //increse에 의해 overflow가 발생되는 경우 없음
	increse(A);
	//4. remove zero
	REMOVE_ZERO(A);
  
	return OK;
}

        //S1.[크기비교] L = (A > B) ==> A : B
	cmpResult = compare_big(A,B);
	switch(cmpResult){
	case 0:
		C[0] = 0;
		return OK;
	case 1: //A > B
		L = A +1;
		LE = A + SIZE(A);
		S = B + 1;
		SE = B + SIZE(B);
		SET_SIZE(C, SIZE(A));
		break;
	case -1:		
		L = B +1;
		LE = B + SIZE(B);
		S = A + 1;
		SE = A + SIZE(A);
		SET_SIZE(C, SIZE(B));
		break;
	}
	W = C + 1;

S1에서는 더할 두 수주에서 어느쪽이 큰 수인지 판단해서(자릿수만이 아닌 같은 자릿수라도 실제 크기 비교), L이 큰 수를 가르키게하고, S가 작은 수를 가르키게 한다. (add함수에서는 자릿수만 비교해도 충분 했었음)

BIGINT 두 수의 크기 비교는 compare_big함수에서 하도록 되어 있다.

/**************************************************************************
compare two BIGINT value
Input: @a, @b
Returns: 
		1 : a > b
		0 : a==b
		-1: a < b
***************************************************************************/
int compare_big(BIGINT a, BIGINT b){	
	int lenA, lenB;
	INT *posA, *posB; 
	//1. check len is not zero
	lenA = (int)*a;
	lenB = (int)*b;
	if(lenA == 0 && lenB == 0) return 0;
  
	//2. check non zero value len and compare length
	while(a[lenA]==0 && lenA>0) --lenA;
	while(b[lenB]==0 && lenB>0) --lenB;
	if(lenA == 0 && lenB == 0) return 0;
	if(lenA > lenB) return 1;
	if(lenA < lenB) return -1;
  
	//3. case:lenA == lenB
	posA = a + lenA;
	posB = b + lenB;
	while( (*posA == *posB) && (posA > a)){
		posA--;
		posB--;
	}
	if(posA == a) return 0;
	if(*posA > *posB) return 1;
	else	return -1;
}

compare_big함수에의해, 만약 A가 크다면 1이 리턴되고, B가 크다면 -1이, 두 수가 같다면 0가 리턴된다.

두 수가 같은 경우, 두 수의 차는 0이다. 따라서, cmpResult가 0인 경우, zero를 리턴하고 종료.

A가 큰 경우는 L에 A가 지정되고, B가 큰 경우는 L에 B가 지정된다.

두 수의 합을 저장하게될 C의 크기는, A, B중 큰 수의 자릿수와 같거나 작게 된다. 즉, A가 5자리, B가 3자리이면, C는 5자리이하가 된다.

일단 C의 자릿수를 두 수중 큰쪽 자릿수로 지정하고, 결과값에서 앞자리 부터 zero인 경우를 없애나가면서 실제 자릿수를 정할 것이다.(S5,S6 이후)

        //S2.[초기화] k=0
	k = ZERO;

S2.는 사용될 변수를 초기화 한다. k는 빌림을 저장할 변수. 초기 빌림값은 zero라야 하므로 0으로 초기화.

ZERO는 biging.h에서 0L 혹은 0로 선언되어 있다.

                //S3. S4. 두 수 빼기. 오른쪽에서 왼쪽으로 until small_end	
	while(S <= SE){
		t = (DINT)*L++ - (DINT)*S++ - (DINT)k;
		*W++ = (INT)t;
		k = (INT)((DINT)(t & BASE) >> (sizeof(INT)*8)); //0 or 1
	}

작은 수의 자릿수 내에서 뺄셈을 수행한다.

먼저 DINT형 변수인 t에 두 수의 차와 빌림수를 빼고, 최종 결과를 보관할 C의 주소를 가르키고 있는 W에는 t를 INT형에 해당하는 밑수로 modula연산한 값을, k는 t가 밑수보다 큰지 여부에 따라 1 혹은 0이 되게 한다.

먼저 t의 계산은, t가 DINT형이기에, INT형 변수들을 DINT로 캐스팅한 후 계산한다.

W에는 t mod BASE을 한 값이 들어가게 될텐데, 간단하게 DINT변수인 t를 INT로 캐스팅해주면 동일한 효과를 볼수 있겠다. 즉, DINT가 8바이트이면, W에는 4바이트까지의 t값이 들어가게되는 것이고, 이는 modular연산과 동일하게 됨

k에는 1 또는 0값이 들어가게 되는데, (t-2³²)의 값이 양수이면(INT가 32비트의 경우) 1 아니면 0으로 처리할 수도 있으나, (INT)(t/2³²)와 동일한 효과를 나타내는 t값을 INT형 비트만큼 오른쪽 쉬프트시키는 것으로 처리하는 것이 더 효율적일 것임

                //S5. S6. large값에다 borrow 빼기
	while(L <= LE){
		t = (DINT)*L++ - (DINT)k;
		*W++ = (INT)t;
		k = (INT)((DINT)(t & BASE) >> (sizeof(INT)*8)); //0 or 1
	}
	//remove zeroes
	REMOVE_ZERO(C);

S5. S6. 에서는 큰수의 자릿수내에서 뺄셈 수행.

만약 두 수 A, B의 자릿수가 같다면, 이 부분은 수행되지 않는다. 왜냐하면 자릿수 크기가 같다면 (SE-S)==(LE-L)이되고, S3. S4 에서 while(S <= SE)될 때까지 L의 주소값이 증가되었기에, S5.S6. 스텝의 while(L <= LE)부분은 수행되지 않음

자릿수가 다른 경우는, 큰 수와 빌림수만을 빼서 결과값 처리.

마지막 자리까지 계산이 다 된 후에는, 계산된 결과값에서 앞부분 zero를 없애는 과정을 수행한다. 즉, 결과값이 빼는 두 수중 큰 값과 자릿수가 동일하다고 세팅해놓고 계산을 했는데, 만약 결과값이 큰 수의 자릿수보다 작다면(많은 경우가 이에 해당), 그 자릿수를 작게 해줘야하는 것이다.

자릿수를 실제값에 맞게 맞춰주는 역할은 매크로인 REMOVE_ZERO에서 수행된다.

#define REMOVE_ZERO(n)		while((SIZE(n)>0) && (*((n) + SIZE(n)) == 0)) --*(n);

이 매크로는, 주어진 BIGINT의 가장 큰 자릿수에 있는 값을 확인해서, 값이 zero이면 자릿수를 하나 감소시킨다. 이런 과정을 반복해서 가장 큰 자릿수의 값이 zero가 되지 않을 때까지 반복하면서 자릿수 조정을 한다.

//S7.[underflow] if(m < n) return underflow
	if(cmpResult == -1){		
		return E_Underflow;
	}
	return OK;

만약 작은 수에서 큰 수를 빼는 경우이면, 값이 음수가 나올것이기에 underflow를 리턴한다.

소스

subtract함수에 대한 전체 소스는 다음과 같다. (bingint.c에 구현)

/***************************************************************************************
두 수의 차를 구함
input:	BIGINT A, BIGINT B
output: BIGINT C (C = A - B)
return:	OK - if all ok
		E_Underflow - 두 수를 뺀 값이 음수인 경우
****************************************************************************************/
int subtract(BIGINT A, BIGINT B, BIGINT C){	
	INT *L, *S, *W;	
	INT *LE, *SE;
	DINT t;
	INT k;//borrow
	int cmpResult = 0;	
	//S1.[크기비교] L = (A > B) ==> A : B
	cmpResult = compare_big(A,B);
	switch(cmpResult){
	case 0:
		C[0] = 0;
		return OK;
	case 1: //A > B
		L = A +1;
		LE = A + SIZE(A);
		S = B + 1;
		SE = B + SIZE(B);
		SET_SIZE(C, SIZE(A));
		break;
	case -1:		
		L = B +1;
		LE = B + SIZE(B);
		S = A + 1;
		SE = A + SIZE(A);
		SET_SIZE(C, SIZE(B));
		break;
	}
	W = C + 1;
	//S2.[초기화] k=0
	k = ZERO; 
	//S3. S4. 두 수 빼기. 오른쪽에서 왼쪽으로 until small_end	
	while(S <= SE){
		t = (DINT)*L++ - (DINT)*S++ - (DINT)k;
		*W++ = (INT)t;
		k = (INT)((DINT)(t & BASE) >> (sizeof(INT)*8)); //0 or 1
	}
	//S5. S6. large값에다 borrow 빼기
	while(L <= LE){
		t = (DINT)*L++ - (DINT)k;
		*W++ = (INT)t;
		k = (INT)((DINT)(t & BASE) >> (sizeof(INT)*8)); //0 or 1
	}
	//remove zeroes
	REMOVE_ZERO(C);
	//S7.[underflow] if(m < n) return underflow
	if(cmpResult == -1){		
		return E_Underflow;
	}
	return OK;
}

테스트

작성된 subtract함수에 대해서는 아래와 같이 6가지 테스트를 하면 될 것이다.

작은 수에 대한 연산
자릿수가 A>B인 경우
자릿수가 A<B인 경우
자릿수가 같으면서 A>B인 경우
자릿수가 같으면서 A>B인 경우
항등원 0과의 차

소스는 다음과 같이 될 것이다. (test.c에 구현)

int test_subtract(){
	BIGINT a,b,c;
	BIGINT expected;
	int result=-1;
	int ret=-1;
	//1. 작은 수에 대한 연산
	hexstr2bigint("0a",a);
	hexstr2bigint("01",b);
	hexstr2bigint("09",expected);
	subtract(a,b,c);
	result = compare_big(c,expected);
	if(result != 0)
		return result;
	//2. 자릿수가 A>B의 경우
	//112233445566778899aabbcc
	//            112233445566
	//11223344556688aaccef1132
	hexstr2bigint("112233445566778899aabbcc",a);
	hexstr2bigint("112233445566",b);
	hexstr2bigint("112233445566666666666666",expected);
	subtract(a,b,c);
	result = compare_big(c,expected);
	if(result != 0)
		return result;
	//3. 자릿수가 A<B의 경우
	hexstr2bigint("88776655",a);
	hexstr2bigint("99999999",b);
	hexstr2bigint("11223344",expected);
	ret = subtract(a,b,c);
	if(ret != E_Underflow) return ret;
	result = compare_big(c,expected);
	if(result != 0)	return result;
	//4. 자릿수가 같으면서 A>B인 경우
	hexstr2bigint("ff112233445566778899aabbcc",a);
	hexstr2bigint("ee112233445566778899aabbcc",b);
	hexstr2bigint("11000000000000000000000000",expected);
	subtract(a,b,c);
	result = compare_big(c,expected);
	if(result != 0)
		return result;
	//5. 자릿수가 같으면선 A<B인 경우
	hexstr2bigint("ff112233445566778899aabbcc",a);
	hexstr2bigint("ff112233445566778899aabbbb",b);
	hexstr2bigint("11",expected);
	ret = subtract(a,b,c);
	if(ret != E_Underflow) return ret;
	result = compare_big(c,expected);
	if(result != 0)	return result;
	//6. 항등원 0과의 차
	hexstr2bigint("ff112233445566778899aabbcc",a);
	b[0]=0;	
	hexstr2bigint("ff112233445566778899aabbcc",expected);
	subtract(a,b,c);
	result = compare_big(c,expected);
	if(result != 0)
		return result;
	return 0;	
}

Visual Studio용 프로젝트 파일; subtract함수 추가 (add함수도 포함되어 있음)

003.Subtract.zip

* 제공되는 프로젝트 파일은, 앞에서 작성한 함수들도 포함된 상태로 배포될 것이다.

위 프로젝트를 실행해보면 다음과 같이 add, increse, subtract함수에 대해 테스트를 한 결과가 나올 것이다.

The Art of Computer Programming Volumn 2 4.3.1 [본문으로]

003.Subtract.zip

0.82MB

저작자표시 비영리 변경금지

'암호화프로그래밍 > (Old)C-BIGINT' 카테고리의 다른 글

011. 곱셈(multiply) (0)	2013.07.30
010. 감소(decrese) (0)	2013.07.30
008. 테스트: 덧셈, 증가 (0)	2013.07.30
007. 증가(increse) (0)	2013.07.29
006. 덧셈(add) (0)	2013.06.20

현재글009. 뺄셈(subtract)

비트코인 논문 번역, 블록체인 번역, wavelength, protection remove, CIE, bitcoin 번역, Block Chain, excel crack, 엑셀 크렉, 사토시 논문, 비트코인 번역본, Fourier, 보호 해제, DFT, FFT, 비트코인 번역, excel vba, 파장, RGB, 시트보호,

Today :
Yesterday :

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

컴퓨터 프로그래밍(암호학, 알고리즘)