[C++] 문자열로 곱셈과 덧셈 구현하기

C++에서 long long int에도 담기지 않는 수가 있다. 9,223,372,036,854,775,807이 가장 큰 수라고 하는데, 그것보다 더 큰 수를 계산해야 하는 경우는 어떻게 해야 할까? 2^1239 을 계산하고 싶을 땐 어떻게 해야 할까? 그 방법 중 하나가 문자열로 곱셈과 덧셈을 구현하는 것이다.

 

원리는 아주 간단하다. 손으로 두자릿수의 곱셈과 덧셈을 해보자. 한 자리씩 더하거나 곱할 때 carry가 발생하면 다음 자리수로 넘겨서 더해준다. 따라서 손으로 하는 필산을 프로그램으로 구현한 것이 되겠다.

 

1. sum

두 수를 문자열로 받고, 뒷 자리수부터 시작해서 carry 가 발생할 경우 자리수 올림까지 고려한다. 두 수의 덧셈을 문자열로 반환한다.

이때 a[Sizea]에서 0을 빼는 건 뭐냐! 라고 생각할 수 있는데, 그렇게 하면 숫자를 ASCII코드의 값이 된다. 참고로 0, 1, 2, 3..은 연달아 있으니까 0의 값을 빼면 해당하는 숫자가 num1 혹은 num2에 할당되는 구조다.

string sum(string& a, string& b) {
    int Sizea = a.length();
    int Sizeb = b.length();
    int cr =0; 
    string ssum = "";
   
    while (Sizea > 0 || Sizeb > 0) {
        int num1 = 0;
        if(Sizea>0){
            Sizea--;
            num1 = a[Sizea]-'0';
        }
        int num2 = 0;
        if (Sizeb > 0) {
            Sizeb--;
            num2 = b[Sizeb]-'0';
        }
        int rem = num1 + num2 + cr;
        cr = rem / 10;
        rem = rem%10;
        char cur = rem +'0';
        ssum += cur;
    }
    if (cr > 0) {
        ssum += cr +'0';
    }
    string tot = "";
    int i =0;
    for (i = (int)ssum.length()-1; i >= 0; --i) {
        tot += ssum[i];
    }
    return tot;
}

 

2. times

임의의 양수와 한 자리 수의 곱을 나타냈다. 두 수를 모두 문자열로 받는다. 두 수의 곱셈을 문자열로 반환한다.

이때 임의의 수 * 한 자리 라는 점을 명심하자.

string times(string& a, string& b){
    int Size1=a.length();
    string time = "";
    int carry = 0;

    while(Size1>0){
        int num = 0;
        if(Size1>0){
            Size1--;
            num=a[Size1]-'0'; //아스키 코드를 활용해서 num에 숫자 할당
        }
        int s = num*(b[0]-'0')+carry;
        int remain = s%10;
        carry =s/10;
        
        char rem = remain + '0';
        time += rem;
    }

    if (carry > 0) {
        time += carry +'0';
    }
    int i =0;
    string tot = "";
     for (i = (int)time.length()-1; i >= 0; --i) {
        tot += time[i];
    }

    return tot;
}

 

3. times2

임의의 양수와 임의의 정수의 곱을 나타낸다. 두 수를 모두 문자열로 받는다. 두 번쨰로 받은 수를 각 자리수별로 쪼갠 다음, times를 통해 첫 번째 수를 곱한다. 곱한 수를 sum을 이용해 더한다. 모든 자리수에 대해 곱을 구해서 더한 다음, 그 값을 문자열로 반환한다.

times가 임의의 양수 * 한자리니까 이번에는 임의의 양수 * 임의의 양수인 경우다. 나중에 곱해지는 수를 자리수마다 하나씩 분해해서 times()를 통해 처리한다. 그리고 str1 += '0';을 보면 알 수 있듯이, 연산값에 자리수만큼 0을 하나씩 더 붙여준 다음에 기존의 값과 sum()을 통해 합쳐서 다시 str에 저장했다.

string times2(string& a, string&b){
    int k = b.length();
    int i=0;
    string str="0";
    while(k>0){
        if(k>0){
            k--;
            string box = "";
            box += b[k];
            string str1 = times(a,box);
            int j;
            for(j=i;j>0;j--){
                str1 += '0';
            }
            i++;
            str=sum(str,str1);
        }

    }
    return str;
}

 

4.power

제곱을 계산한다. n와 k를 받는다. while 문을 이용해서 n을 k번 곱한다. times2를 이용해서 n * n의 값을 구하고, 그 값을 저장한다. 또 그 값을 다시 times2에 넣어서 n을 곱한다. 

string power(string& a, string& b){
    std::stringstream ss(b);
	int n;
	ss >> n;
    if(n==0){
        return "1";
    }
    if(n==1){
        return a;
    }
    string str = times2(a,a);
    while(n-2>0){
        n--;
        str=times2(str,a);
    }
    return str;
}

 

2^260와 같은 큰 수! 이 방법으로 계산하면 오버플로도 안 나고 빠르게 계산할 수 있다.

개인적으로 필산 구현하기는 기본적으로 꼭 한번은 구현해봐야 하는 로직인 것 같다.