상세 컨텐츠

본문 제목

BigInteger를 구현해보자 - 8. 10진수로 출력하기(알고리즘)

프로그래밍/Multi precision

by ∫2tdt=t²+c 2009. 4. 26. 02:26

본문

지금까지 정말 bigint를 정의하고 사칙연산들을 수행하는 함수를 짜보았다. 근데 아무리 계산하면 뭐하나 눈에 보이지가 않는걸! 드디어 BigInteger 구현은 막바지에 다다랐다. 10진수 입출력만 끝내면 이제 아무리 큰 수를 계산하는 것도 두렵지 않다.
컴퓨터는 내부적으로 2진수로 수를 저장한다. 따라서 2진수를 10진수로 보여주려면 변환 과정이 필요하다. 2진수를 10진수로 변환하는 가장 쉬운 방법은
10으로 나누어서 나머지를 차례로 취하는 것이다.

n을 10진수로 출력하기(Psuedo코드)
방법1-1. 10으로 나누기.
print_dec(n)
{
  print_dec(n/10)
  print(n%10)
}
이 방법은 간단하고 이해하기 쉬울지는 몰라도 log_10(n)번의 나눗셈과 재귀호출이 필요하다.

방법1-2. 100000000(10^9)으로 나누기 (32비트 최적화)
print_dec(n)
{
  print_dec(n/1000000000)
  print(n%1000000000)
}
32비트 정수를 한 단위로 사용했으므로, 32비트 정수에 들어갈수 있는 십진수 최대 자리인 9개씩 숫자를 출력하는 것이다.
방법1보다 9배 빠르다.

아무리 그래도 나눗셈은 속도가 나지 않는다. 그래서 예전에 2진수를 BCD코드로 변환할때 쓰이던 double dabble 알고리즘 (시프트 더하기 3)을 소개한다.
BCD코드는 한자리에 4비트를 써서 10진수를 나타낸다. 따라서 BCD코드를 4비트씩 끊어서 출력하면 그게 곧 10진수로 출력하는것이다.
방법2-1. 시프트 더하기 3

3F(00111111)을 BCD코드로 변환하는 과정이다. 3F는 총 8비트(4비트가 한자리. 두 자리이므로 8비트)이므로, 8번 왼쪽으로 시프트해 나가면 되는데, 시프트해 나가면서 5이상의 자리에(그림에 약간의 에러가 있군요.) 3을 더해주면 된다.
나눗셈 없이 시프트연산과 더하기만으로 10진수로 변환했다. n을 10진수로 변환하는데, log_2(n)번의 비트연산과 여러 번의 덧셈이 사용된다. 하지만, 이 방법의 단점은 요즘 CPU의 기본 레지스터 크기가 32비트, 64비트로 커짐에 따라 4비트 단위로 접근하는게 점점 비효율적으로 되었다는 것이다.

방법2-2. 시프트 더하기 1647483648 (32비트 최적화)
이 방법은 위의 시프트 더하기 3을 32비트에서 최적화한것이다.
방법2-1은 4비트를 한 단위로 두고 계산했지만, 이 방법은 32비트를 한 단위로 두고, 32비트로 10진수 9자리를 표현한다.

n번 왼쪽으로 시프트 해나가는데, 시프트 해나가는 도중 500000000의 자리에 1647483648을 더해주면 된다.

관련글 더보기

댓글 영역