컴퓨터 알고리즘 - 큰 정수곱셈 소스코드 및 분석

소개글

컴퓨터 알고리즘 - 큰 정수곱셈 소스코드 및 분석에 대한 보고서 자료입니다.

본문내용

------
large_integer Prod(large_integer u, large_integer v)
{
large_integer x = (char*)malloc(sizeof(char)*ARRAY_SIZE);
large_integer y = (char*)malloc(sizeof(char)*ARRAY_SIZE);
large_integer w = (char*)malloc(sizeof(char)*ARRAY_SIZE);
large_integer z = (char*)malloc(sizeof(char)*ARRAY_SIZE);
char *t1, *t2, *t3, *t4, *t5, *t6, *t7, *t8, *t9;
int n, m, num_of_u, num_of_v;
parray[count_of_array++] = x;
parray[count_of_array++] = y;
parray[count_of_array++] = z;
parray[count_of_array++] = w;
#ifdef CONFIRM_COUNT_OF_PROD
printf("Count_Of_Prod : %d\n", count_of_prod++);
#endif
num_of_u = NumCountOfArray(u);
num_of_v = NumCountOfArray(v);
n = Maximum(num_of_u, num_of_v);
if(num_of_u == 0 || num_of_v ==0)
{
return ZeroArray();
}
else if(n <= threshold )
{
return ArrayMultipleByNormalMethod(u, v);
}
else
{
m = (int)floor((double)(n/2));
GetDivideAndRem(u, m, x, y);
GetDivideAndRem(v, m, w, z);
t1 = Prod(x, w);
t2 = Prod(x, z);
t3 = Prod(w, y);
t4 = Prod(y, z);
t5 = PowArray(t1, (2*m));
t6 = AddArray(t2, t3);
t7 = PowArray(t6, m);
t8 = AddArray(t5, t7);
t9 = AddArray(t8, t4);
return t9;
}
}
//---------------------------------------------------------------------------
// 함수설명 : 배열과 배열을 곱하는 함수 2
//---------------------------------------------------------------------------
large_integer Prod2(large_integer u, large_integer v)
{
large_integer x = (char*)malloc(sizeof(char)*ARRAY_SIZE);
large_integer y = (char*)malloc(sizeof(char)*ARRAY_SIZE);
large_integer w = (char*)malloc(sizeof(char)*ARRAY_SIZE);
large_integer z = (char*)malloc(sizeof(char)*ARRAY_SIZE);
large_integer r = (char*)malloc(sizeof(char)*ARRAY_SIZE);
large_integer p = (char*)malloc(sizeof(char)*ARRAY_SIZE);
large_integer q = (char*)malloc(sizeof(char)*ARRAY_SIZE);
char *t1, *t2, *t3, *t4, *t5, *t6;
int n, m, num_of_u, num_of_v;
parray[count_of_array++] = x;
parray[count_of_array++] = y;
parray[count_of_array++] = w;
parray[count_of_array++] = z;
parray[count_of_array++] = r;
parray[count_of_array++] = p;
parray[count_of_array++] = q;
num_of_u = NumCountOfArray(u);
num_of_v = NumCountOfArray(v);
n = Maximum(num_of_u, num_of_v);
if(num_of_u == 0 || num_of_v ==0)
{
return ZeroArray();
}
else if(n <= threshold )
{
return ArrayMultipleByNormalMethod(u, v);
}
else
{
m = (int)floor((double)(n/2));
GetDivideAndRem(u, m, x, y);
GetDivideAndRem(v, m, w, z);
//-------------------------------------------------------------------
// p * 10^2m + (r-p-q) * 10^m + q
//-------------------------------------------------------------------
r = Prod2( AddArray(x, y), AddArray(w, z) );
p = Prod2(x, w);
q = Prod2(y, z);
t1 = PowArray(p, (2*m));
t2 = SubArray(r, p);
t3 = SubArray(t2, q);
t4 = PowArray(t3, m);
t5 = AddArray(t1, t4);
t6 = AddArray(t5, q);
return t6;
}
}
- 실행 결과 -
이론상 최악의 시간 복잡도
prod() -
W(n)`` IN `` theta (n ^{log4} ) APPROX theta (n ^{2} )
prod2() -
W(n)`` IN `` theta (n ^{log _{2} 3} ) APPROX theta (n ^{1.58} )
시간 측정 결과값
prod() 연산시간 0.002303초
prod2()연산시간 0.001943초
큰 정수의 곱셈에서 prod2()함수가 빠른 것을 알 수 있다.

키워드

큰정수,   곱셈,   알고리즘,   무한,   정수,   계산,   소스