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

지금까지 정말 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을 더해주면 된다.

5이상의 자리에 3을 더해주는 이유는 BCD코드의 한 자리는 4비트로써 16이 되어야 자리 올림이 발생하는데, 우리는 10진수 단위로 수를 끊어야 하므로 10이상이 되었을때 자리올림이 발생하도록 하여야 한다. 따라서 각 자리가 5이상이 되었을때 3을 더해주면 그 자리는 8이상이 되고, 다음번에 왼쪽으로 한 번 시프트 되므로 16이상이 되어서, 자리올림이 발생한다. 이 방법을 응용하면 2진수를 2n진수꼴의 형태로 나눗셈 없이 바꿀수 있다.

나눗셈 없이 시프트연산과 더하기만으로 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을 더해주면 된다.

이 방법은 32비트를 한 자리로 보기때문에, 2^32가 되어야 자리 올림이 발생한다. 그런데 10^9이상이 되었을때 자리올림이 발생하여야 하므로, 500000000 이상이 되었을때 1647483648을 더해주면, 2147483648이 되고, 다음번에 왼쪽으로 한 번 시프트 되므로 4294967296(2^32)이 되어서 자리올림이 발생한다.