SIRINI`s Blog

life, saying, developing, . . . and so on #10th anniversary

[뻘쭘한 알고리즘] 긴 자리수 덧셈 뺄셈 해보기

이번에는 아주 기본적인 것을 한 번 고찰해 보겠습니다.
이름하야, 긴 자리수 (혹은 무한 자리수!) 덧셈 뺄셈!! ...입니다. ^^;
굳이 설명이 필요할 것 같지는 않지만, 그래도 한 번 같이 생각해보자는 취지로
배경지식을 이야기 해 보도록 하겠습니다.

C 언어에서 기본적으로 제공하는 데이터 타입 중에
95782023975478592927348 이라는 숫자를 한 번에 담을 수 있는
타입이 무엇일까요? 네, 짱돌 날라오는 군요. ==3=3 (튀엇!!)

없죠.
어이 없어 하시는 것도 충분히 이해가 됩니다.
사실 저는 그 동안 이른 바, 강타입(strong type) 언어를 자주 쓰지 않아서
이런 부분에 특히 무신경 했습니다. 놀랍게도 Python 과 같은 언어에서는
아예 언어 특성상 이런 무한자리수 연산이 가능하도록 설계가 되어 있으니
더더욱 무신경했는지도 모릅니다. (반성중... ㅠ.ㅠ)

어쨌든, 현실세계는 냉정합니다.
95782... 로 시작하는 저런 긴 숫자는 최소한 C언어에서는 감당할 수가 없습니다.
반드시 배열이나 기타 다른 데이터 구조에 담아서 별도의 가공을 거쳐야 하지요.
슬픈 현실 앞에 비통한 마음 금할 길 없지만, 뭐 그래도 어쩌겠습니까.
언어에서 지원하지 않는다면 우회하는 길이라도 만들어 봐야지요. ^^;;

그래서 준비된 것이 이번에 소개해 드릴 긴 자리수 연산 알고리즘입니다.
원리는 단순합니다. 긴 자리수를 4자리 정수를 담을 수 있는 short 배열에다가
담습니다. 그리고 그 4자리씩 덧셈과 뺄셈을 해서 각각 자리올림수와 자리내림수를
처리해 줍니다. 그러니까 다시 말해 긴 자리의 숫자를 한 번에 처리하지 않고
4자리씩 끊어서 결국 4자리 short int 형 정수의 덧셈과 뺄셈을 하는 것입니다.

우선 아래 성공했을 시 나타날 화면을 보시겠습니다. (찬조출현: GNOME 콘솔)

upload image
(출력부분을 보시면 일부로 4자리씩 끊어서 나타난 것을 알 수 있습니다.)

이 전략을 좀 더 고급(?)스럽게 이야기하면 '분할 정복 전략' 이 되겠습니다.
즉, 한 번에 해결할 수 없는 단위의 큰 문제는 한 번에 해결할 수 있는 작은 몇 개의 문제로
나눠서 개별적으로 각개 격파 하는 것입니다. 위에서도 긴 자리수의 숫자를
short int 형으로 담아서 결국에는 4자리수 덧셈 / 뺄셈을 하도록 했습니다.

물론 여기서 만족할 수는 없겠지요.
아래 제가 작성한 코드의 문제점은 외부에서 입력을 받을 때 어떻게 할 것인가 하는 대비가
없다는 점입니다. 또한 수치를 반드시 short int 형 배열에 쪼개서 넣는 게 좋은지,
아니면 다른 타입으로 변환해서 넣는게 더 좋은지에 대해서도 고려를 해보아야 합니다.
더 깊게 생각해 본다면 CPU I/O 카운팅을 통해서 그야말로 마니악한 집요성으로
코드 최적화를 해 볼 수도 있겠습니다.

#include <stdio.h>

/* 이 소스코드는 기존 C 언어에서 지원하지 않는
무한자리수 산수 연산을 예시한다. 기본 데이터타입의 범위를 초과한
데이터의 덧셈과 뺄셈을 처리한다. */

#define LIMIT 32 /* 일단 여기서는 편의상 32자리 수로 제한한다. */
#define NUM ( ((LIMIT-1) / 4) + 1 ) /* 배열 크기다. short 타입의 배열을 쓴다. */

void iAdd(short*, short*, short*); /* 덧셈 */
void iSub(short*, short*, short*); /* 뺄셈 */
void iResult(short*); /* 결과 출력용 */

int main(int args)
{
    // 임의로 큰 수를 4자리로 short 배열에 담아두었다.
    // 실제 활용시에는 이 부분도 자동으로 되겠금 처리하는 게 좋다.
    static short a[NUM+2] = {1522,7849,2969,5432,1562,5092,8504,9562},
            b[NUM+2] = { 592,1949,6040,2947,6029,1156,5892,6782},
            c[NUM+2];
    
    printf("연산대상 A: 1522,7849,2969,5432,1562,5092,8504,9562₩n");
    printf("연산대상 B:  592,1949,6040,2947,6029,1156,5892,6782₩n");
    printf("---------------------------------------------------₩n");
    
    iAdd(a, b, c);
    printf("덧셈결과 +: ");
    iResult(c);
    
    iSub(a, b, c);
    printf("뺄셈결과 -: ");
    iResult(c);
    
    return 0;
}

// 긴 자리 덧셈하기
void iAdd(short a[], short b[], short c[])
{
    short i, cy=0;
    
    // 배열의 뒷자리부터 (그러니까 작은 단위수부터) 한 인덱스씩 계산한다.
    // 한 블럭의 덧셈결과가 10000 을 넘게 되면 자리올림수 처리를 해준다. (cy)
    for (i=NUM-1; i>=0; i--) {
        c[i] = a[i] + b[i] + cy;
        
        // 4자리수끼리 덧셈을 했는데도 10000 을 못넘겼으면 자리올림수는 없다!
        if(c[i] < 10000)
            cy = 0;
        else {
            c[i] = c[i] - 10000;
            cy = 1; // 덧셈해서 10000 을 넘겼다면 자리올림수를 만든다.
            // 위에서 만들어진 자리올림수는 그대로 다음 루프문에서 반영된다.
        }
    }
}

// 긴 자리수 뺄셈하기
void iSub(short a[], short b[], short c[])
{
    short i, br=0;
    
    // 역시 배열의 뒷자리 블럭부터 4자리씩 끊어서 계산한다.
    for (i=NUM-1; i>=0; i--) {
        c[i] = a[i] - b[i] - br;
        
        // 4자리수 뺄셈해서 결과가 0 이거나 혹은 0보다 크면 자리내림수는 없다!
        if (c[i] >= 0)
            br = 0;
        else {
            c[i] = c[i] + 10000; // 0보다 작게 되었다면 10000 을 빌리고
            br = 1; // 대신 그 윗자리수에서 1을 뺀다. 등가교환법칙
        }
    }
}

// 출력용
void iResult(short c[])
{
    short i;
    
    // 저장된 배열을 역시 4자리씩 끊어서 보여준다.
    for (i=0; i<NUM; i++)
        printf("%04d ", c[i]);
    printf("₩n");
}

알록달록한 코드 첫머리를 보고자 하실 분들을 위해... (찬조출연: GEdit)

upload image

개인적으로 파이썬에서는 어떻게 이런 긴자리수 연산을 지원하는지
무척 궁금합니다. 귀도 아저씨가 어떤 기가 막힌 알고리즘을 썼을지... ^^;;

에, 오늘은 좀 싱거웠나요?
사실 저는 이 부분 보면서 '아...! 이렇게 하면 되네...!' ...라는 둥,
뻘 소리를 남발했거든요. -_;;; (저는 처음에 한자리씩 차근차근 움직이면서
덧셈하고 자리올림수 만들고 다시 덧셈하고... 이런 걸 구상했었거든요. ㅠ.ㅠ)

참고로 긴 자리수 곱셈과 나눗셈 역시 여러분들께서 예측하신대로,
4자리수 씩 나눠서 쉽게 할 수 있습니다.
다만 곱셈의 경우는 4자리수씩 곱셈을 하고, 5번째 이상 숫자는 그 앞 블럭의
곱셈결과에 더해주는 과정을 처리해야 합니다. 그러니까 자리올림수가 한 개가
아니고 두 개가 있는 거지요. (직접 한 번 해 보아요~)

나눗셈의 경우는 좀 더 손을 가해야 합니다.
4자리수씩 하는 건 맞는데 4자리 나눗셈을 하고 나서 몫은 그대로 결과에 반영하고,
나머지는 10000배 해서 그 다음 블럭에 더한 후 다시 나누기를 해야 합니다.
그리고 계산 방향도 기존과는 반대방향이구요. (역시 직접 한 번 해 보아요~)

이 긴 자리수 사칙연산은 실제로도 굉장히 유용합니다.
어째서 유용한지, 내일 보여드릴 원주율(pi) 값 구하기편에서 같이 알아보도록 합시다.
(긴 자리수 나누기 함수도 사용합니다. 그리고 pi 값은 소수점 이하 1000 자리까지
슈퍼컴퓨터 뺨치고 달랠 수 있을 정도로 정확하게 구할 수 있습니다. ^^)

Tag: 뻘쭘,알고리즘,긴자리,무한자리수,사칙연산,덧셈,뺄셈,C,언어,제약,강타입,gcc,short,분할정복, Date: 2008-11-18 8 Responses
안녕하세요^^ 반갑습니다.
인터넷서핑을 하다가 들르게 되었습니다..
아..저.. 혹시 위문제와 관련해서.. 음..
긴자리수소수점나누셈이을 어떻게 하시는지 알고싶습니다.
이문제로 고생을좀 하고 있는터라.. -_-;;
음.. -_- 두서없는글 읽어주셔서 감사합니다. ㅜ.ㅜ
안녕하세요~ ㅎㅎ
저도 허접이라;; C로 작성한 수치해석 혹은 자료구조 혹은 알고리즘 같은 책들을 보시면 아마 도움이 되시지 않을까 생각 됩니다. 일본인 저자로 생각되는데, 그리 크지 않은 크기의 C 자료구조 책이 있습니다. 그 책 도움이 많이 되니 한 번 찾아보시면 어떨까요? ㅎ
알고리즘 공부를 하다가 궁금해서 물어보고싶은게 있는데..
바쁘시지 않으시다면 답변 부탁드립니다 ~

배열의 크기를 선언할떄 NUM ( ((LIMIT-1) / 4) + 1 ) 왜뺴고 나누고 더하는지 알고싶고.
void에 (short*, short*, short*) 포인트함수르르 왜 세번넣는지 알고싶고
int args어떤의미를 가르키는지 알고싶고,
static short a[NUM+2] 왜 더하기 2를 하는지 알고싶습니다 ㅇㅅㅇ
음;;; 설명을 하기 보다는 C 언어 책을 먼저 한 번 보시는 게 어떠실런지요? 다름이 아니고 사실 저도 잘 몰라서요;;; 대충 설명 드리면 NUM 의 경우엔 LIMIT 자리수에 따라서 배열 크기를 맞추기 위해서 저렇게 된 거구요, short* 받는 건 포인터로 피연산자1,2 와 해당 연산의 결과를 저장할 저장용 배열변수를 받기 위해서 그렇게 된 것입니다~ 나머지 부분도 생각보다 어렵진 않으실테니 책 보시면 금방 이해되실 거에요~
좋은글이 있어서 그냥 지나칠 수가 없네요ㅎㅎ
당당하게 퍼가겠습니다.!!
퍼감에 대한 사항은 구독하였으니 걱정(?) 마세요 ㅎㅎ

좋은글이 있어서 그냥 지나칠 수가 없네요ㅎㅎ
당당하게 퍼가겠습니다.!!
퍼감에 대한 사항은 구독하였으니 걱정(?) 마세요 ㅎㅎ
아.. 제 블로그는 http://ghd5262.tistory.com/ 여기 입니다.
누추하지만 한번 놀러오세요~

뺄셈을 한번 제대로 만들어 봤습니다. 같은 방법으로요....
#include<stdio.h>
#include<string.h>
char t[101],u[101],v[101];
int a[101],b[101],c[101],i,br,e,f,z,k;
int main(int args)
{
for(i=0;i<100;i++)t[i]='0';
for(i=0;i<100;i++)u[i]='0';
scanf("%s%s",t,u);
for(i=strlen(t)-1;i>=0;i-=4){a[e]+=((int)t[i]-48);if(i>0)a[e]+=((int)t[i-1]-48)*10;if(i>1)a[e]+=((int)t[i-2]-48)*100;if(i>2)a[e]+=((int)t[i-3]-48)*1000;e++;}
for(i=strlen(u)-1;i>=0;i-=4){b[f]+=((int)u[i]-48);if(i>0)b[f]+=((int)u[i-1]-48)*10;if(i>1)b[f]+=((int)u[i-2]-48)*100;if(i>2)b[f]+=((int)u[i-3]-48)*1000;f++;}
if(e<f)z=1;
else if(e==f)for(i=0;i<e;i++)if(b[i]>a[i])z=1;
if(z==0)
{
for(i=0;i<e;i++){
c[i]=a[i]-b[i]-br;
if (c[i]>=0)
br=0;
else {
c[i]=c[i]+10000;
br=1;
}
}
for(int i=e-1;i>=0;i--)
{
v[k++]=(char)((c[i]/1000))+48;
v[k++]=(char)((c[i]%1000)/100)+48;
v[k++]=(char)((c[i]%100)/10)+48;
v[k++]=(char)(c[i]%10)+48;
}
int y=1;
for(i=0;i<k;i++)
{
if(v[i]!='0')y=0;
if(y==0)printf("%c",v[i]);
}
if(y==1)printf("0");
}
else
{
for(i=0;i<f;i++){
c[i]=b[i]-a[i]-br;
if (c[i]>=0)
br=0;
else {
c[i]=c[i]+10000;
br=1;
}
}
printf("-");
for(int i=f-1;i>=0;i--)
{
v[k++]=(char)(c[i]/1000)+48;
v[k++]=(char)((c[i]%1000)/100)+48;
v[k++]=(char)((c[i]%100)/10)+48;
v[k++]=(char)(c[i]%10)+48;
}
int y=1;
for(i=0;i<k;i++)
{
if(v[i]!='0')y=0;
if(y==0)printf("%c",v[i]);
}
if(y==1)printf("0");
}
return 0;
}

Leave a comment here!

93c2
비밀번호를 입력해 주세요
이름을 입력해 주세요