큰정수의 덧셈과 뺄셈(진행중)

#include <stdio.h>

#include <stdlib.h>

typedef struct _bigUnsigned {

    int length;

    int *body;

} bigUnsigned, *pBigUnsigned;

typedef struct _bigInt {

    int           sign;

    pBigUnsigned  mag;

} bigInt, *pBigInt;

// 두개의 부호가 없는 큰정수 a와 b를 비교한다.

// a가 크다면 1을 b가 크다면 -1을 같다면 0을 반환한다.

int bigUCompare(pBigUnsigned a, pBigUnsigned b) {

    int i, n;

    // a의 길이가 b의 길이보다 크다면 1을 반환한다.

    if(a->length>b->length) return 1;

    // a의 길이보다 b의 길이가 크다면 -1을 반환한다.

    if(a->length<b->length) return -1;

    // n은 각 수의 body의 길이를 계산한 것이다.

    // 만진법을 사용하고 있으므로 전체 10진수의 길이를

    // 4로 나누어준 몫이 필요한 원소의 갯수가 된다.

    // 3을 더해준 다음 4로 나누어 준 것은 나머지가 있을 경우

    // 이를 1개로 계산해 주기 위해서 이다.

    n=(a->length+3)/4;

    for(i=n-1;i>=0;--i) { 

        if(a->body[i]>b->body[i]) return 1;

        if(a->body[i]<b->body[i]) return -1;

    }

    return 0;

}

// 두개의 부호가 없는 큰정수 a와 b를 더하여 결과를 반환한다.

pBigUnsigned bigUAdd(pBigUnsigned a, pBigUnsigned b) {

    pBigUnsigned r;

    int i, n, m, nn, *c, *d, x;

    n=(a->length+3)/4;

    m=(b->length+3)/4;

    if(n>m) nn=n; else nn=m;

    nn=nn+1;

    c=(int *)malloc(sizeof(int)*nn);

    for(i=0;i<nn;++i) c[i]=0;

    x=0;

    for(i=0;i<nn;++i) {

        if(i<n&&i<m) c[i]=a->body[i]+b->body[i]+x;

        else if(i<n) c[i]=a->body[i]+x;

        else if(i<m) c[i]=b->body[i]+x;

        //printf("a =%d b= %d c[i]=%d ", a->body[i], b->body[i], c[i]);

        if(c[i]>=10000) { c[i]-=10000; x=1; }

        else x=0;

    }

    i=nn-1;

    while(c[i]==0) i=i-1;

    n=i+1;

    x=c[i];

    i=0;

    while(x>0) { x=x/10; i=i+1; }

    r=(pBigUnsigned)malloc(sizeof(bigUnsigned));

    r->length=n*4+i-4;

    if(n<nn) {

        d=(int *)malloc(sizeof(int)*n);

        for(i=0;i<n;++i) d[i]=c[i];

        free(c);

        c=d;

    }

    r->body=c;

    //printf("r->length=%d ", r->length);

    //printf("r->body[0]=%d ", r->body[0]);

    return r;  

}

// 두개의 부호가 없는 큰정수 a와 b의 차이를 구하여 결과를 반환한다.

// 이때 항상 a의 크기는 b의 크기보다 같거나 큰 경우만 계산하도록 한다.

// 만약 b가 더 크다면 NULL을 반환한다.

pBigUnsigned bigUSub(pBigUnsigned a, pBigUnsigned b) {

    pBigUnsigned r;

    int x=bigUCompare(a, b);

    int i, n, m, nn, *c, *d;

    if(x<0) return NULL;

    if(x==0) {

        r=(pBigUnsigned)malloc(sizeof(bigUnsigned));

        r->length=0;

        r->body=NULL;

        return r;

    }

    // 여기서 부터는 정상적으로 동작합니다. x를 다시 사용합니다.

    n=(a->length+3)/4;

    m=(b->length+3)/4;

    c=(int *)malloc(sizeof(int)*n);

    for(i=0;i<n;++i) c[i]=0;

    x=0;

    for(i=0;i<n;++i) {

        if(i<m) c[i]=a->body[i]-b->body[i]+x;

        else c[i]=a->body[i]+x;

        if(c[i]<0) { c[i]+=10000; x=-1; }

        else x=0;

    }

    i=n-1;

    while(c[i]==0) i=i-1;

    nn=i+1;

    x=c[i];

    i=0;

    while(x>0) { x=x/10; i=i+1; }

    r=(pBigUnsigned)malloc(sizeof(bigUnsigned));

    r->length=nn*4+i-4;

    if(nn<n) {

        d=(int *)malloc(sizeof(int)*nn);

        for(i=0;i<nn;++i) d[i]=c[i];

        free(c);

        d=c;

    }

    r->body=c;

    return r;  

} 

// 두개의 큰정수 a와 b를 더하여 결과를 구하여 반환한다.

pBigInt bigAdd(pBigInt a, pBigInt b) {

    pBigInt c=(pBigInt)malloc(sizeof(bigInt));

    c->mag=bigUAdd(a->mag, b->mag); 

    return c;

}

// 두개의 큰정수 a와 b의 뺄셈을 한 후 그 결과를 반환한다.

pBigInt bigSub(pBigInt a, pBigInt b) {

    pBigInt c=(pBigInt)malloc(sizeof(bigInt));

}

void printBigUnsigned(pBigUnsigned mag) {

    int i, n;

    if(mag->length==0) return;

    i=(mag->length-1)/4;

    printf("%d", mag->body[i]);

    while(--i>=0) printf("%04d", mag->body[i]);

}

void printBigInt(pBigInt a) {

    if(a->sign<0) printf("-");

    printBigUnsigned(a->mag);

    printf("\n");

}

// 문자열로 부터 큰정수를 만들고 이를 반환한다.

pBigInt makeInt(char buf[]) {

    int i, j, x, n, nn;

    char *b=buf;

    pBigInt a=(pBigInt)malloc(sizeof(bigInt));

    if(buf[0]=='-') { 

        a->sign=-1;

        b=&buf[1];

    } 

    else a->sign=1;

    a->mag=(pBigUnsigned)malloc(sizeof(bigUnsigned));

    i=0;

    while(b[i]!=0) i=i+1;

    n=i;

    nn=(n+3)/4;

    a->mag->length=n;

    a->mag->body=(int*)malloc(sizeof(int)*nn);  

    i=0; j=nn-1; x=0;

    nn=4-(n%4);

    while(b[i]!=0) {

        x=10*x+b[i]-'0';

        i=i+1;

        if((i+nn)%4==0) {

            a->mag->body[j--]=x;

            x=0;

        }

    }    

    return a;

}

int main() {

    char buf[1000];

    pBigInt a, b, c;

    printf("큰정수: ");

    gets(buf);

    a=makeInt(buf);

    printf("큰정수: ");

    gets(buf);

    b=makeInt(buf);

    //printf("OK");

    c=bigAdd(a, b);

    printBigInt(c);

    return 0;

}