NatNumb CompSystem

자연수 세계 - 서론과 이야기거리 로 돌아가기

q-진법과 연산

우리는 십진법의 연산에 익숙해있기 때문에 십진법이 가장 '쉬운' 계산이라고 생각하기 쉽다. 덧셈이 얼마나 쉬운가, 구구단을 외우고 나면 곱셈은 또 얼마나 쉬운가. 그런데 덧셈 계산이란 어떻게 한다는 것일까? 덧셈과 곱셈을 셈하는 방법은 우리가 아는 방법 말고는 없는 것일까? 컴퓨터는 어떻게 계산할까? 더 나아가 과연 '쉬운 계산'이란 무엇일까? 아니, '계산'이란 도대체 무엇일까? 물음표를 붙여갈수록 답은 그리 간단하지 않다. 이 질문에 대해 우리가 충분히 검토하기는 어렵다. 다만 우리가 하는 덧셈과 곱셈은 '어떤 규칙'에 따라 차례차례 해나가는 무엇이다. 여기서는 익숙한 10진법의 덧셈과 곱셈의 알고리듬을 보고 그것이 사실은 어떤 진법이든 상관없이 통한다는 것만 보기로 하자.

덧셈과 곱셈의 알고리듬

어떤 한 수에 다른 수를 '더해가는' 것을 덧셈이라고 한다. a + b 라 썼다면, 그것은 a 라는 자연수 다시 말해, 하나,하나,하나... 를 a 번 해서, 거기다가 다시 하나, 하나, 하나 b 만큼 보태어 간다는 것을 말한다. 이 과정은 '숫자'로 통역될 때야 비로소 우리 앞에 '보이게' 된다. 따라서 a 를 표현된 숫자에 b 라는 숫자를 더해서 나온 결과인 a + b 가 어떻게 '표현'될까 하는 것은 수의 표현인 '진법'에 따라 다를 수 밖에 없다. 하지만 계산의 구조인 알고리듬은 다르지않다. 예를들어 $15+973$이나 $999+1234$와 같은 수을 더해보면서 어떤 계산과정을 거치는지 차근차근 짚어보라.

10-진법과 2-진법의 덧셈

십진법이라는 통역 프로그램은 덧셈에 대하여 어떻게 작동할까? 가장 익숙한 방법은 알다시피 다음과 같다. 어떤 자연수 u와 v에 대해, u 가 $a_{n}a_{n-1}\cdots a_{1}a_{0}$로 표현되고 v가 $b_{m}b_{m-1}\cdots b_{1}b_{0}$ 이라 해보자. 이때, $n<m$ 라고 가정하자. 다른 경우라도 영향을 주지 않는다.

(step 1)

• $a_{0}+b_{0}$을 연산한 결과가 0 과 9 사이에 있는 경우 :

나온 결과를 맨 끝자리에 쓰고, $a_{1}+b_{1}$을 연산한다.

• $a_{0}+b_{0}$을 연산한 결과가 0 과 9 를 넘어서는 숫자로 표현되어야 하는 경우 :

$a_{0}+b_{0}$에서 1x 로 표현해야 하므로, x 부분만 맨끝자리에 쓰고, 1 을 다음 단계 계산으로 넘겨 $a_{1}+b_{1}+1$ 로 간다.

(step 2)

• 앞 단계의 결과에 따라 $a_{1}+b_{1}$ 또는 $a_{1}+b_{1}+1$ 를 계산한다. 이 때도 두 경우로 갈린다. 십을 넘는 경우와 아닌 경우, 그에 따라 다음 단계로 넘어간다.

(step 3)

• 위 과정을 $a_{n}+b_{n}$ 또는 $a_{n}+b_{n}+1$ 까지 반복한다.
• 그 결과를 $b_{m}b_{m-1}\cdots b_{n+1}$ 또는 $b_{m}b_{m-1}\cdots (b_{n+1}+1)$ 에 덧붙여 쓴다.

어떤 진법에 대해서도 마찬가지라는 것은 쉽게 알 수 있다. 어떤 경우에 '넘겨주기'가 발생하는지만 다를 뿐이다. 2-진법에서는 더한 결과가 0 과 1 로 표현할 수인가 아닌가에 따라, 3-진법의 경우, 0, 1, 2 중에 있는지에 따라 결정하면 된다. 기본 알고그램은 같다.

예를들어 2진법 체계에서 111 + 1010의 덧셈연산을 해보자.

