8바이트 이상 크기의 정수 계산을 위한 BigInt 타입 구현

BigInt.c

#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "BigInt.h"

#define UNITLENGTH (4)
#define UNITLIMIT (9999)
#define UNITSIZE (10000)

struct _BigInt {
    unsigned int cellCount;
    unsigned int numberCount;
    int *data;
    char *description;
    bool _desc_created;
};

typedef struct _BigInt* BigInt;

static int convertShortStringIntoInteger(const char* str);
static void parseString(const char* str, int** array);
static BigIntRef BigIntShift(BigIntRef a, unsigned int s);
static BigIntRef BigIntMultiplyHelper(BigIntRef a, int s);

void BigIntRelease(BigIntRef r)
{
    BigInt b = (BigInt)r;
    if(b->_desc_created){
        free(b->description);
    }
    free(b->data);
    free(b);
}


BigIntRef BigIntCreateWithString(const char* str)
{
    int len = strlen(str);
    BigInt r = (BigInt)(malloc(sizeof(struct _BigInt)));
    r->cellCount = (int)ceil((double)len / UNITLENGTH);
    r->numberCount = len;
    r->_desc_created = NO;
    r->description = NULL;
    parseString(str, &r->data);
    return (void*)r;
}

BigIntRef BigIntCreate(int* data, int cellC, int numberC)
{
    BigInt r = (BigInt)(malloc(sizeof(struct _BigInt)));
    r->data = data;
    r->numberCount = numberC;
    r->cellCount = cellC;
    r->_desc_created = NO;
    r->description = NULL;
    return (void*)r;
}

void BigIntTraverse(BigIntRef r)
{
    BigInt b = (BigInt)r;
    int i;
    for(i=0;i<(int)b->cellCount;i++){
        printf("%04d : %04d\n", i, b->data[i]);
    }
}

const char* BigIntGetDescription(BigIntRef r)
{
    BigInt b = (BigInt)r;
    if(!b->_desc_created){
        b->description = (char*)malloc(sizeof(char) * b->numberCount + 1);
        b->description[b->numberCount] = 0;
        int currentPosition = b->numberCount - 1;
        int i, j, k;
        for(i=0;i<(int)b->cellCount;i++){
            k = b->data[i]; 
            for(j=0;j<UNITLENGTH;j++){
                b->description[currentPosition] = k % 10 + '0';
                currentPosition--;
                k = k / 10;
                if(currentPosition < -1){
                    break;
                }
            }
        }
    }
    return b->description;
}


BigIntRef BigIntAdd(BigIntRef a, BigIntRef b)
{
    BigInt x = (BigInt)a;
    BigInt y = (BigInt)b;
    unsigned int maxCellCount = x->cellCount > y->cellCount ? x->cellCount : y->cellCount;
    int* tempArray = (int*)malloc(sizeof(int) * (maxCellCount + 1));
    int flag = 0;
    int d = 0;
    int i,j,k;
    for(i=0;i<(int)maxCellCount;i++){
        j = i >= (int)x->cellCount ? 0 : x->data[i];
        k = i >= (int)y->cellCount ? 0 : y->data[i];
        d = j + k + flag;
        if(d > UNITLIMIT){
            flag = 1;
            d = d % UNITSIZE;
        } else {
            flag = 0;
        }
        tempArray[i] = d;
    }

    if(flag){
        tempArray[i] = flag;
        maxCellCount++;
    } 

    unsigned int maxNumberCount = UNITLENGTH * (maxCellCount - 1) + (unsigned int)(floor(log10(tempArray[maxCellCount-1]))) + 1;
    int* resultData = (int*)malloc(sizeof(int) * maxCellCount);
    memcpy(resultData, tempArray, sizeof(int) * maxCellCount);
    BigInt result = BigIntCreate(resultData, maxCellCount, maxNumberCount);
    free(tempArray);
    return (BigIntRef)result;
}


/** 문자열을 4자리씩 쪼갠후 int의 배열로 리턴해준다. **/
void parseString(const char* str, int** array)
{
    int len = strlen(str);
    int arraySize = ceil((double)len / UNITLENGTH);
    char* ar = (char*)malloc(sizeof(char)*(UNITLENGTH + 1));
    *array = (int*)malloc(sizeof(int)*arraySize);
    int i, j;
    int position;
    for(i=0;i<arraySize;i++){
        strcpy(ar, "0000"); // "0" * UNITLENGTH
        for(j=0;j<UNITLENGTH;j++){
            position = len - 1 - (UNITLENGTH * i) - j;
            if(position >= 0){
                ar[4-j-1] = str[position];
            } else {
                break;
            }
        }
        (*array)[i] = convertShortStringIntoInteger(ar);
    }
    free(ar);
}


/** 4자리 미만의 문자열을 정수로 변경해주는 함수 **/
int convertShortStringIntoInteger(const char* str)
{
    int len = strlen(str);  // strlen은 마지막 널 종료문자는 세지 않는다.
    int result = 0;
    int i;
    for(i=0;i<len;i++){
        char c = str[i];
        result = result * 10 + (int)(c - '0');
    }
    return result;
}


