컴퓨터 알고리즘 - 큰 정수곱셈 소스코드 및 분석
본 자료는 5페이지 의 미리보기를 제공합니다. 이미지를 클릭하여 주세요.
닫기
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
해당 자료는 5페이지 까지만 미리보기를 제공합니다.
5페이지 이후부터 다운로드 후 확인할 수 있습니다.

소개글

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

본문내용

------
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()함수가 빠른 것을 알 수 있다.

키워드

큰정수,   곱셈,   알고리즘,   무한,   정수,   계산,   소스
  • 가격1,000
  • 페이지수16페이지
  • 등록일2004.05.26
  • 저작시기2004.05
  • 파일형식한글(hwp)
  • 자료번호#252992
본 자료는 최근 2주간 다운받은 회원이 없습니다.
청소해
다운로드 장바구니