큰수의 나눗셈 - 0x100000000 진법

#include <stdio.h>

#include <string.h>

#define MAX 1000

#define MAX2 2000 // 10진수 출력을 위한 수, 10진수 16000 자리 까지 허용

#define MAX8 8000 // 입력되는 수는 8000 자리 까지 허용

//  0번째 칸에는 자리수를 저장합니다. 16진수 0x100000000진법을 사용합니다.

// 1번째 칸에는 일의 자리, 2번째 칸에는 16진수억의 자리, 3번째 칸에는 16진수 조의 자리

// ... 등을 저장합니다. 최대 7996자리까지 출력이 가능합니다.

// notation 1: hex, 2: oct, 3: bin, 4: dec

void printResult(long long [], int);

void copy(long long a[], long long b[]) {

    int i, n=a[0];

    for(i=0;i<MAX;i+=1) { b[i]=a[i]; }

}

void clear(long long a[]) {

    int i;

    for(i=0;i<MAX;i+=1) { a[i]=0; }

    a[0]=1;

}

int compare(long long a[], long long b[]) {

    int i=a[0];

    if(a[0]<b[0]) { return -1; }

    if(a[0]>b[0]) { return 1; }

    while(i>0) {

        if(a[i]<b[i]) { return -1;  }

        if(a[i]>b[i]) { return 1; }

        i-=1;

    }

    return 0;

}

void add(long long a[], long long b[], long long r[]) {

    int i, j;

    long long x=0;

    clear(r);

    r[0]=a[0];

    if(b[0]>r[0]) { r[0]=b[0]; }

    for(i=1;i<=r[0];i+=1) {       // 수의 각 자리와 밑에서 올라온 수를

        x=a[i]+b[i]+x;             // 더해줍니다.

        r[i]=x%0x100000000LL;             // 값이 9999보다 크면 제자리의 수만 남고

        x=x/0x100000000LL;                // 윗자리로 올라갑니다.

    }

    if(x!=0) { 

        r[0]+=1;

        r[r[0]]=x;

    } 

}

void sub(long long a[], long long b[], long long r[]) {

    int i, j;

    long long x=0;

    clear(r);

    r[0]=a[0];

    if(b[0]>r[0]) { r[0]=b[0]; }

    for(i=1;i<=r[0];i+=1) { // 수의 각 자리로

        x=a[i]-b[i]+x;      // 결과에 더해줍니다.

        if(x<0) {

            r[i]=x+0x100000000LL;

            x=-1;

        } else {

            r[i]=x;

            x=0;

        }

    }

    if(x!=0) { 

        for(i=0;i<a[0]+1;i+=1) { printf("%08x ", a[i]); } printf("\n");

        for(i=0;i<b[0]+1;i+=1) { printf("%08x ", b[i]); } printf("\n");

        printf("*****************ERROR*************\n");

        getchar(); getchar();

    } 

    i=r[0];

    while(r[i]==0) { i-=1; }

    if(i==0) { i=1; }

    r[0]=i;

    //for(i=0;i<10;i+=1) { printf("%d ", r[i]); } printf("\n");

}

void mul(long long a[], long long b[], long long r[]) {

    int i, j, k;

    unsigned long long x, y;

    clear(r);

    //printf("a = ");

    //printResult(a, 1);

    //printf("b = ");

    //printResult(b, 1);

    for(i=1;i<=b[0];i+=1) {         // 승수의 각 자리로

        for(j=1;j<=a[0];j+=1) {     // 피승수의 각자리를 곱합니다.

            x=b[i]*a[j];

            y=r[i+j-1];

            y=y+x;

            r[i+j-1]=y%0x100000000LL;

            x=y/0x100000000LL;

            r[i+j]+=x;

        }

    }

    r[0]=a[0]+b[0];   // 결과의 자리수를 구합니다.

    if(r[r[0]]==0) { r[0]-=1; }

}

