일반적인 큰정수 곱셈을 코딩했는데 이상한답이 나오네요.....지적질과 칼질 부탁드립니다.....
///////////////////////////////
///1.일반적인 큰 정수의 계산법///
///////////////////////////////
/*큰 정수 계산법 : 1. 큰 수를 담기위해 배열을 선언한다 그리고 인덱스가 큰배열로 제일큰 자릿수가 오도록 저장한다. ex(123456 => s[6][5][4][3][2][1]=123456)
2. 부호를 담기위한 int형을 선언한다.
3. (1,2)를 묶어서 Large_Integer형을 만든다. */
#include <stdio.h>
#include <stdlib.h>
#define DIGIT 100 // 최대한도 자릿수를 100자리까지 잡는다.
typedef struct large_integer// Large_Integer형
{
char n[DIGIT]; //저장시 숫자는 순서가 거꾸로 저장된다.
int p; //양수 음수 판단.(true=음수 .false = 양수)
} LARGE_INTEGER;
char i_a(int a); //정수를 알파벳으로 변환
int a_i(char a); //알파벳을 정수로 변환
int Digit_Count(LARGE_INTEGER x); //입력한 수가 몇자리인지를 구하는 함수.
void Initial(LARGE_INTEGER &x); // 배열을 초기화
void Input_num(LARGE_INTEGER &x, LARGE_INTEGER &y); // 숫자입력.
void Print_num(LARGE_INTEGER x); // 이용자가 보기 편하게 거꾸로 저장된 LARGE_INTERGER를 올바르게 출력.
void Reverse(LARGE_INTEGER &u); // 배열의 순서를 뒤집어준다.
void JudgePlusMinus(LARGE_INTEGER &u); //음수 양수를 판단해서 bool에 저장해준다.
LARGE_INTEGER CheckDigit(LARGE_INTEGER u); //0을 없애준다.
LARGE_INTEGER Mul_Usual (LARGE_INTEGER u, LARGE_INTEGER v); // 일반적 방법으로 두 수 곱하기
void main()
{
LARGE_INTEGER u, v, x;
Initial(u); Initial(v); Initial(x);
// u.v,x를 초기화해줍니다.
printf("첫번쨰 큰수 곱셈법\n");
Input_num(u, v);
//입력 및 배열에 거꾸로 저장
JudgePlusMinus(u); JudgePlusMinus(v);
//음수 양수를 판단해서 저장
printf("\n일반적인 곱셈법 : ");
Print_num(Mul_Usual(u,v));
}
int Digit_Count(LARGE_INTEGER x) // 자리수 구하기
{
int counter=0; //자릿수를 세기위한 counter 변수
for(int i=0 ; i<=DIGIT-1 ; i++) // 배열에서 NULL 이 나올때까지 루프돌려서 자리수를 알아낸다.
{
if(x.n[i] != NULL)
counter++;
else
break;
}
return counter;
}
void Initial(LARGE_INTEGER &x) // 배열을 초기화.
{
for(int i=0 ; i<=DIGIT-1 ; i++)
{
x.n[i] = 0; // 모든 배열에 0을 넣어준다.
}
x.p = 0; // 부호의 기본값을 양수로 설정.
}
void Input_num(LARGE_INTEGER &x, LARGE_INTEGER &y) // 입력받고 음수양수 처리 및 배열 거꾸로 돌려 저장
{
scanf("%s %s", x.n, y.n);
Reverse(x);
Reverse(y);
}
void Print_num(LARGE_INTEGER x) // 거꾸로 돌리고 출력
{
Reverse(x);
if(x.p == 1)
printf("- %s",x.n);
else
printf(" %s",x.n);
}
void Reverse(LARGE_INTEGER &u) // 배열에 저장된 숫자를 거꾸로 되돌리기 and 음수 양수 저장
{
int digit = Digit_Count(u);
char temp[DIGIT];
for(int i = 0 ; i<digit ; i++) //거꾸로 temp배열에 저장
temp[i] = u.n[digit-i-1];
for(int i = 0 ; i<digit ; i++)
u.n[i] = temp[i];
}
void JudgePlusMinus(LARGE_INTEGER &u) //양수 음수를 판단하여 0.1을 저장
{
int digit = Digit_Count(u);
if( u.n[(digit)-1] == '-')
{
u.p = 1; //음수
u.n[(digit)-1]=NULL;
}
else
u.p = 0; //양수
}
LARGE_INTEGER Mul_Usual(LARGE_INTEGER u, LARGE_INTEGER v) // 일반적 방법으로 두 수 곱하기
{
LARGE_INTEGER result;
Initial(result);
int carry1=0;
int carry2=0;
int digit1 = Digit_Count(u);
int digit2 = Digit_Count(v);
int digit3 = digit1+digit2;
result.n[digit3+1]=NULL;
Reverse(u);
Reverse(v);
for(int i=digit1 -1;i>=0;i--)
{
int k=digit1+i;
for(int j=digit2-1; j>=0; j--,k--)
{
if(a_i(u.n[i]) * a_i(v.n[j]) >=10) //u와 v의 한자리 배열의 곱이 carry를 발생시킬떄
{
carry1 = a_i(u.n[i]) * a_i(v.n[j]) / 10; //carry를 구해서 carry1에 저장
if( ( a_i(u.n[i]) * a_i(v.n[j]) % 10 + carry2 + a_i(result.n[k]) ) >=10 ) //전 단계 carry + 배열곱셈의 나머지 + 결과배열 기존값의 합이 carry를 발생시킬떄
{
carry1 = carry1 + ( (a_i(u.n[i]) * a_i(v.n[j]) % 10 + carry2 + a_i(result.n[k]) ) / 10 ); // 기존 carry에 덧셈으로 인해 증가하는 carry값을 더함.
result.n[k] = i_a( ( a_i(u.n[i]) * a_i(v.n[j]) % 10 + carry2 + a_i(result.n[k])) % 10 ); //해당 결과 배열에 carry하는 값을 뺸 나머지를 저장.
carry2 = carry1; //다음 연산시 carry를 더하기위한 대입.
}
else
{
result.n[k] = i_a(a_i(u.n[i]) * a_i(v.n[j]) % 10 + carry2 + a_i(result.n[k])); //더하기로 carry가 없기떄문에 그냥 나머지를 저장.
carry2=carry1; //다음 연산시 carry를 더하기위한 대입.
}
}
else
{
carry1 = 0; //곱으로 인한 carry가 발생하지 않으므로 carry값은 0이다.
if( ( a_i(u.n[i]) * a_i(v.n[j]) + carry2 + a_i(result.n[k]) ) >=10 ) //전 단계 carry + 배열곱셈의 나머지 + 결과배열 기존값의 합이 carry를 발생시킬떄
{
carry1 = carry1 + ( ( a_i(u.n[i]) * a_i(v.n[j]) + carry2 + a_i(result.n[k]) ) /10 ); //기존 carry에 덧셈으로 인해 증가하는 carry값을 더함.
result.n[k] = i_a( ( a_i(u.n[i]) * a_i(v.n[j]) + carry2 + a_i(result.n[k])) % 10 ); //해당 결과 배열에 carry하는 값을 뺸 나머지를 저장.
carry2 = carry1; //다음 연산시 carry를 더하기위한 대입.
}
else
{
result.n[k] = i_a( a_i(u.n[i]) * a_i(v.n[j]) + carry2 + a_i(result.n[k]) ); //해당 결과 배열에 carry하는 값을 뺸 나머지를 저장.
carry2 = carry1; //다음 연산시 carry를 더하기위한 대입
}
}
}
result.n[k-1] = i_a( a_i(result.n[k-1]) + carry2 ); //for문안에서 못 계산한 carry를 계산.
carry2 = 0; //자릿수 계산이 완료햇기 떄문에 0으로 초기화
}
Reverse(result);// 뒤집어서 저장
result=CheckDigit(result); //자리수 조정
return result; //결과 리턴
}
LARGE_INTEGER CheckDigit(LARGE_INTEGER u) // 배열 제일 오른쪽 큰 자리수가 0일 때 자리수 조정하기(EX : 123000 -> 123 )
{
LARGE_INTEGER result;
int digit = Digit_Count(u);
result = u;
for( int i = digit-1 ; i>0 ; i--)
{
if(result.n[i] == '0')
result.n[i] = NULL;
else break;
if(result.n[i-1] != '0')
break;
if(i == 1 || result.n[0] == '0')
result.n[1] = NULL;
}
return result;
}
int a_i(char a)
{
int re=0;
re=a-48;
return re;
}
char i_a(int a)
{
int re=0;
re=a+48;
return re;
}