• 제일 오른쪽의 숫자 1 + 0 의 결과가 1 이므로 다음 단계로 넘어간다. (결과 1 오른쪽 0번째 칸에 저장)
• 다음 단계, 1 + 1 의 결과가 0 과 1 로 표현이 안된다. 0과 1 다음 수를 표현한 숫자인 10 이므로 0 을 두고 1 은 다음 단계 계산에 더해준다. (결과 0 오른쪽에서 첫번째 칸에 저장)
• 다음 단계, 1 + 0 계산. 앞 단계에서 1 이 넘어왔으므로 실제로 계산은 (1 + 0) +1 을 계산해야 한다. 결과가 10 이므로 0 을 두고 1 은 다음 단계로 넘긴다. (결과 0을 오른쪽 두번째 칸에 저장)
• 다음 단계, 앞 단계에서 1이 넘어왔으므로 마지막 1 에 1을 더한 결과를 덧붙여 쓴다. (결과 10을 위의 결과에 덧붙여 씀)
• 최종 결과 10001 이라는 기호, 따라서 자연수 십칠.

실제로 111 은 자연수 칠을, 1010은 자연수 십을 표현한 것이기 때문에 그 결과가 틀림없다.

이제 10-진법의 곱셈 과정을 보고 일반적으로 q-진법 곱셈 과정을 유추해보자.

10-진법과 2-진법의 곱셈

처음 산수를 배울 때, 3 + 3 을 할 때면 6 이라고 쉽게 답을 한다. 그러다가 3 + 3 + 3 + 3 이라는 문제에는 머뭇거린 기억이 있는지? (없었다구요?) 그러다 구구단(10진법의 곱셈표)를 '외우고' 나서부터는 쉽게 $3\cdot 4$ 을 마음 속에서 끄집어 내어 "12 요 ! " 라고 자신있게 말할 수 있었다. 그보다 큰 수로 넘어가면서 곱셈과 덧셈이 섞이고 반복해서 나오기 때문에 점점 틀린 답을 낼 가능성은 커진다. 10진법의 곱셈을 할 때 알게 모르게 어떤 단계들을 밟아갔던 것일까? 스스로 27*9와 265*24를 해보면서 추정해보라. 여기서도 u와 v라는 두 자연수의 십진법 표시는 위의 덧셈과 같다고 해보자.

(step 1)

• 먼저 $a_{0}\cdot b_{0}$을 곱셈표에서 찾는다. 실제로는 $a_{0}$ 를 $b_{0}$ 번 더한 것이다. 그 결과는 0 에서 부터 81 사이의 값일 것이다. 그것이 $x_{0}y_{0}$ 라고 하자. '일의 자리 수'인 $y_{0}$ 은 저장하고 $x_{0}$ 을 다음 계산으로 넘긴다.

(step 2)

• $a_{0}\cdot b_{1}$을 곱셈표에서 찾는다. 마찬가지로 0 과 81 사이의 어떤 수가 $x_{1}y_{1}$ 로 표현될 것이다. 여기에 앞단계에서 넘어온 수 $x_{0}$ 를 더한다. 다시 말해 덧셈 $y_{1}+x_{0}$ 을 한다. 어떤 경우는 그 결과가 십보다 작을 것이고 어떤 경우는 10보다 클 것이다.

그 덧셈의 결과가 십 보다 작은 경우 : $x_{1}$ 을 다음 계산으로 넘긴다.

그 덧셈의 결과가 십 보다 클 경우 : $x_{1}+1$ 을 다음 계산으로 넘긴다.

• $a_{0}\cdot b_{m}$ 까지 위 과정을 되풀이하고 결과를 덧붙여 쓰고 저장해둔다.

(step 3)

• 이제부터는 $a_{1}\cdot b_{0}$ 부터 $a_{1}\cdot b_{m}$ 까지 위의 계산을 되풀이해서 결과를 저장한다.

(step 4)

• 위의 과정을 $a_{n}\cdot b_{m}$ 까지 되풀이한다. 을 곱셈표에 따라 연산하고 (step1)에서 '올리기 위해' 저장한 수를 더한다. 그 결과에서 10보다 작은 일의 자리 수만 그대로 두고 10의 자리의 수 $x_{0}$를 저장한다.

(step 5)

• 앞의 결과에서 저장된 결과들을 모두 더한다.

