오늘은 바로 일전에 포스팅을 했지만 그렇게 개발을 많이 하진 못했다. 다만 학교에서 큰수 계산에 대한 과제가 있었기 때문에 이에 대해 약간 정리해본다.
기본적으로 숫자들은 char 배열에 존재한다고 가정한다. 무한이니깐 char *Str 뭐 이런식으로 해야하겠다 포인터로.
1. 덧셈
덧셈은 간단해 보여도 간단해 보이지가 않다. 사실 그냥 정수 덧셈은 아래 알고리즘 대로 하면 쉽다.
- 두 숫자 중 길이가 긴 것을 선택한다.
- 길이가 긴 것만큼의 새로운 char* 를 만든다.(new char[(int)strlen(Str_A) 이런식)
- 길이가 작은 숫자를 기준으로 반복문을 돌면서 뒤에서부터 sum = (A[len_A-1]-‘0’) + (B[len_B-1] – ‘0’) 이런식으로 더해나간다. 여기서 -‘0’을 빼주는 이유는 ASCII값이기 때문에 정수를 구하기 위해.
- 구한 sum은 새롭게 만든 char*형 배열의 맨 뒤에서부터 넣어준다.
- 더했을 때 10 이상이 발생하면 int형 carry를 하나 둬서 1을 주고 temp = sum % 10 으로 둔다. 만약 10 미만이면 carry는 0으로 준다.
- 반복문이 끝나고 다음에는 sum에 temp와 carry를 더해준다.
- 이런식으로 반복하다 반복문이 끝나면 이제 큰 숫자를 기준으로 마지막으로 끝난 위치부터 0의 위치까지 돌면서 같은 위치에 길이가 긴 것의 값을 넣어준다. -> 이 과정에서 기존에 반복문에서 마지막에 carry를 값 그대로 유지하면서 또한 carry를 계속 확인해준다. 예를들어 99999999 + 1 의 경우 길이가 작은 것 기준의 반복문이 끝나더라도 carry가 계속 1로 발생할 수 있다.
문제는 만약 -123 + -456 의 경우인데 이 경우는 일단 부호를 제외하고 계산한 다음에 마지막에 부호를 붙혀주는 것이 좋겠다. 만약 부호가 다를 경우, 뻴셈이나 두 숫자를 비교해서 예를 들어 123 – (-456)의 경우는 결과적으로 123 + 456이 되어야 하므로 부호를 바꿔 준 다음에 더해주면 되겠다.
이러한 예외 상황이 있기 때문에 최초 Str_A 와 Str_B에 대한 양/음수에 대한 구분이 필수적으로 실행되어야 한다.
2. 뻴셈
뺄셈은 위에서도 언급했듯이 결과가 +이냐 -이냐에 따라 부호가 같은 숫자를 뺄 경우 양수끼리는 위의 덧셈 과정에서 carry를 -1로 주고 똑같이 돌려주면 된다. 단, 맨 처음 문자가 0이 될 수 있으므로(예 : 1000 – 1 = 0999) 마지막에 문자열에서 0을 제거해주는 방법을 시행해야 한다.
3. 곱셈
곱셈은 더 좋은 방법이 있겠지만 나 같은 경우 예를 들어 123 * 222 을 한다 치면 (123 + 123) + (123+123) * 10 + (123+123) * 100 으로 하였다. 이게 무슨말이냐면, 여기서 뒤에 *10, *100 의 경우는 123을 2만큼 더한 결과에 0을 붙히는 것이 된다. 어차피 우리 결과는 Char*형이기 때문에 new를 사용하여 가변적으로 길이를 조절한다면 246에 0을 붙히는 것은 10을 곱하는 게 아니라 ‘0’이란 문자를 추가하는 게 된다. 그렇게 계산된 결과를 전역변수에서 더해주기만 하면 된다.
좀 무식한 방법 같지만 우리가 위에서 덧셈을 구현해 놨기 때문에 이를 활용하는 것이나 마찬가지다. 만약 음수를 곱한다면 역시나 두 숫자가 모두 같은 부호라면 양수를, 다른 부호라면 음수를 제일 마지막에 주면 되겠다.
부끄럽지만 소스를 공개하겠다. 참고로 나는 과제에서 큰 정수용 타입을 정의한 클래스를 사용하라 하였기에 BIG_INT라는 타입을 정의하였다. 이를 인지하고.. 참고로 소스 실행이 원활이 될 지는 모르겠다. 중간에 몇몇 살짝 적지 않은게 있기도 하고.. 연산자 오버로딩(예 : operator+) 을 사용했기 때문에 이 부분에 대한 이해도 필요할 것이다. 이는 구글에 검색하면 잘 나오니 참조하면 되겠다. 이러한 부분은 독자의 배움의 입장에서 소스를 확인하라는 취지에서 숙제로 남겨두겠다.
[#M_소스보기|접기|
(big_int.h)
/*
programmed by Matthew, CHANG
www.izect.kr
*/
#include<iostream>
using namespace std;
class big_int{
private:
char* cDigits;
unsigned int iLength;
bool bSign;
public:
inf_int(void);
inf_int(int);
inf_int(const char*);
inf_int(const inf_int&);
~inf_int();
inf_int& operator=(const inf_int&);
friend bool operator==(const big_int& , const big_int&);
friend bool operator!=(const big_int& , const big_int&);
friend bool operator>(const big_int& , const big_int&);
friend bool operator<(const big_int& , const big_int&);
friend big_int operator+(const big_int& , const big_int&);
friend big_int operator-(const big_int& , const big_int&);
friend big_int operator*(const big_int& , const big_int&);
friend ostream& operator<<(ostream&, const big_int&);
};
(big_int.cpp)
#include “big_int.h”
big_int::big_int(){
}
big_int::big_int(int tNum){
char *temp_char;
int len = 0;
int tNum2 = tNum;
// 음수 처리
if(tNum2 < 0) { // Negative
tNum2 *= -1;
tNum *= -1;
bSign = false;
for(int i = 0 ; ; i++) {
len++;
tNum2 /= 10;
if(tNum2 <= 0) break;
}
temp_char = new char[len+1];
for(int i = 0 ; i < len ; i++) {
int temp = tNum%10;
temp_char[i] = temp + ‘0’;
tNum /= 10;
}
temp_char[len] = ‘\0’;
}else{ // Positive
bSign = true;
for(int i = 0 ; ; i++) {
len++;
tNum2 /= 10;
if(tNum2 <= 0) break;
}
temp_char = new char[len+1];
for(int i = 0 ; i < len ; i++) {
int temp = tNum%10;
temp_char[i] = temp + ‘0’;
tNum /= 10;
}
temp_char[len] = ‘\0’;
}
//
iLength = (int)strlen(temp_char);
cDigits = new char[len+1];
for(int i = 0 ; i < iLength ; i++) {
cDigits[i] = temp_char[iLength-i-1];
}
cDigits[len] = ‘\0’;
}
big_int::big_int(const char* tChar){
bool zflag = false;
int cnt = 0;
if((int)strlen(tChar) == 1 && tChar[0] == ‘0’) {
cDigits = new char[1];
cDigits[0] = ‘0’;
cDigits[1] = ‘\0’;
}else if(tChar[0] == ‘-‘){
bSign = false;
cnt = 1;
for(int i = 1 ; ; i++) {
if(tChar[i] != ‘0’) break;
cnt++;
}
cDigits = new char[(int)strlen(tChar) – cnt];
for(int i = 0 ; i < (int)strlen(tChar) – cnt ; i++) {
cDigits[i] = tChar[i+cnt];
}
cDigits[(int)strlen(tChar) – cnt] = ‘\0’;
iLength = (int)strlen(cDigits);
}else{
bSign = true;
for(int i = 0 ; ; i++) {
if(tChar[i] != ‘0’) break;
cnt++;
}
cDigits = new char[(int)strlen(tChar) – cnt];
for(int i = 0 ; i < (int)strlen(tChar) – cnt ; i++) {
cDigits[i] = tChar[i+cnt];
}
cDigits[(int)strlen(tChar) – cnt] = ‘\0’;
iLength = (int)strlen(cDigits);
}
}
big_int::big_int(const big_int& temp){
cDigits = new char[temp.iLength];
bSign = temp.bSign;
strcpy(cDigits,temp.cDigits);
iLength = temp.iLength;
}
big_int::~big_int(){
strcpy(cDigits,”\0″);
bSign = true;
iLength = 0;
}
big_int& big_int::operator=(const big_int& temp){
bSign = temp.bSign;
strcpy(cDigits,temp.cDigits);
iLength = temp.iLength;
return *this;
}
bool operator==(const big_int& orig, const big_int& ext) {
bool flag = true;
if(orig.bSign != ext.bSign){
flag = false;
}else if(strcmp(orig.cDigits,ext.cDigits)){
flag = false;
}else if(orig.iLength != ext.iLength){
flag = false;
}
return flag;
}
bool operator!=(const big_int& orig, const big_int& ext) {
bool flag = true;
if(orig.bSign == ext.bSign){
flag = false;
}else if(!strcmp(orig.cDigits,ext.cDigits)){
flag = false;
}else if(orig.iLength == ext.iLength){
flag = false;
}
return flag;
}
bool operator>(const big_int& orig, const big_int& ext) {
bool flag = true;
if(orig.bSign == false && ext.bSign == true){ // -orig , +ext
flag = false;
}else if(orig.bSign == true && ext.bSign == false){ // +orig , -ext
flag = true;
}else if(orig.bSign == true && ext.bSign == true){
if(orig.iLength > ext.iLength) { // same sign, length is orig > ext
flag = true;
}else if(orig.iLength < ext.iLength) { // same sign, length is orig < ext
flag = false;
}else{
if(!strcmp(orig.cDigits,ext.cDigits)){
flag = false;
}else{
for(int i = orig.iLength-1 ; i>=0 ; i–){ // same sign, same length
int A = (int)(orig.cDigits[i] – ‘0’);
int B = (int)(ext.cDigits[i] – ‘0’);
if(A < B) {
flag = false;
break;
}
}
}
}
}else if(orig.bSign == false && ext.bSign == false){
if(orig.iLength > ext.iLength) { // same sign, length is orig > ext
flag = false;
}else if(orig.iLength < ext.iLength) { // same sign, length is orig < ext
flag = true;
}else{
if(!strcmp(orig.cDigits,ext.cDigits)){
flag = false;
}else{
for(int i = orig.iLength-1 ; i>=0 ; i–){ // same sign, same length
int A = (int)(orig.cDigits[i] – ‘0’);
int B = (int)(ext.cDigits[i] – ‘0’);
if(A > B) {
flag = false;
break;
}
}
}
}
}
return flag;
}
bool operator<(const big_int& orig, const big_int& ext) {
bool flag = true;
if(orig.bSign == false && ext.bSign == true){ // -orig , +ext
flag = true;
}else if(orig.bSign == true && ext.bSign == false){ // +orig , -ext
flag = false;
}else if(orig.bSign == true && ext.bSign == true){
if(orig.iLength > ext.iLength) { // same sign, length is orig > ext
flag = false;
}else if(orig.iLength < ext.iLength) { // same sign, length is orig < ext
flag = true;
}else{
if(!strcmp(orig.cDigits,ext.cDigits)){
flag = false;
}else{
for(int i = orig.iLength-1 ; i>=0 ; i–){ // same sign, same length
int A = (int)(orig.cDigits[i] – ‘0’);
int B = (int)(ext.cDigits[i] – ‘0’);
if(A > B) {
flag = false;
break;
}
}
}
}
}else if(orig.bSign == false && ext.bSign == false){
if(orig.iLength > ext.iLength) { // same sign, length is orig > ext
flag = true;
}else if(orig.iLength < ext.iLength) { // same sign, length is orig < ext
flag = false;
}else{
if(!strcmp(orig.cDigits,ext.cDigits)){
flag = false;
}else{
for(int i = orig.iLength-1 ; i>=0 ; i–){ // same sign, same length
int A = (int)(orig.cDigits[i] – ‘0’);
int B = (int)(ext.cDigits[i] – ‘0’);
if(A < B) {
flag = false;
break;
}
}
}
}
}
return flag;
}
// 덧셈 : orig + ext
big_int operator+(const big_int& orig, const big_int& ext) {
int max_i,min_j,k,carry,temp,len,findex;
char *temp_str,*result_str,*high,*low;
if(orig.bSign == ext.bSign){ // 부호가 같은 경우
// 길이가 긴 것을 찾아서 공통 변수 할당
if(orig.iLength < ext.iLength) {
high = new char[(int)strlen(ext.cDigits)];
low = new char[(int)strlen(orig.cDigits)];
strcpy(high,ext.cDigits);
strcpy(low,orig.cDigits);
max_i = ext.iLength – 1;
min_j = orig.iLength – 1;
}else{
high = new char[(int)strlen(orig.cDigits)];
low = new char[(int)strlen(ext.cDigits)];
strcpy(high,orig.cDigits);
strcpy(low,ext.cDigits);
max_i = orig.iLength – 1;
min_j = ext.iLength – 1;
}
// 임시변수 초기화
temp_str = new char[(int)strlen(high)];
carry = 0;
// 자릿수가 적은 숫자의 길이만큼의 덧셈 수행
while(true) {
temp = ((int)(high[max_i] – ‘0’) + (int)(low[min_j] – ‘0’));
temp += carry;
if(temp >= 10){
carry = 1;
temp %= 10;
}else{
carry = 0;
}
temp_str[max_i] = temp + ‘0’;
max_i–;
min_j–;
if(min_j<0){
break;
}
}
// 자릿수가 긴 숫자의 길이만큼을 임시변수에 넣어줌
for( ; max_i >= 0 ; max_i– ){
temp = (int)(high[max_i] – ‘0’) + carry;
if(temp >= 10){
carry = 1;
temp %= 10;
}else{
carry = 0;
}
temp_str[max_i] = temp + ‘0’;
}
temp_str[(int)strlen(high)] = ‘\0’;
// 만약 끝까지 CARRY가 발생한 경우를 대비해서 다시 임시배열에 넣어줌.
if(carry != 0) { // carry가 있는경우
if(orig.bSign && ext.bSign){ // 둘다 양수라면
len = (int)strlen(temp_str) + 1;
findex = 1;
result_str = new char[len];
result_str[0] = carry + ‘0’;
for(k = findex ; k < len ; k++) {
result_str[k] = temp_str[k-1];
}
}else if(!orig.bSign && !ext.bSign){ // 둘다 음수라면
len = (int)strlen(temp_str) + 2;
findex = 2;
result_str = new char[len];
result_str[0] = ‘-‘; // 부호 할당
result_str[1] = carry + ‘0’;
for(k = findex ; k < len ; k++) {
result_str[k] = temp_str[k-1];
}
}
}else{
if(orig.bSign && ext.bSign){ // 둘다 양수라면
len = (int)strlen(temp_str);
findex = 0;
result_str = new char[len];
for(k = findex ; k < len ; k++) {
result_str[k] = temp_str[k];
}
}else if(!orig.bSign && !ext.bSign){ // 둘다 음수라면
len = (int)strlen(temp_str) + 2;
findex = 1;
result_str = new char[len];
result_str[0] = ‘-‘; // 부호 할당
for(k = findex ; k < len ; k++) {
result_str[k] = temp_str[k-1];
}
}
}
result_str[len] = ‘\0’;
big_int result(result_str);
return result;
}else{ // 부호가 다른 경우
bool rsign = true;
// 결과 부호구하기
// 다 똑같은데 부호만 다른 경우, 0이 나오니 0 리턴.
if(!strcmp(ext.cDigits,orig.cDigits)){
big_int result(0);
return result;
}
if(!ext.bSign) { // ext가 음수
if(orig.iLength > ext.iLength) { // orig가 크다면 결과는 당연히 양수다.
rsign = true;
}else if(orig.iLength < ext.iLength){ // ext가 크면 결과는 음수다.
rsign = false;
}else{ // 길이가 같으면 숫자만 보고 큰숫자 결정해야함.
for(int i = 0 ; i < orig.iLength ; i++) {
if((orig.cDigits[i] – ‘0’) > (ext.cDigits[i] – ‘0’)) {
rsign = true;
break;
}else if((orig.cDigits[i] – ‘0’) < (ext.cDigits[i] – ‘0’)) {
rsign = false;
break;
}
}
}
if(rsign) { // 결과가 양수면 orig가 큰숫자.
high = new char[(int)strlen(orig.cDigits)];
low = new char[(int)strlen(ext.cDigits)];
strcpy(high,orig.cDigits);
strcpy(low,ext.cDigits);
max_i = orig.iLength – 1;
min_j = ext.iLength – 1;
}else{
high = new char[(int)strlen(ext.cDigits)];
low = new char[(int)strlen(orig.cDigits)];
strcpy(high,ext.cDigits);
strcpy(low,orig.cDigits);
max_i = ext.iLength – 1;
min_j = orig.iLength – 1;
}
}else{ // orig가 음수
if(orig.iLength > ext.iLength) { // orig가 크다면 결과는 음수다.
rsign = false;
}else if(orig.iLength < ext.iLength){ // ext가 크면 결과는 양수다.
rsign = true;
}else{ // 길이가 같으면 숫자만 보고 큰숫자 결정해야함.
for(int i = 0 ; i < orig.iLength ; i++) {
if((orig.cDigits[i] – ‘0’) > (ext.cDigits[i] – ‘0’)) {
rsign = false;
break;
}else if((orig.cDigits[i] – ‘0’) < (ext.cDigits[i] – ‘0’)) {
rsign = true;
break;
}
}
}
if(rsign) { // 결과가 양수면 ext가 큰숫자.
high = new char[(int)strlen(ext.cDigits)];
low = new char[(int)strlen(orig.cDigits)];
strcpy(high,ext.cDigits);
strcpy(low,orig.cDigits);
max_i = ext.iLength – 1;
min_j = orig.iLength – 1;
}else{
high = new char[(int)strlen(orig.cDigits)];
low = new char[(int)strlen(ext.cDigits)];
strcpy(high,orig.cDigits);
strcpy(low,ext.cDigits);
max_i = orig.iLength – 1;
min_j = ext.iLength – 1;
}
}
// 임시변수 초기화
temp_str = new char[(int)strlen(high)];
carry = 0;
// 자릿수가 적은 숫자의 길이만큼의 뺄셈 수행
while(true) {
temp = ((int)(high[max_i] – ‘0’) – (int)(low[min_j] – ‘0’));
temp -= carry;
if(temp < 0){
carry = 1;
temp += 10;
}else{
carry = 0;
}
temp_str[max_i] = temp + ‘0’;
max_i–;
min_j–;
if(min_j<0){
break;
}
}
// 자릿수가 긴 숫자의 길이만큼을 임시변수에 넣어줌
for( ; max_i >= 0 ; max_i– ){
temp = (int)(high[max_i] – ‘0’) – carry;
if(temp < 0){
carry = 1;
temp += 10;
}else{
carry = 0;
}
temp_str[max_i] = temp + ‘0’;
}
temp_str[(int)strlen(high)] = ‘\0’;
// 만약 끝까지 CARRY가 발생한 경우를 대비해서 다시 임시배열에 넣어줌.
if(temp_str[0] == ‘0’) {
if(!rsign){
len = (int)strlen(temp_str);
result_str = new char[len];
result_str[0] = ‘-‘;
for(k = 1 ; k < len ; k++) {
result_str[k] = temp_str[k];
}
}else{
len = (int)strlen(temp_str);
result_str = new char[len];
for(k = 0 ; k < len-1 ; k++) {
result_str[k] = temp_str[k+1];
}
}
}else{
if(!rsign){
len = (int)strlen(temp_str) + 1;
result_str = new char[(int)strlen(temp_str) + 1];
result_str[0] = ‘-‘;
for(k = 1 ; k < len ; k++) {
result_str[k] = temp_str[k-1];
}
}else{
len = (int)strlen(temp_str);
result_str = new char[(int)strlen(temp_str)];
for(k = 0 ; k < len ; k++) {
result_str[k] = temp_str[k];
}
}
}
result_str[len] = ‘\0’;
big_int result(result_str);
return result;
}
}
// 뻴셈. orig – ext
big_int operator-(const big_int& orig, const big_int& ext) {
int max_i,min_j,k,carry,temp,len,findex;
char *temp_str,*result_str,*high,*low;
bool rsign;
if(orig.bSign != ext.bSign){ // 부호가 다른 경우, 길이가 긴 쪽의 부호를 바꿔서 덧셈 수행.
if(!strcmp(ext.cDigits,orig.cDigits)){
big_int result(0);
return result;
}
if(!ext.bSign) { // ext가 음수면 다 양수로 바꿔서 계산.
big_int result(ext.cDigits);
return orig+result;
}else{ // orig가 음수면 결과는 무조건 음수다.
temp_str = new char[ext.iLength + 1];
temp_str[0] = ‘-‘;
for(int i = 1 ; i < ext.iLength + 1 ; i++) temp_str[i] = ext.cDigits[i-1];
temp_str[ext.iLength + 1] = ‘\0’;
big_int result(temp_str);
return orig+result;
}
}else{ // 부호가 같은 경우, ext를 음수로 바꾸고 덧셈 수행.
if(!ext.bSign) { // 둘다 음수일 경우, 뒤의 숫자를 양수로 바꿔주고 덧셈 수행.
big_int result(ext.cDigits);
return orig + result;
}else{ // 둘다 양수일 경우, 뒤에 숫자를 음수로 바꿔주고 덧셈 수행.
temp_str = new char[ext.iLength + 1];
temp_str[0] = ‘-‘;
for(int i = 1 ; i <= ext.iLength ; i++) temp_str[i] = ext.cDigits[i-1];
temp_str[ext.iLength – 1] = ‘\0’;
big_int result(temp_str);
return orig + ext;
}
}
}
big_int operator*(const big_int& orig, const big_int& ext) {
big_int temp(0),torig(orig),text(ext); // 33 * 44 의 경우, 33 * 4 + 33 * 40 즉 한자리씩 자릿수만큼 반복해서 더한다음에 뒤에 0을 여러개 붙히고 이를 다시 더해준다.
int i = ext.iLength – 1;
if(!orig.bSign){
big_int tt(orig.cDigits);
torig = tt;
}
if(!ext.bSign) {
big_int tt(ext.cDigits);
text = tt;
}
while(i>=0) {
big_int temp2(0);
char *temp_char,*result_char;
for(int j = 0 ; j < (int)(text.cDigits[i] – ‘0’) ; j++) {
temp2 = temp2 + torig;
}
if(text.cDigits[i] == ‘0’){
big_int rslt(“0”);
temp = temp + rslt;
}else{
// 최종 문자 만들기
result_char = new char[temp2.iLength + (text.iLength – i – 1)];
for(int j = 0 ; j < temp2.iLength ; j++) {
result_char[j] = temp2.cDigits[j];
}
for(int j = temp2.iLength ; j < temp2.iLength + (text.iLength – i – 1) ; j++) {
result_char[j] = ‘0’;
}
result_char[temp2.iLength + (text.iLength – i – 1)] = ‘\0’;
big_int rslt(result_char);
temp = temp + rslt;
}
i–;
}
if((!orig.bSign && ext.bSign) || (orig.bSign && !ext.bSign)) {
char *rslt = new char[temp.iLength + 1];
rslt[0] = ‘-‘;
for(int j = 1 ; j < temp.iLength + 1 ; j++) {
rslt[j] = temp.cDigits[j-1];
}
rslt[temp.iLength + 1] = ‘\0’;
big_int result(rslt);
return rslt;
}else{
return temp;
}
}
ostream& operator<<(ostream& c, const big_int& orig) {
if(orig.bSign == false) c << ‘-‘;
c << orig.cDigits;
return c;
}
_M#]
