투 명 테 잎

큰 수를 저장하는 방법은 다양할 것입니다.
우선, char형 배열을 만들어서 각자리를 십진수로 저장하는 방법이 있습니다.

char *result = "12345";

예전에 PKU 1001번 문제를 풀 때, 위와 같은 방식을 사용하였습니다.
문제를 대략 설명드리면,
0.0 < R < 99.999  사이에, 소수점을 포함하여 6글자의 문자열을 입력받고
0 < n <= 25 사이의 숫자 n을 입력 받은 후,
R ^ n (R의 n승)을 구하는 문제였습니다.
R을 n번 곱하는 식으로 풀었는데,
char result[500];을 정의한 후, 문자열로 입력을 받아
두 십진수의 곱셈을 하는 식으로 하였습니다.
하지만 이런 방식에는 두가지의 문제점이 있습니다.

첫 번째, char형 배열로 숫자를 저장할 때는 공간이 낭비됩니다.
char a[3] = "10";
십진수 10을 저장하기 위해 '\n' 포함 3의 크기를 가지는 배열을 정의했습니다.
하지만 char형은 1바이트의 크기를 가집니다. 8비트이죠.
8비트로는 0부터 255(2^8-1)까지의 숫자를 저장할 수 있습니다.
하지만 이 거대한 공간에 단지 0부터 9까지의  숫자밖에 저장하지 않습니다. 
0 ~ 9까지의 숫자를 입력 받는데는 4비트면 충분합니다.
숫자 한자리를 저장할 때마다 4비트씩이나!! 낭비되는 현상이 발생합니다.
작은 수라면 몰라도 만들려고 하는 BigInteger 클래스는 상당히 큰 수를 다루어야 하기 때문에
이런 방식은 고려 할 수 없습니다.

두 번째, 연산 과정이 느려집니다.
한자리한자리씩 연산하고 자릿수 올림,내림을 반복해야 하기 때문에 당연히 느릴 수 밖에 없습니다.
n자리의 두 정수의 곱셈을 한다고 가정해보겠습니다.
이 연산에서는 n^2번의 곱셈과 n번의 나눗셈 n번의 나머지 연산이 필요합니다.
n이 100억이라고 생각하면 어휴.. ㅋㅋ

위의 두가지 이유 때문에
여기서는 큰수를 저장하기 위해 다른 방식을 사용합니다.
unsigned long형 배열에 2진수로 숫자를 저장하는 겁니다.
그러면 1비트의 공간도 낭비하지 않고 알차게(?) 숫자를 저장할 수 있습니다.
쉽게 생각해서 2^32진법을 사용한다고 보시면 됩니다.

unsigned long blk[4];

blk[0]	blk[1]	blk[2]	blk[3]
1	2	3	4

 
다음과 같이 표현할 경우 나타내지는 수는
1 + ( 2 * 2^32 ) +  ( 3 * ( 2^32 )^2 ) + ( 4 * ( 2^32 )^3 )
와 같이 어마어마한 숫자가 담아집니다.

또한, 배열 저장 방식에 리틀 에디안(Little Endian) 방식을 사용합니다.
즉, 배열의 앞 부분이 낮은 자릿수를 나타내는 것이지요.

<소개 글>

두 달에 걸쳐서 Biginteger 클래스를 c++로 구현했습니다.
여기서는 그 두 달을 시간 순으로 배열해보며 어떤 순서로 만들었는지 회고해보겠습니다.

약 한달간을 자료조사에 투자했습니다.
큰 정수를 표현해보고 싶다는 생각이 들었지만, 어떻게 표현해야할지 몰랐습니다.
매우 큰수는 기존의 정수형으로 표현할 수 없었기 때문에, 지금까지 공부한 것을 바탕으로 새로운
클래스를 만들어야만 했습니다.
그래서 자료조사를 시작했고, 3가지 괜찮은 BigInteger 자료를 찾게 되었습니다.
우선 자바로 만들어진 BigInteger를 찾았습니다.
(자바에서는 기본적으로 BigInteger형을 지원한다는 것을 알고 참.. 부러웠습니다.)
저는 현재 C/C++를 공부하는 중이여서 자바의 J도 알지 못합니다.
자바도 같은 C 계열이기 때문에, 약간의 코드는 이해할 수 있었으나 한계가 있었습니다.
그래서 그 다음으로 찾은 자료가  Matt McCutchen이라는 외국인이 만든 것을 찾았습니다.

C++ Big Integer Library - Matt McCutchen's Web Site