$a_{0}\cdot b_{0}$ 에서 $a_{0}\cdot b_{m}$ 의 결과 더하기,

$a_{1}\cdot b_{0}$ 에서 $a_{1}\cdot b_{m}$ 의 결과 더하기,

...

$a_{n}\cdot b_{0}$ 에서 $a_{n}\cdot b_{m}$ 의 결과.

10-진법의 계산이 그렇듯 일반적인 q-진법에 대해서도 마찬가지 알고리듬이 적용된다. 다만 참고할 곱셈표와 어떤 수일 때 넘겨주기를 할 것인가에 따라 달라진다.

10-진법의 덧셈이나 곱셈의 프로그램을 짰다고 하자. 2-진법, 3-진법, ... , 12-진법, 60-진법이라해도 프로그램을 다시 짜는 게 아니라 그 프로그램의 숫자 몇 개만 바꾸어 주면 될 것이다. 10-진법은 어떤 수와 어떤 수의 곱을 해서 최소 0 에서 최대 81 사이의 값이 나올테니 다음 단계로 올라가는 숫자는 0 부터 8 사이일 것이다. 2 진법의 곱셈을 하면 어떤 경우도 0 과 1 밖에 안나오기 때문에 넘어가는 수는 항상 0 이다. 3 진법의 경우는 2 곱하기 2 의 결과일 때 1 이 올라갈 수 있다. 7 진법의 경우, 0 부터 36까지의 결과가 나오니 올라가는 수는 0 부터 3 중 하나다. 참고할 곱셈표를 미리 만들어두면 편하다. 10-진법을 구구단이라고 부르니, 7-진법에서는 육육단을, 12진법에서는 십일십일단을 참고하면 된다. 만약 인류가 7-진법 체계를 쓰고 있다면 우리는 어려서부터 아래의 곱셈표를 외웠을 것이다. 기호는 0, 1, 2, 3, 4, 5, 6을 쓴다고 하자.

	1	2	3	4	5	6
1	1	2	3	4	5	6
2	2	4	6	11	13	15
3	3	6	12	15	21	42
4	4	11	15	22	26	33
5	5	13	21	26	34	42
6	6	15	42	33	42	51

3-진법 곱셈표(두두단. 또는 둘둘단)와 12-진법의 곱셈표(십이십이단, 또는 열둘열둘단)을 만들어보라.

2-진법 곱셈의 예를 들어보자. 2-진법으로 표현된 111 과 101 을 곱셈을 해보자.

			1	1	1
			1	0	1
			1	1	1
		0	0	0
	1	1	1
1	0	0	0	1	1

2-진법에서 나타내는 숫자 111 은 일곱을, 101 은 다섯을 나타낸다. 따라서 삼십오가 결과로 나와야 하는데, 우리의 결과 100011 은 실제로 삼십오라는 수를 나타내는 기호다.

덧셈과 곱셈 알고리듬은 하나밖에 없을까 ?

덧셈과 곱셈을 할 때 우리가 보통하는 계산 과정을 풀어 써보았다. 그런데 덧셈과 곱셈 알고리듬이 그것 하나만 있을까? 하나만 존재한다면 그것이 하나일 수 밖에 없음을 밝혀야 할 것이다. 그렇지 않다면, 다른 알고리듬이 있다는 것만 보일 수 있다. 과연 어떻게 될까 ? 그리고 어떤 알고리듬이 가장 쉬울까? 컴퓨터로 프로그래밍 해서 같은 컴퓨터에서 돌려본다면 어떤 것이 더 빨리 계산 결과를 줄까?

자연수의 연산을 하는데 있어 10진법은 가장 좋은 체계인가?

10-진법은 2-진법, 3-진법 이나 7-진법보다 기호가 많고 따라서 곱셈표는 더 많아진다. 12-진법, 20-진법은 더할 것이다. 3-진법의 곱셈표를 만들어보면 1*1, 1*2, 2*2 밖에는 외울 것이 없다. 그렇다면 2진법은? 2진법의 곱셈표는 1*1 밖에 없다. 외우고 말 것도 없는 것이다. 위에서 2-진법 체계에서 111*101 곱셈에서 보았듯, 셈이 얼마나 단순한가. 실제로 디지털 컴퓨터가 2-진법을 사용하는데는 하드웨어적인 이유도 있지만, 소프트웨어적인 이유도 있다. 2-진법은 눈에 띄게 계산이 단순하다. 빠르게 계산해낸다. 진법이 낮아질수록 단점은 같은 수를 표현하는데 더 길게 써야한다는 것인데, 이는 메모리 매체가 발달한 현대 컴퓨터에게는 문제가 되지 않는다.

