BigInteger를 구현해보자 - 1. BigInteger의 개요

Big Integer는 기본적인 자료형 int보다 훨씬 더 큰 정수를 저장하기 위한 자료형이다. 특별한 일 없으면 int64로 어지간한 수는 다 표현할 수 있지만, 때때로 매우 큰 수가 필요하다규.

가장 쉬운 구현 방법은 char배열을 사용해서 10진수로 각 자리수를 저장하는 것이다. n자리수를 저장하는데 n바이트가 필요하므로, n바이트로 표현할수 있는 수 범위는 0 ~ 10^n -1 이다. 그런데 이 방법은 매우 비효율적이다. 그래서 좀 더 효율적인 방법으로 DWORD배열을 사용(32비트 프로그램 기준)하는데, 각 DWORD마다 10진수로 숫자를 9자리씩 저장하는 것이다. DWORD가 대략 42억까지 포함할 수 있으므로, 최대 9자리씩저장 할수 있다. n바이트로 표현할수 있는 수 범위는 0 ~ 10^(9*n/4) -1 이다. 이 두 가지 방법은 약간의 비효율이 있지만, 10진수로 출력할 때는 매우 빠르다는 장점이 있다.
가장 효율적인 방법은 1비트도 버리지 않고 DWORD배열에 2진수로 수를 나눠담는 방법이다. 연산 속도는 가장 빠르지만 10진수로의 출력은 가장 느리다. 또 가장 효율적인 만큼 가장 구현하기도 까다롭다. 필자는 이 방법으로 Big Integer를 구현해볼 것이다.

DWORD의 배열로 숫자 표현을!

dats[0]	dats[1]	dats[2]	dats[3]	...
5	100	13	25	...
0~31자리비트	32~63자리비트	64~95자리비트	96~127자리비트	...

dats가 나타내는 수는 5*1 + 100*2^32 + 13*(2^32)^2 + 25*(2^32)^3 가 된다. 2^32진법을 쓰는것이라고 생각하면 좋다.