Skip to content

Instantly share code, notes, and snippets.

@sooop

sooop/BigInt.c Secret

Last active August 29, 2015 14:09
Show Gist options
  • Save sooop/fd3c194aba489230869b to your computer and use it in GitHub Desktop.
Save sooop/fd3c194aba489230869b to your computer and use it in GitHub Desktop.
8바이트 이상 크기의 정수 계산을 위한 BigInt 타입 구현
#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
* 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);
//********************************************************************
#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;
}
@sooop
Copy link
Author

sooop commented May 31, 2015

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment