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

Posted by 적분 ∫2tdt=t²+c
2009.03.29 00:23 프로그래밍/Multi precision
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진법을 쓰는것이라고 생각하면 좋다.
Tags
이 댓글을 비밀 댓글로
  1. 안녕하세요. big integer에 관해서 막 검색하다가 이글보고 설정 방식을 이해해서 큰 도움이 되었습니다.

    그리고 질문이 있습니다.
    1. 가장 효율적인 방법은 1비트도 버리지 않고 DWORD배열에 2진수로 수를 나눠담는 방법이라고 하셨는데, 실제로 이방식을 이용해서 구현하신 것이 맞는것인가요? 적당히 효율적인 예제로 설명해주신 것은 0 ~ 999,999,999를 DWORD에 집어넣고 연산하는 방식이라 이방식으로 구현하신 것인줄 알았거든요.

    2. 위에서 말한 가장 효율적인 방법으로 구현하면 어떤 식으로 연산이 돌게 되나요?
    적당히 효율적인 방법은 0~999,999,999 <-> 2진법 11101 11001 10101 10010 01111 11111의 30자리까지만 사용하는데,
    만약 32비트를 다 쓴다면 2^32-1 = 4,294,967,296-1 = 4,294,967,295 라는 십진법으로 상당히 애매한 수를 어떤 식으로 처리가 가능할까요? 2^32진법을 완전하게 이용한다는 말씀이신가요? (적당히 효율적인 방법은, 2^32진법을 완전하게 쓰진 않더군요)
    • 1. 네, 가장 효율적인 방법이라고 제시한, 이진수로 32비트를 꽉꽉 채워담는 것을 사용했습니다.

      2. 예, 2^32진법을 쓰신다고 생각하시면 됩니다. 이 방법은 여러 연산들이 내부적으로 빠르게 처리될수 있는 장점이 있지만, 10진수로 출력시에 조금 느리다는 단점이 있습니다.