코드에 주석을 달다
장황하게 쓰게 되었는데 이것만으로도
충분히 출력하는 부분에 대해서는 설명이 가능 할 것 같아서
주석 부분을 올립니다.
혹시 그래도 아사무사하시면 아래 링크를 참조하세요. ^^
[진법 변환 - 1] 2진법에서 BCD로
장황하게 쓰게 되었는데 이것만으로도
충분히 출력하는 부분에 대해서는 설명이 가능 할 것 같아서
주석 부분을 올립니다.
혹시 그래도 아사무사하시면 아래 링크를 참조하세요. ^^
[진법 변환 - 1] 2진법에서 BCD로
/*
* radix_a부터 radix_d까지는
* 입력, 출력 함수에서 사용하기 위해 작성하였고
* 나오게 된 이론적인 배경은 다음과 같습니다.
*
* 일반적으로 2진수로 되있는 값을 10진수로
* 출력하기 위해서는 2진수 값을 bcd로 바꾼 후, 출력합니다.
* (여기에 대한 내용은 인터넷에서
* bcd, binary to bcd, shift and add 3, double dabble
* 등의 검색어로 다양한 정보를 얻으실 수 있습니다.)
* 여기서도 물론 같은 방법을 사용하여 출력, 입력을 하며
* 좀 더 일반적이고 확장된 정리를 사용합니다.
*
* "binary to bcd"("2진수를 bcd로")
* bcd란 간단히 10진법 배열입니다.
* 0부터 9라는 숫자를 나타내기 위해서는
* 최소 4비트가 필요하며(2^4=16) 4비트로 10진법의
* 한자리를 나타낸다는 것이 bcd입니다.
* 즉, bcd로 바꾼다는 말은 2진수 값을 10진법의 배열로 바꾼다는 이야기이며
* 이것을 일반화 해본다면 다음과 같습니다.
*
* "binary to arbitrary radix"("2진수를 임의의 진법으로")
* 2진수 값을 n진법으로 출력 하고자 한다면
* n진법의 배열로 바꾸어주면 됩니다.
* 그럼 여기서 n진법 배열의 원소는 최소 몇비트가 필요할까요?
* 우리가 표현하고자 하는 진법은
* 2~36사이의 진법입니다.
* 여기서 36진법이 한자리당 필요한 비트수가 제일 많습니다.
* 최소 6비트가 필요합니다.(2^6=64)
* 우리가 사용할 수 있는 타입 중 가장 작은 것은 1바이트(8비트)이며
* 36진법이라고 치면 한 자리당 2비트(8-6=2)를 비효율적으로 사용합니다.
* 정리하자면 bcd를 일반화 한 것은
* 2진수 값을 n진법으로 출력하는 방법이며
* n진법 배열을 사용하여 한자리씩을 표현한다는 것입니다.
* 그러나 이렇게 한자리씩 끊어서 나타내면
* 큰수를 입,출력해야 하는 상황에서
* 메모리가 비효율적으로 낭비 될 뿐만 아니라
* 1바이트와 같이 작은 비트를 접근하는 연산을 하여 속도도 나지 않습니다.
* 따라서 여기서 한발 더 나아가
* 32비트에 최적화 시킵니다.(cpu 비트수)
*
* "binary to arbitrary radix in 32bits("2진수를 임의의 진법으로(32비트 최적화)")"
* 일단, 진법 변환 이야기를 살짝 하겠습니다.
* 9진법으로 17을 3진법으로 바꾼다면 어떻게 구할까요?
* 9는 3의 2승입니다. 즉, 9진법의 한자리는 3진법으로 두자리라는 말이 됩니다.
* (27진법을 3진법으로 나타낸다면 27(3 ^ 3)진법의 한자리는 3진법으로 3자리가 됩니다.)
* 9진법 1은 3진법으로도 1, 9진법 7은 3진법으로 21입니다.
* 즉, 3진법으로 121이 됩니다.
* 여기서 알 수 있는 것은 진법 변환에 있어
* n진법을 r진법으로 변환한다고 하였을 때(n > r)
* n진법이 r진법의 지수승으로 나타낼 수 있다면(=> n == r ^ x)
* n진법의 r진법 변환은 추가적인 나눗셈 연산 없이도
* 각 자리를 쪼개는 것만으로 변환이 가능하다는 것입니다.
* 자 이제, 무엇을 해야 할지 감이 오시나요?
* n의 x승 진법으로 숫자를 저장 한 후,
* n ^ x승 한자리를 x개의 자리로 쪼개는 전략을 쓰겠다는 겁니다!
* 그리고 이 전략을 32비트에 최적화 시키는 것입니다!
* 그럼 과연 n진법의 몇 승 진법을 써야 할까요?
* 여기에서 radix_a를 구한 이유가 나옵니다.
* 그 식은 다음과 같습니다.
* 2^32 >= n ^ x (n진법의 x승)을 만족하는 제일 큰 x
* 32비트로 나타낼 수 있는 n진법의 최대 승을 구하는 식입니다.
* 이것을 radix_a라는 배열에 저장해 두었습니다.
* 그리고 n ^ x 값을 radix_b라는 배열에 저장해 두었구요.
* 여기까지를 정리해보면
* 2진수 값을 n진법으로 변환, 출력하는데 있어
* 32비트에 최적화 시키기 위해서
* 2진수 값을 n진법의 x승 진법으로 값을 변환한 후,
* n진법의 x승 진법의 각 자리를 n진법 x개로 쪼개는 식으로
* 출력한다면 이것은 2진수 값을 n진법으로 표현하는 것과 같다!
* 라고 정리 할 수 있습니다.
* 후... 이제 어떻게 해야 하는지 방향은 정했습니다.
* 근데 중간 과정이 설명되지 않았습니다.
* 2진수 값을 n ^ x 진법으로 저장한다고 했는데
* 어떻게 저장할것인가 하는 겁니다.
*
* "Shift and Add 3(Double Dabble) algorithm"
* 진법 변환 하는 방법 아시나요?
* 10진수를 8진법으로 바꿀려면
* 8로 나누어서 그 나머지들을 역순으로 쓰면 된다고 배웠습니다.
* 즉, 어느 수를 n진법으로 바꾼다면 그 수를 n으로 나누어서
* 그 나머지들을 역순으로 쓰면 됩니다.
* 이것을 위의 32비트 최적화의 개념에 적용하다면
* 출력하고자 하는 숫자를 n ^ x로 나누어
* 그 나머지를 역순으로 저장하면
* 2진수 값을 n ^ x진법으로 바꾸어 저장할 수 있습니다.
* 초기 출력 함수의 알고리즘도 그랬습니다.
* n ^ x로 나누어서 값을 _ltoa_s함수를 사용하여
* 각 자리를 n진법으로 변환 출력하는 것입니다.
* 근데, 이 방법은 확실히 느립니다.
* 곱셈, 나눗셈보다는 덧셈, 뺄셈이 빠르며
* 덧셈 뺄셈보다는 비트, 쉬프트 연산이 빠릅니다.
* 여기서 사용할 알고리즘 이름이
* shift and add 3 알고리즘 같은말로 double dabble 알고리즘(이하 더블대블)입니다.
* 이름에서와 같이 binary를 bcd로 바꾸는데 쉬프트와 덧셈만을 이용하며
* 나누어서 나머지를 취하는 방법에 비해서 효율적인 알고리즘입니다.
*
* 아래 링크는 위키피디아에 있는 더블대블 알고리즘에 대한 설명글이며
* http://en.wikipedia.org/wiki/Double_dabble
*
* 다음의 링크는 제 블로그에 위의 글을 번역해본 것입니다.
* http://transparenttape.tistory.com/entry/Double-DabbleShift-and-add-3-Algorithm
* 더블대블 알고리즘을 잘 모르시겠다면 참고하시기 바랍니다.
*
* "Double Dabble algorithm in 32 bits"
* radix_a를 보면 32비트에는 10진법으로는 9자리를 표현 할 수 있음을 알 수 있습니다.
* 더블 대블 알고리즘을 이해 하셨다면, 여기도 이해가 될 것입니다.
* 5이상에 3을 더하던 것을
* 500000000(5억)이상에 1647483648을 더해주면 됩니다.
* 5억 이상인 수에 저 숫자를 더한 후, 쉬프트를 해주게 되면 2^32이상이 되어
* 자리올림이 발생하게 됩니다.
* 원리는 동일하며, 숫자만 다를뿐입니다.
*
* "Double Dabble algorithm in 32 bits for arbitrary radix"
* 이제 더블대블 알고리즘을 수학적으로 접근해보겠습니다.
* 5이상인 블럭에는 3을 더해주고 쉬프트 해준다가 이 알고리즘의 핵심입니다.
*
* 5, 3이라는 숫자가 나온 이유를 생각해 본다면
* 5 = 변환하고자 하는 진법의 반 ... (a)
* 3 = ( (2 ^ 저장되는 블럭의 한블럭의 비트 수) - 변환하고자 하는 진법 )/2 ... (b)
* 과 같은 식으로 나온것입니다.
*
* 5 = 10 / 2
* 3 = (2^4 - 10) / 2
*
* 따라서 저 식대로라면 어느 진법에 대해서든 알고리즘을 적용할 수 있습니다.
* 하지만, 홀수 진법에서는 (a)식이나 (b)식이나 모두 0.5가 생깁니다.
* 결과적으로는 홀수 진법일 시에서는, (a)식은 올림, (b)식은 내림 처리합니다.
* 왜 그래야 하는지는 해당 알고리즘 부분에서 다시 설명하겠습니다.
* 여기서 (b)식이 radix_c를 구한 식입니다. (a)식은 radix_b를 오른쪽으로 1 쉬프트 하면 되지만
* (b)식은 조금 복잡하기 때문에 미리 구해놨습니다.
*
* 이제 총 정리입니다.
* 출력을 하는데 있어서 2진수 값을 n진법의 x승 배열에 변환 저장한 후,
* 각 배열에 저장되어 있는 값을 n진법의 x개의 숫자로 쪼개는 식으로 출력을 할 것이며
* 여기서 n진법의 x승 배열에 저장하는 방법은 더블대블 알고리즘을
* 32비트에 최적화, 임의의 진법에도 적용되도록 확장하여 사용한다.
* 여기까지가 총 정리입니다.
* 이제 radix_d만 남았습니다.
* radix_d는 n진법의 x승 배열의 크기를 구하는 식에서부터 도출되었습니다.
* 2진수로 x자리인 수는 10진수로는
* x * log10(2) 의 올림값 자리수만큼이 됩니다.
* 이것을 32비트에 맞춰 생각해보면
* 2진수 32 * x자리인 수는 10진수로
* 32 * lgo10(2) * x자리가 됩니다.
* 여기서 구하고자 하는 것은 10진법 배열의 크기이므로
* 저 숫자를 9로 나누어 줍니다.
* 그러면 (32 * lgo10(2) * x) / 9가 되며
* 이것을 n진법으로 확대하려면 위 식에 log10(n)을 나누어 주면 됩니다.
* 그래서 다음과 같은 식이 나오며
* ( ( 32 * log10(2) ) / ( log10(n) * radix_a[n]) ) * x
* radix_d는 ( 32 * log10(2) ) / ( log10(n) * radix_a[n])을 구하는 식이며
* 나온 값에 10000을 곱하고 올림 처리 하였습니다.
*/
'프로젝트 > 큰수 클래스(Big Numerics)' 카테고리의 다른 글
| [BigInteger - 18] 업데이트 및 수정내용 (0) | 2011.07.14 |
|---|---|
| [BigInteger - 17] 문자열로 입력받기 (0) | 2011.07.14 |
| [BigInteger - 16] 나눗셈(Part 3) (0) | 2011.07.11 |
| [BigInteger - 15] 나눗셈(Part 2) (0) | 2011.07.09 |
| [BigInteger - 14] 나눗셈(Part 1) (0) | 2011.07.08 |