같은 수를 표현하는데 10-진법에 비하여 2진법은 얼마나 더 길까?

그렇다면, 같은 알고리듬을 썼을 때, 12-진법, 10-진법과 7-진법, 2-진법의 곱셈 연산 어떤 것이 더 빨리 결과를 낼까? 컴퓨터로 계산할 때, 같은 자연수를 여러 진법으로 했을 때, 계산 속도나 메모리를 차지하는 정도가 같을까? 어떤 의미에서 계산의 복잡성 정도가 같을까?

지금까지 이야기한 것을 되돌아보면 자연스럽게 이런 질문이 생길 수 있다.

가장 좋은 진법은 어떤 것일까?

물론, 위의 질문은 '가장 좋은' 이라는 말이 모호하기 때문에 아직 분명한 질문은 아니다. 어떤 기준을 정할 것인가에 따라 달라질 수 있다. 곱셈과 덧셈의 연산의 경우 2-진법은 매우 빠르고 틀릴 가능성이 적다. 그렇지만 곱셈과 덧셈의 계산을 빨리한다고 했을 때, 뺄셈과 나눗셈의 계산도 빨라질까? 게다가 자연수 세계를 탐구해가는 과정에서 튀어나오는 수많은 문제들도 있다. q-진법에서 q가 커질수록 우리에게는 어떤 자연수를 표현하기 위해 우리가 정해야 하는 기호는 q만큼 많아진다. 그리고 단위가 올라갈 때마다 새로운 '단어'가 필요하게 된다. 예를들어 10-진법의 경우 0 부터 9까지 열 개의 기호를 가져오고 나면 9가 끝나고 단위가 올라갈 때 '십'이라는 단어를, 99가 끝나고 '백'이라는 단어를, 999가 끝나고 '천'이라는 단어가 새로 추가되는 것이다. 대신 20-진법의 경우 스무개의 기호와 열아홉이라는 자연수를 가리키는 기호 다음에 '이십'을 나타내는 단어가 새로 나와야 할 것이고, '사백'에 해당하는 자연수를 나타내기 위해 '사백'을 뜻하는 단어를 내야할 것이다. 처음 정하는 기호와 새로 운 '단어'들을 합해보자. 다시 말해 0 부터 1000 까지 일 때, 10-진법에서는 10 개 기호와 세 단어니까 총 13개, 20진법에서는 총 22개가 된다.

0 부터 1000 까지 자연수에 대해 2-진법부터 15-진법까지 보았을 때, 어떤 진법이 '가장 적은 개수의 기호+단어'를 가지게 될까? (WIM, 영어판, 9쪽.)

관절뼈로 센다함은 요렇게...

12-진법은 1, 2, 3, 4, 6, 12로 인수가 많고 그 중에는 가장 기초적인 소수인 2, 3 이 들어있다. 20 이하의 진법에서는 다른 진법보다 풍요롭고 좋은(?) 수로 잘 쪼개진다. 따라서 나눗셈에서 특히 강력하다. 12-진법 연산이 단순하고 좋은 시스템이라 이것을 받아들이자고 주장하는 사람들도 있다. 12-진법은 오랫동안 써왔고 지금도 그 흔적이 곳곳에 남아있다. 시계를 보라. 12시간, 24시간(하루), 12 개월 (1년, 약 360일). 그리고 연필 한 타스(dozen). D-Day 이전의 영국화폐에는 12 진법의 흔적이 남아있었다.

10-진법은 사실 사람들이 세어 가기 편하다. 보통 양 손의 손가락을 굽히면서 센다. 그렇다면 12-진법은 ? 더 쉽다. 한 손만 쓰면 된다. 엄지손가락 하나를 빼고 나머지 네손가락의 관절뼈로 세어간다. 이 열두개를 다섯번 하면 60 이 된다. 우리 옛 선조들도 이 방법을 써서 60 갑자를 추정하고 해와 달을 계산하였다고 한다. 지금도 주역으로 점을 보는 사람들 사람들은 엄지손가락으로 나머지 손가락들을 토닥거리고 있다.

자연수 세계 - 서론과 이야기거리 로 돌아가기

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia