큰 수 구하기

친절한 설명이 있는 좋은 글을 봐서 주인장 허락(?)을 구하고 퍼왔다.

출저는 미리 밝혀둔다.

[http://sirini.net/grboard2/blog/view/741]

좋은 자료가 많은 것 같아 종종 들러야 겠다.

긴긴 수를 구하는 알고리즘이며, 공부하여 내것으로 만들어야겠다.

아래는 글의 내용이다.

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

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

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

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

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

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


(출력부분을 보시면 일부로 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)



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

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

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

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

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