2.5 곱셈(multiply)
덧셈/증가 그리고 뺄셈/감소에 이어 곱셈에 대해 알아보자.
곱셈도 알고리즘이 그리 어렵지 않다. 덧셈 뺄셈과 마찬가지로 손으로 곱셈을 계산하는 방법을 그대로 구현하면 된다.
수행횟수는 덧셈/뺄셈이 O(n)정도를 보이는데 반해, 곱셈은 O(mn) 정도를 보인다. (m과 n은 곱하려는 두 수의 자릿수)
* O(n) : n이 커짐에 따라 n만큼의 수행횟수 증가를 보이는 알고리즘. O(n2)은 n이 증가함에 따라 n2으로 수행횟수가 많아짐을 나타냄
알고리즘
이 알고리즘은, 음이 아닌 n자리 정수 U=(um-1...u1u0)b와 V=(vn-1...v1v0)b가 주어졌을 때, 정수U와 정수V의 곱 W=(wm+n-1...w1w0)b을 구한다.
S1.[초기화]
wm-1 ← 0, ... w1 ← 0, w0 ← 0
j←0
S2.[곱수가 0?]
만일 vj = 0 이라면, wj+m ← 0으로 설정하고 goto S6
S3.[i 초기화]
i←0 , k←0
S4. [곱셈 & 덧셈]
t ← ui x vj + wi+j +k
wi+j = t mod b
k = ⌊t/b⌋ (k는 항상 0 <= k < b)
S5. [i에 대한 루프]
i ← i + 1
if(i < m) goto S4
else wj+m ← k
S6.[j에 대한 루프]
j ← j + 1
if(j < n) goto S2
else goto END
END
S1.[초기화]
j는 0에서 n-1까지 루프를 돌리기 위한 변수. zero로 초기화
곱한 결과값을 저장할 w의 모든 값을 zero로 초기화.
S2. [곱수가 0?]
곱할값 v가 0이라면 u와의 곱을 할 필요없다. 만약 이 판단이 없다면 0임에도 불구하고 n-1회 루틴 돌게되므로 비효율.(사실 v가 0가 될 확률은 굉장히 낮다. 따라서, v에 대한 판단하는 이 스텝은 생략해도 무방)
S3. [i 초기화]
v의 자릿수만큼 루프를 도는데 사용될 i값과 carry값을 저장할 k에 대해 초기화
S4. [곱셈 & 덧셈]
두 수의 곱을 구한다. 이 때, 손으로 써가면서 곱셈을 할 때와 다르게 이미 계산된 곱셈결과값을 더하면서 진행해 나간다. 즉,
t ← ui x vj + wi+j +k (여기서 wi+j + k는 결과값으로, 곱셈이 이뤄질 때마다 해당 자릿수의 결과값을 누적해서 더해나간다.)
여기서 t의 최대값은 u, v, w, k가 최대일때이므로,
(b-1) x (b-1) + (b-1) + (b-1) = b2 - 1 < b2
따라서 t에 해당하는 변수는 b2을 처리할 수 있는 변수라야 함 (만약 b=232이면 b2=264. 즉, 64비트의 long형 변수이면 됨)
wi+j = t mod b (덧셈, 뺄셈에서와 마찬가지로, 결과값은 b보다 작은값 즉, b로 modulo연산)
k = ⌊t/b⌋ (k는 항상 0 <= k < b)
S5. [i에 대한 루프]
u의 자릿수를 나타내는 i를 i<m까지 증가
S6. [j에 대한 루프]
v의 자릿수를 나타내는 j를 j<n까지 증가
위의 알고리즘을 876 x 32을 수행하는 것으로 설명해보자 (b=10인 경우. 즉, 십진수의 경우)
손으로는 아래와 같이 계산될 것이다.
876 x 32 이므로, u=876 v=32 m=3 n=2
u2=8 u1=7 u0=6
v1=3 v0=2
w는 (m+n)자릿수를 가지므로 5자리
이 정보를 가지고 알고리즘대로 손으로 따라가 보면 아래와 같이 계산된다. (엑셀 혹은 손으로 계산해보기 바람)
위의 예는 십진수(b=10)의 경우이고, 만약 b=232(32비트=4바이트)라면 다음과 같이 계산될 것이다.
u = 0x1122 33445566
v = 0x 3344 55667788 99AABBCC
프로그래밍
이제 위에서 작성된 알고리즘을 기반으로 해서 두 양의정수에 대한 곱셈을 수행하는 함수 multiply_positive를 프로그래밍해본다.
/*************************************************************************************** 두 자연수(양의정수)에 대한 곱셈int multiply_positive(BIGINT A, BIGINT B, BIGINT C){ INT W[MAX_INT_LEN + 2] = {0,}; INT *u, *ue, *v, *ve, *w, *we; DINT t; INT k; //carry int m,n,l; //m:SIZE(A) n:SIZE(B) l:SIZE(C) int i,j;input: BIGINT A, BIGINT B : should be positive value output: BIGINT C 두 수의 곱 C = A x B return: OK - if all ok E_Overflow - 곱한 결과가 BIGINT범위를 벗어날 경우. 이 경우, C를 변화시키지 않음 ****************************************************************************************/
함수명은 multiply이고, 인자는 곱할 두 수 A, B와 곱해진 결과를 저장할 값 C
곱셈 계산값을 처리할 변수로 (MAX_INT_LEN+2)크기의 변수를 선언해서 사용한다. BIGINT보다 1 더 큰 메모리를 할당하는 이유는, 두 수의 자릿수 합이 MAX_INT_LEN보다 1 더 큰 경우를 처리하기 위해서이다. 이 경우도 계산결과에 따라 overflow가 아닌 MAX_INT_LEN자릿수로 될 수 있기 때문.
각 BIGINT값을 가르키는 변수들 (*u, *ue, *v, *ve, *w, *we) 선언. 이 포인트 변수를 이용해서 계산 진행할 것임
t는 실제 곱셈연산과 덧셈을 저장할 변수. INT의 두 배되는 DINT로 선언해야함
i,j는 루프돌리기 위한 변수
m = SIZE(A); n = SIZE(B); l = m + n;
//overflow if(l > (MAX_INT_LEN+1)){ return E_Overflow; }
0보다 큰 입력값을 가정하기에 두 수가 0인 경우는 고려하지 않는다. (고려한다면 두 수중 하나라도 0이면 결과값이 0이되게 구현 필요)
크기정보(각 BIGINT의 자릿수)를 나타내는 변수 m, n, l 정하기.
곱셈 결과값의 크기는 두 수 A, B의 크기에 의해 결정된다. 이 때, 자릿수의 최대 크기는 곱할 두 수의 자릿수 합.
만약 A의 자릿수가 3이고(m=3), B의 자릿수가 2(n=2)이면, 결과값 C는 최대 5자리 수가 된다. 여기서, 최대가 5자리라는 얘기이고 5보다 작은 자릿수가 될 수도 있다. 따라서, 계산을 다하고 난 후에 자릿수 보정을 해줘야한다. (매크로 REMOVE_ZERO 이용)
예상되는 결과값의 자릿수가 BIGINT가 처리할 수 있는 최대 자릿수를 확실히 넘어선다면 overflow로 처리하고 함수를 종료한다. 확실히 넘는다는 것은 (MAX_INT_LEN+1)보다 클 때이다. (MAX_INT_LEN+1)과 같은 경우는, 최대 자릿수 값을 확인해봐야 Overflow인지 아닌지를 확인할 수 있다. 곱셈 계산을 다 한 후, Overflow가 되는지 확인하는 코드를 넣을 것이다.
//포인터 변수 지정
u = A + 1;
ue = A + m;
v = B + 1;
ve = B + n;
w = W + 1;
SET_SIZE(W,l);
we = W + SIZE(W);
포인터변수가 각 값을 가르키도록 지정.
we의 경우 W를 (l=m+n)크기로 지정하고 난 후, 지정했음에 유의
//S1. [초기화]
//j=0;
for(i=0;i<l;i++){
w[i] = (INT)0;
}
알고리즘에 있는 j에 대한 초기화는, 바로 이어지는 for루프에서 하기때문에 여기서는 삭제
곱셈 결과값을 저장할 메모리 전체는 zero로 초기화한다. i, j를 증가시키면서 곱셈을 하고 또한 해당 자릿수에 해당하는 w값을 더하는 것을 동시에 수행하기 때문에, 초기 w값 전체에 대해 0으로 초기화해댜하는 것이다.
for(j=0; j<n; j++){
//S2.[곱수가 0?]
/**
if(v[j] == 0){
w[j+m] = 0;
continue;
}
*/
//S3.[i 초기화]
//S4. [곱셈 & 덧셈]
//S5. [i에 대한 루프]
for(i=0, k=0; i<m; i++){
t = (DINT)u[i] * (DINT)v[j] + (DINT)w[i+j] + (DINT)k;
w[i+j] = (INT)t;
k = (INT)((DINT)t >> (sizeof(INT)*8));
}
w[j+m] = k;
}
알고리즘에 보면 vj가 zero인 경우 계산을 건너띄게되어 있다.
이 루틴이 필요한가에 대한 검토를 해보면, 결론은 큰 수에 대해서는 zero인지 판단하지 않는 것이 더 좋을 듯하고, 해서 코드에서는 주석처리했다. 왜냐하면, 큰 수의 경우 각 INT값이 zero가 되는 경우는 거의 없기 때문이다.
* 큰 수는 주로 암호학에서 사용되게 되는데, 암호학에서 큰 수는 난수인 경우가 대부분. 그렇다면 난수를 발생했을 때 32비트가 연속해서 0가 나오게 되는 경우는 무시해도 될 경우의 수임.
i에 대한 for루프에서 대부분의 계산이 이루어진다.
앞 장에서 다뤘던 덧셈, 뺄셈과 유사하게, DINT형 t에 계산값을 넣고, 결과값인 w에는 INT범위내(0~b-1) 값이 들어가도록 modulor값을 넣고, k에 올림값을 넣는다.
k값은 덧셈과 뺄셈의 경우는 0 혹은 1 이었으나, 곱셈의 경우 k의 범위는 (0 <= k < b)이다. 따라서, t값을 INT의 비트수 만큼 오른쪽 쉬프트해서 k값을 구한다.
i에 대한 루프가 끝나면, 남아 있는 올림수인 k를 w[j+m]으로 지정한다.
REMOVE_ZERO(W); if(SIZE(W) > MAX_INT_LEN){ SET_SIZE(W,MAX_INT_LEN); copy_big(C,W); return E_Overflow; }else{ copy_big(C,W); if(isPositive(C) == -1){ //자릿수를 over하진 않았지만 양의 최대값을 넘은 경우. return E_Overflow; } return OK; } }
i, j를 증가시키면서 for루프를 종료한 후에는, 계산된 결과값을 조사해서 앞부분 zero를 없앤다. 그리고 나서 W의 크기를 봤을 때, BIGINT가 허용할 수 있는 자릿수인 MAX_INT_LEN보다 큰 경우이면 Overflow처리 한다. 이 때, C의 값은 overflow되는 부분을 짤라내고 나머지 부분만을 지정하고 종료한다.
크기가 MAX_INT_LEN보다 작은 경우는 정상적인 경우로, 계산 결과값으로 임시 사용했던 W영역을 C영역으로 복사하고, 음수인지를 확인한다. 이것은 결과값이 BIGINT의 양수로서의 최대값을 넘어섰는지 확인하기 위해서이다.
이 경우를 1바이트 수체계에서 설명해보자.
1바이트 수체계에서 양수는 1~127까지이다. 16진수로 표현하면 0x01~0x7F이다.
0x80은 -128이되고 0x81=-127 ... 0xFF=-1 이다.
여기서 만약 2 x 70 = 140이 되는 계산을 하고자 한다면, 위 곱셈 알고리즘으로 구현했다면 0x2 x 0x46 = 0x8C = -116 이 되어 원하는 결과값인 140을 얻을 수 없다. (음수까지 지원하는 1바이트로는 127까지밖에 표현하지 못하므로, 표현하지 못한다는 말이 더 맞을 수도 있겠다.)
이처럼 BIGINT의 곱셈에서도 결과값이 표현할 수 있는 최대양수값을 넘어선 경우 Overflow를 리턴하고 종료한다.
* 그렇다면 1024비트의 수 체계를 사용한다고 할 때, 무리없이 곱셈을 할 수 있도록 어느 정도 크기로 BIGINT를 정의해야 할까? 답은 2048이다. m자리의 두 수를 곱했을 때 그 결과값에 대한 최대 자릿수는 m+m=2m이기 때문이다.
부호를 고려한 곱셈
이제 부호까지 고려한 곱셈을 해보자.
위의 알고리즘 및 multiply_positive는 두 수가 양수인 경우만 고려했다. 부호를 생각하면 첫째 두 수 중에 0이 있는지를 확인해야하고, 두번 째 두 수의 부호를 고려해서 결과값의 부호를 바꿔줘야 한다.
| A | B | C | 계산 |
| + | + | + | A*B |
| + | - | - | -(A*|B|) |
| - | + | - | -(|A|*B) |
| - | - | + | (|A|*|B|) |
즉, 둘 다 양수인 경우는 그대로 양수끼리의 곱셈함수를 이용해서 값을 구하면 되고, 음수가 있는 경우는 절대값의 곱셈을 하고나서 부호를 붙여주면 된다.
위 조건을 고려하면서 부호가 있는 BIGINT간의 곱셈을 수행하는 multiply함수는 다음과 같이 구현된다.
/*************************************************************************************** 두 정수의 곱셈 input: BIGINT A, BIGINT B output: BIGINT C 두 수의 곱 C = A x B return: OK - if all ok E_Overflow - 곱한 결과가 BIGINT범위를 벗어날 경우. 이 경우, C를 변화시키지 않음 ****************************************************************************************/ int multiply(BIGINT A, BIGINT B, BIGINT C){ int resultSign, ret; BIGINT absA, absB;//1. A,B 중 하나라도 zero이면 C = zero if((*A == 0) || (*B == 0)){ *C = 0; return OK; }
//2. 두 수의 부호에 따라, 결과값 부호 결정 resultSign = isPositive(A) * isPositive(B);
//3. 절대값(=양수)으로 변환 후 곱셈 //인자로 주어진 A,B값 자체를 변환시키지 않기위해, 복사본을 만들어 사용 copy_big(absA,A); abs(absA); copy_big(absB,B); abs(absB); ret = multiply_positive(absA,absB,C);
//4. 부호 결정 if(ret == OK){ if(resultSign == -1) return negative(C); else return OK; }else{ return ret; } }
위 multiply함수 소스를 보면 abs함수가 새롭게 사용되었다. 이 함수는 주어진 BIGINT값을 절대값(양수)로 바꿔준다.
/************************************************************************** 주어진 BIGINT을 절대값으로 변환 Input: @A: BIGINT to change to a absolute value if(A>0) A=A else A=-A Returns : OK ***************************************************************************/ int abs(BIGINT A){ if(isPositive(A) == -1) return positive(A); else return OK; }
테스트
multiply함수에 대한 테스트를 위해, 1바이트 수체계에서의 주의해야할 곱셈형태를 고민해 봤다.
| 입력 값(A) | 입력 값(B) | multiply | 비고 | |||
| Hex | Dec | Hex | Dec | Hex | Dec | |
| 00 | 0 | 03 | 3 | 00 | 0 | |
| 03 | 3 | 00 | 0 | 00 | 0 | |
| 01 | 1 | 03 | 3 | 03 | 3 | |
| 03 | 3 | 01 | 1 | 03 | 3 | |
| FF | -1 | 03 | 3 | FE | -3 | |
| FE | -2 | 03 | 3 | FA | -6 | |
| FE | -2 | FD | -3 | 06 | 6 | |
| 02 | 2 | 7F | 127 | n/a | n/a | overflow |
| FE | -2 | 7F | 127 | n/a | n/a | overflow |
| 02 | 2 | 46 | 70 | n/a | n/a | overflow |
위 사항을 고려하면 다음과 같은 테스트케이스가 나오겠다.
01. 0 x b = 0
02. a x 0 = 0
03. 1 x b = b
04. a x 1 = a
05. -1 x b = -b
06. -a x b = -ab
07. -a x -b = ab
08. overflow(양수 x 양의 최대값)
09. overflow(음수 x 양의 최대값)
10. a x b; len(a) > len(b)
11. a x b; len(a) < len(b)
아래는 위 테스트 케이스에 맞게 작성된 테스트함수 소스.
int test_multiply(){ BIGINT a,b,c; BIGINT expected; int result=-1; int ret=-1; int i; //01. 0 x b = 0 *a =0; hexstr2bigint("11223344",b); ret = multiply(a,b,c); *expected = 0; result = compare_big(c,expected); if((ret != OK) || (result != 0)) return -1; //02. a x 0 = 0 hexstr2bigint("11223344",a); *b =0; ret = multiply(a,b,c); *expected = 0; result = compare_big(c,expected); if((ret != OK) || (result != 0)) return -1; //03. 1 x b = b a[0] =1; a[1]=1; hexstr2bigint("1122",b); ret = multiply(a,b,c); expected[0] = 1; expected[1]=0x1122; result = compare_big(c,expected); if((ret != OK) || (result != 0)) return -1; //04. a x 1 = a hexstr2bigint("1122",a); b[0] =1; b[1]=1; ret = multiply(a,b,c); expected[0] = 1; expected[1]=0x1122; result = compare_big(c,expected); if((ret != OK) || (result != 0)) return -1; //05. -1 x b = -b hexstr2bigint("-1",a); hexstr2bigint("1122",b); ret = multiply(a,b,c); hexstr2bigint("-1122",expected); result = compare_big(c,expected); if((ret != OK) || (result != 0)) return -1; //06. -a x b = -ab hexstr2bigint("-112233445566",a); hexstr2bigint("112233",b); ret = multiply(a,b,c); hexstr2bigint("-01258F5C28F5BA8F52",expected); result = compare_big(c,expected); if((ret != OK) || (result != 0)) return -1; //07. -a x -b = ab hexstr2bigint("-112233445566",a); hexstr2bigint("-112233",b); ret = multiply(a,b,c); hexstr2bigint("01258F5C28F5BA8F52",expected); result = compare_big(c,expected); if((ret != OK) || (result != 0)) return -1; //08. overflow(양수 x 양의 최대값) hexstr2bigint("112233",a); b[0] = MAX_INT_LEN; for(i=1;i<MAX_INT_LEN;i++) b[i] = MAX_INT; b[MAX_INT_LEN] = MAX_POSITIVE; ret = multiply(a,b,c); if(ret != E_Overflow) return -1; //09. overflow(음수 x 양의 최대값) hexstr2bigint("-112233",a); b[0] = MAX_INT_LEN; for(i=1;i<MAX_INT_LEN;i++) b[i] = MAX_INT; b[MAX_INT_LEN] = MAX_POSITIVE; ret = multiply(a,b,c); if(ret != E_Overflow) return -1; //10. a x b; len(a) > len(b) hexstr2bigint("112233445566",a); hexstr2bigint("112233",b); ret = multiply(a,b,c); hexstr2bigint("01258F5C28F5BA8F52",expected); result = compare_big(c,expected); if((ret != OK) || (result != 0)) return -1; //11. a x b; len(a) < len(b) hexstr2bigint("112233445566",a); hexstr2bigint("33445566778899AABBCC",b); ret = multiply(a,b,c); hexstr2bigint("036E630371D028F5C28F4D4E70918F48",expected); result = compare_big(c,expected); if((ret != OK) || (result != 0)) return -1; return OK; }
프로젝트 파일(테스트 포함)
005.Multiply.zip
'암호화프로그래밍 > (Old)C-BIGINT' 카테고리의 다른 글
| 013. 나눗셈(divide) (0) | 2013.08.02 |
|---|---|
| 012. 제곱(square) (0) | 2013.07.31 |
| 010. 감소(decrese) (0) | 2013.07.30 |
| 009. 뺄셈(subtract) (0) | 2013.07.30 |
| 008. 테스트: 덧셈, 증가 (0) | 2013.07.30 |