void div(long long a[], long long b[], long long q[], long long r[]) {

    long long v1[MAX]={1,};

    long long v2[MAX]={1,};

    long long one[MAX]={1,1,};

    long long two[MAX]={1,};

    int i, j, e1, e2, ex;

    long long x;

    double d1, d2, dd;

    clear(q);

    copy(a, r); // 피제수를 나머지에 복사한다. 

                // 당분간 나머지가 임시로 남아있는 피제수 노릇을 한다.

    //printf("[r] = ");

    //printResult(r, 1);

    d2=0;       // 제수의 근사값을 d2와 e2로 나타낸다.

    i=b[0];

    j=0;

    while(i>0 && j<2) {

        d2=0x100000000LL*d2+b[i];

        i-=1; 

        j+=1;

    }

    e2=i;

 

    // 남아있는 피제수가 제수보다 클 동안 계속한다.

    while(compare(r, b)>=0) { 

        // 피제수의 근사값을 d1과 e1으로 나타낸다. 

        d1=0;                 

        i=r[0];

        j=0;

        while(i>0 && j<2) {

            d1=0x100000000LL*d1+r[i];

            i-=1; 

            j+=1;

        }    

        e1=i;

        // 임시 몫의 근사값을 dd와 ex로 나타낸다

        dd=d1/d2;            

        while(dd>0x100000000LL) { dd/=0x100000000LL; e1+=1; }

        //printf("dd=%g e1=%d e2=%d\n", dd, e1, e2); getchar();

        ex=e1-e2+1; 

        clear(v1);

        // 임시 몫은 v1이다. dd와 ex로 부터 v1을 구한다.

        v1[0]=ex;            

        i=0;

        while(ex>0&&i<2) {

            x=dd; dd-=x; dd*=0x100000000; v1[ex]=x; ex-=1; i+=1;

        }

        

        // v1이 클 경우 빼주는 값을 one이라한다.

        clear(one);          

        one[ex+1]=1;

        one[0]=ex+1;

        // v1의 아래 자리는 모두 0으로 채운다. 

        if(i==0) {           

            while(ex>0) { 

                v1[ex]=0; ex-=1; 

            } 

        }

        // 임시몫 v1이 너무 크다면 줄여준다.

        while(1) {

            // 임시 몫 v1과 제수를 곱한 결과를 v2라 한다.

            mul(v1, b, v2);

            // 임시 피제수가 v2보다 크다면 정상적으로 진행한다.

            if(compare(r,v2)>=0) { break; }

            // 만약 임시 피제수보다 v2가 크다면 위에서 구한 임시 몫 v1이 과도하게 크다.

            // v1에서 one을 빼준다.

            sub(v1, one, two);

            copy(two, v1);

        } 

        // 임시 피제수에서 v2를 뺀 결과를 임시 피제수로 한다.

        sub(r, v2, two);

        copy(two, r);

        // q에 v1을 더한 결과를 q로 한다.

        add(q, v1, two);

        copy(two, q);

    }   

    // q의 가장 큰 자리가 0일 경우는 1 자리를 줄여준다.

    while(q[q[0]]==0) { q[0]-=1; }

    if(q[0]<1) { q[0]=1; }

    // r에는 나머지가 남아 있게 된다.

}

// 16진수를 10진수로 바꾸어준다.

void convertResult(long long result[], int d[]) {

    long long a[MAX]={1,};  // 피제수

    long long b[MAX]={1,};  // 제수

    long long q[MAX]={1,};  // 몫

    long long r[MAX]={1,};   // 나머지

    int i=1, x;

    // 십진수 억진법을 사용해서 나머지와 몫을 계속해서 구해갑니다.

    b[1]=100000000; 

    copy(result, a);

    while(1) {

        div(a, b, q, r);

        d[i]=r[1];

        i+=1;

        copy(q,a);

        if(a[0]==1&&a[1]==0) { break; }

    }

    d[0]=i-1;

}

// 출력은 다시 큰 수 부터 출력해 준다.

void printResult(long long result[], int notation) {

    int    decimal[MAX2]={1,};

    const int hex=1, oct=2, bin=3, dec=4;

    int i, x;

    if(notation==1) {

        x=result[0];

        printf("%x", result[x]);

        for(i=1;i<x;i+=1) {

            printf("%08x", result[x-i]);

        }

        printf("\n");

    } else if(notation==2) {

    } else if(notation==3) {

    } else if(notation==4) {   

        convertResult(result, decimal);

        x=decimal[0];

        printf("%d", decimal[x]);

        for(i=1;i<x;i+=1) {

            printf("%08d", decimal[x-i]);

        }

        printf("\n");

    } else {

        printf("ERROR.\n");

    }

}

// 16진수의 표현으로 입력을 하는 것을 전제로 한다.

void convert(char a[], long long b[]) {

    int i, j;

    long long k, x;

    

    i=strlen(a)-1;

    x=0;

    j=1;

    k=1;

    while(i>=0) {

        if(a[i]<='9') {

            x+=k*(a[i]-'0');

        } else {

            x+=k*(a[i]-'a'+10);

        }

        k*=0x10;

        i-=1;

        if(k==0x100000000) {

            k=1;

            b[j]=x;

            j+=1;

            x=0;

        }

    }

    if(k>1) {

        b[j]=x;

        j+=1;

    }

    b[0]=j-1;

}

int main() {

    long long a[MAX]={1,};  // 피제수

    long long b[MAX]={1,};  // 제수

    long long q[MAX]={1,};  // 몫

    long long r[MAX]={1,};  // 나머지

    long long t[MAX]={1,};  // 임시

    long long s[MAX]={1,};  // 임시

    char m1[MAX8];

    char m2[MAX8];

    int i, x, z;

    while(1) {

        printf("1.덧셈 2.뺄셈 3.곱셈 4.나눗셈 0.마침 ");

        i=scanf("%d", &z);

        if(i<1) { 

            fflush(stdin);

            continue;

        }

        if(z==0) { 

            break; 

        } 

        printf("입력1   = ");

        scanf("%s", m1);

        printf("입력2   = ");

        scanf("%s", m2);

        // 입력된 수를 뒤집어 준다.

        convert(m1, a);

        convert(m2, b);

        if (z==1) {

            add(a, b, r);

        } else if(z==2) {

            sub(a, b, r);

        } else if(z==3) {

            mul(a, b, r);

        } else if(z==4) {

            div(a, b, q, r);

            printf("dividend= ");

            printResult(a, 4);

            printf("divider = ");

            printResult(b, 4);

            printf("몫      = ");

            printResult(q, 4);

            printf("나머지  = ");

            printResult(r, 4);

            mul(b, q, s);

            add(r, s, t);

            printf("원래값  = ");

            printResult(t, 1); 

        }

        // 결과를 출력해 준다.

        if(z<4) printResult(r, 1);

    }

    return 0;

}