C++로 구현되었기 때문에 소스 코드 읽기가 매우 편했습니다!
많은 기능이 구현되어있었고, 고맙게도 비록 영어지만 주석을 많이 달아주어서 이해하기 쉬웠습니다....
그래서 모든 소스 코드를 인쇄하여.. -0-.. 보기 시작했습니다.
정확히는 모르겠지만, 한 5000줄(?) 되는거 같았습니다.. 후..
처음 쭉.. 읽으니.. 무슨 말인지 모르겠습니다.
잘 읽다가 어느 순간 '어 뭐지?', 이 상태의 연속이였습니다.
책 말고, 처음으로 다른사람이 만든 소스를 읽어보는거라 적응이 안됬습니다.
'아 왜 대문자를 여따 쓰지..', '아 변수명이 왜 이따구야..' 이런 사소한거부터,
'아놔.. 먼 함수가 이리 왔다갔다허냐..' 하는 것까지 불만 한 가득이였습니다...
아마 제가 만든것을 보시는 분들도 같은 생각이시겠죠.. ㅠㅠ
최대한 정리정돈 잘 해서 만들었습니다.. ㅜㅠ
(무슨 말인지 모르겠다면 댓글로 막 물어보셔도 됩니다.. ^^)
Matt씨가 만든걸 몇번 반복해서 읽고 이해하는데만 약 3주정도의 시간을 보냈습니다.
사칙연산 부분이 가장 난해했습니다. 그 중에서도 나눗셈이 어려웠습니다.
음.. 도저히 이건 무슨 말인지 몰라서.. 세번째로 다른 자료를 찾았습니다.
이것은 오.. 지져스... 우리나람사람이 만든것이라 이해하기 100만배는 쉬웠습니다. !!

우리 나라 사람이 만든 C++ BigInteger class

사칙연산 부분, 출력과 입력 부분을 보기 위해 참고하였고
Matt씨가 사용한것과는 다른 알고리즘을 사용하였고
알고리즘이 이해하기 쉬워서 많은 도움이 됬습니다.

위 세가지를 보면서, 어느정도 감이 왔습니다.
우선 Matt씨가 만든것을 약간 개조하는 식으로 할려고 했습니다.
그런데, 사람심리가 무서운 것이, 자꾸 Matt씨가 만들었던게 신경이 쓰였습니다.
조금만 막혀도 Matt씨의 코드를 보려고 하고, 제 스스로는 생각하려고 하지 않았습니다.
1주일정도를 그렇게 날렸습니다.
그리고는 처음부터 제가 만들기로 했습니다.
그렇게 해서 약 2~3주 정도의 시간을 들여서 제 스스로가 만족할만한 클래스를 완성하게 되었습니다.
그리고 약 1주일가량 동안 테스트 코드를 작성하였습니다.
작성할때는 그렇게 완벽해 보이던 코드가 여러군데에서 헛점을 들어냈습니다..
수정한 곳도 많았고 첨가한 부분도 많았습니다.
이제 마지막 자가 테스트를 하려고 합니다.
이 글을 쓰면서 코드 한줄 한줄, 단어 한글자 한글자씩 점검해보려고 합니다.
그럼 시작하겠습니다 !! 

const는 상수성을 지정하기 위해서 사용합니다.
그런데.. 이게 포인터와 사용하다 보면 많이 헷갈립니다..
(저만 그런건가요.. ㅠㅠ)
그래서 간략하게 정리해볼까 합니다. 

변수 a에 대해서 const를 붙일 수 있는 경우는

// const 한 개
/* 1 */const char *a = "abcd";
/* 2 */char const *a = "abcd";
/* 3 */char *const a = "abcd";

// const 두 개
/* 4 */const char *const a = "abcd";
/* 5 */char const *const a = "abcd";

 

요정도가 되겠습니다.
여기서 1번과 2번은 같은 의미입니다.
그냥 const와 char의 순서만 다른겁니다.
1,2번과 3번의 의미가 다릅니다.

밑에 글을 읽기 전에 이 한 줄을 읽고 보시면 이해하시기 편하실겁니다.
"const는 바로 뒤에것을 상수로 만든다!!!"

하나하나 살펴보시죠.. ^^
* 표시 앞에 const 지정자가 붙으면(1, 2번)
char *a가 상수성을 가진다는 겁니다.
char *a == "abcd"이므로 "abcd"가 상수라는 뜻이됩니다.
즉, "abcd"를 못 바꾼다는 겁니다.
a[0] = '2', 이렇게 대입을 못한다는 겁니다.
a[0]에 해당하는 값은 "abcd"의 'a'이고 이게 상수이므로 바꾸지 못합니다.
하지만 변수 a 자체는 상수가 아니기 때문에 주소는 바꿀 수 있습니다.
즉, a = "1234", 이렇게 a에 새로운 문자열 주소를 대입 할 수 있는 거죠.

* 표시 뒤에 const 지정자가 붙으면(3번)
이건, 변수 a가 상수라는 겁니다.
즉, 변수가 상수성을 가지기 때문에 '주소'를 바꾸지 못한다는 뜻이 됩니다.
a = "1234", 이렇게 못 바꾼다는 거죠.
왜냐하면, 주소값이 상수성을 내포하기 때문에 다른 문자열 주소로 바꾸지 못하는 겁니다.
따라서 이런 경우에는 선언과 동시에 값을 대입해줘야 합니다.
하지만 대입받은 값들이 상수는 아니기 때문에
a[0] = '2', 이렇게 하나하나씩 바꿀 수 있습니다.

그럼 4,5번과 같이 const를 둘다 쓰면 어떻게 될까요?
1, 2번과 3번 둘 다의 속성을 가지게 됩니다.

1. 변수 자체가 상수다, 고로 한번 대입받으면 다른것을 대입 못한다.
2. 대입 받은 값 자체가 상수다, 고로 대입 받은 값을 하나하나씩도 못바꾼다.
3. 선언과 동시에 값을 대입해줘야 하는건 기본이다.(* 뒤에 const가 있으므로)