BigIntRef BigIntMultiply(BigIntRef a, BigIntRef b)
{
    BigInt r = (BigInt)b;

    int i;
    int rightCellCount = (int)r->cellCount;
    BigInt* tempResults = (BigInt*)malloc(sizeof(BigInt) * rightCellCount);
    BigInt Result = BigIntCreateWithString("0");
    BigIntRef temp;

    for(i=0;i<rightCellCount;i++){
        temp = BigIntMultiplyHelper(a, r->data[i]);
        tempResults[i] = BigIntShift(temp, i);
        BigIntRelease(temp);
    }

    for(i=0;i<rightCellCount;i++){
        temp = BigIntAdd(Result, tempResults[i]);
        BigIntRelease(Result);
        Result = temp;
    }

    for(i=0;i<rightCellCount;i++){
        BigIntRelease(tempResults[i]);
    }

    free(tempResults);
    return Result;
}


static BigIntRef BigIntMultiplyHelper(BigIntRef a, int s)
{
    int i;
    int d=0, flag=0;
    unsigned int newNumberCount;
    int *newResultArray;

    BigInt result;
    BigInt b = (BigInt)a;
    unsigned int newCellCount = b->cellCount;
    int* tempArray = (int*)malloc(sizeof(int) * (b->cellCount + 1));

    for(i=0;i<(int)b->cellCount;i++){
        d = b->data[i] * s + flag;
        if(d > UNITLIMIT){
            flag = d / UNITSIZE;
            d = d % UNITSIZE;
        } else {
            flag = 0;
        }
        tempArray[i] = d;
    }

    if(flag){
        tempArray[i] = flag;
        newCellCount += 1;
        newNumberCount = UNITLENGTH * (i - 1) + (unsigned int)floor(log10(flag)) + 1;
    } else {
        newNumberCount = UNITLENGTH * (i - 2) + (unsigned int)floor(log10(flag)) + 1;
    }

    newResultArray = (int*)malloc(sizeof(int) * newCellCount);
    memcpy(newResultArray, tempArray, sizeof(int) * newCellCount);

    result = BigIntCreate(newResultArray, newCellCount, newNumberCount);
    free(tempArray);
    return (void*)result;
}


static BigIntRef BigIntShift(BigIntRef a, unsigned int s)
{
    BigInt b = (BigInt)a;
    int* tempArray = (int*)malloc(sizeof(int) * (b->cellCount + s));
    int i, j;
    for(j=0;j<(int)s;j++){
        tempArray[j] = 0;
    }
    for(i=0;i<(int)b->cellCount;i++){
        tempArray[i+s] = b->data[i];
    }
    BigInt result = BigIntCreate(tempArray, b->cellCount + s, b->numberCount + (UNITLENGTH * s));
    return result;
}

BigInt.h

/*
 * BigInt.h
 * 2015. 05. 28 by sooop.
 *
 *
 * 큰 정수 덧셈하기
 * 큰 정수는 작은 조각으로 나누고
 * 각 조각들과 올림처리된 플래그 값을 더한다.
 * 최종적으로 올림처리된 플래그 값이 남아있으면 최상위 조각을 더해준다. 
 * 조각을 순서대로 연결해주면 끝
 *
 *
 * BigInt 구조체는 큰 정수 계산을 쉽게 하기 위해서 사용하는 구조체
 * 정수를 4자리 단위로 끊어서 리틀엔디언 방식으로 저장한다. 
 * 생성은 문자열을 기준으로 한다. 
 * --> 문자열을 뒤에서부터 4자리씩 끊는 함수가 필요하다. 
 *  그리고 출력은 역시 문자열로 해야 하므로 BigInt 타입의 값을
 *  문자열로 표현해주는 함수가 필요하다. 
 */

typedef unsigned short bool;
#define YES ((bool)(1))
#define NO ((bool)(0))

typedef void* BigIntRef;


BigIntRef BigIntCreateWithString(const char* str);
BigIntRef BigIntCreate(int* data, int cellC, int numberC);

BigIntRef BigIntAdd(BigIntRef a, BigIntRef b);
BigIntRef BigIntMultiply(BigIntRef a, BigIntRef b);
const char* BigIntGetDescription(BigIntRef r);
void BigIntTraverse(BigIntRef r);

void BigIntRelease(BigIntRef r);



//********************************************************************

temp.c

#include <stdio.h>
#include "BigInt.c"

int main(){
    BigIntRef a = BigIntCreateWithString("2");
    BigIntRef b = BigIntCreateWithString("2");
    BigIntRef temp;
    int i;
    for(i=0;i<999;i++){
        temp = BigIntMultiply(a, b);
        BigIntRelease(a);
        a = temp;
    }
    BigIntTraverse(a);
    printf("2^1000 is : %s\n", BigIntGetDescription(a));

    BigIntRelease(a);
    BigIntRelease(b);

    return 0;
}

코드가 좀 엉망인데, UInt64를 써서 한 번에 여덟자리씩 계산하도록하여 효율을 높이며,
가능한 문자열과 정수배열을 상호변환하지 않는 것이 성능이 도움이 된다.