Skeptic.Cynical() : 컴퓨터로 곱셈을 해보자.

2008년 03월 16일

컴퓨터로 곱셈을 하는 법을 정말 피지컬하게...-_- 아차 요즘 학교를 다니다보니 교수의 말투를 써버렸네요. 물리적인 부분부터 들어가서 곱셈 한번 해보려고 합니다. 잘 알려면 쉽게 설명할 줄 알아야죠. 읽으실 때 잘 모르는 영문이나 문자나 기호는 그냥 지나치셔도 됩니다.

시작합니다.

컴퓨터라는 기계는 전기를 사용합니다. 일단 정보를 표시하는 기본적인 아이디어를 생각해보겠습니다.

1. 모든 정보는 숫자로 표현 가능합니다. 즉 A는 숫자 65라고 합시다. B는 66으로 하죠. 띄어쓰기는 32라고 합시다. 0에서 255까지를 두고 이것저것 배열합니다. 알파벳도 넣고 기호도 넣고 하는 식으로 표를 하나 만듭니다. 그래서 65 66 32 65 라고 치면 "AB A"가 됩니다.

2. 십진수의 숫자를 이진수로 표현 가능합니다. 즉 65는 이진수 1000001 로 표현가능하군요. 그렇다면 66은 1000010 으로 표현 가능하겠네요. 32는 100000 이네요. 보기 쉽게 전부 8자리로 맞춰서 앞에 0을 붙여주면 아까 말했던 65 66 32 65는

01000001 01000010 00100000 01000001

이라고 쓰면 되겠네요.

3. 0은 없는 것, 1은 있는 것으로 표현 가능합니다. 마찬가지로 0은 안하는 것, 1은 하는 것으로 표현 가능하겠네요.

4. 여기서 전기를 쓰면 쉽게 조절 가능하므로 1볼트보다 낮으면 0으로 생각하고 3볼트보다 높으면 1로 생각할 수 있겠군요.

자 여기까지 전기로 정보를 표현해봤습니다. 즉 정보는 숫자로 표현 가능합니다.

이제 숫자를 가지고 더하거나 빼거나 하고 싶어집니다. 그러기 위해서는 전기를 원하는 부분을 0볼트로 만들었다가 아니면 3볼트로 만들었다가 하는 식의 조작을 할 수 있어야합니다. 여기서 트렌지스터가 나오는군요. (요즘은 IC, 옛날에는 진공관) 트렌지스터를 잘 연결하면 원하는 식으로 0이나 1로 조작할 수 있습니다. 밑에 그림을 봅시다. 자세하게 볼 건 없고 설명만 보면 됩니다.

위 그림의 하단은 트랜지스터 연결에 대한 회로도 입니다. 그러니깐 컴퓨터나 TV같은 제품에 들어있는 녹색의 기판에 꼽힌 요상한 칩들의 연결을 나타낸 것이라고 보면 됩니다. 그리고 그림 상단은 그림 하단의 입력값과 결과값만을 요약해서 표시한 그림입니다. 0과 1로만 입력을 받아서 각 입력값에 따라서 다른 결과를 나타내는군요.

1. 위 그림의 상단에 요약된 그림을 뭉뚱그려서 게이트라고 합니다. 저런 게이트는 물론 위 그림의 하단에 보이는 회로도처럼 녹색 기판에 꼽힌 작은 회로들의 집합입니다. 즉 게이트는 녹색기판으로 바꾸어 생각할 수 있습니다.

2. 게이트를 이용하면 0과 1이라는 숫자를 조작할 수 있음을 알았습니다. 이를태면 1과 1이 입력되면 0을 내놓거나 하는 식으로 말입니다.

3. 게이트를 잘 배치하면 정보를 저장할 수 있는 배치가 가능합니다. 1이나 0을 저장할 수 있지요. 다시 말하면 "넌 이제부터 1이다"라고 하면 그걸 기억하고 있는다는 뜻입니다. 중간에 "지금부터 넌 0이야"라고 하면 그때부터 0을 기억합니다. 아래 그림처럼 배치하면 전기를 공급하는 동안 정보가 저장됩니다. (안 봐도 됩니다.)

(안 읽어도 되는 대충 설명: 1bit를 저장하는 저런 회로를 flip-flop이라고 합니다. 위 그림에서 D는 생각하지 마시고 나머지를 보시면 됩니다. 위에서 NAND라는 게이트가 어떤 식으로 결과를 내는지 보셨을 겁니다. 초기값이 A=1, B=1, C=0 일 때 A값에 잠시 전원을 끊었다가 붙여주면 C가 1이 되는 상태로 유지됩니다. 즉 정보가 저장됩니다. 마찬가지로 B를 잠시 0으로 했다가 다시 1로 하면 C는 다시 0이 되는 상태로 유지됩니다.)

4. 게이트를 잘 배치하면 더하기, 빼기가 가능합니다. 녹색 기판에 칩들을 잘 배열해서 말입니다. (자세한건 생략 -_-)

5. 게이트를 잘 배치하면 2로 곱하거나 나누는 것이 가능합니다. 이건 쉽습니다. 만약 65가 있다면 2로 나누면 32가 됩니다.(나머지는 버리고) 이걸 이진수로 표현하면

01000001 : 65(10진수)
00100000 : 32(10진수)

눈치 채셨나요? 우측으로 한 칸 옮겼습니다. 그러면 2로 나누는 연산이 됩니다. 하지만 1의 자리에 있던 1이 사라졌네요. 하지만 나머지를 버렸을 뿐이지 결과는 맞습니다. 마찬가지로 곱셈도 가능합니다.

00100001 : 33(10진수)
01000010 : 66(10진수)

좌측으로 한 칸씩 밀어낸 뒤 1의 자리에는 0을 넣었습니다. 그랬더니 딱 2를 곱한 값이 되는군요. 참 쉽죠? -_-;

여기까지 이해하셨으면 우리는 녹색 판에 트랜지스터인지 뭔지 하는 작은 칩들을 이리 연결하고 저리 연결해서 전기를 흘려보내주면 원하는 정보를 저장하거나 더하거나 빼거나 2로 곱하거나 2로 나눌 수 있다는 사실을 알았습니다.

이제 곱하기를 해보겠습니다.

이 방법(알고리즘)은 a la russe 라고 하는 방법입니다.

1. 곱하고 싶은 2개의 숫자를 써놓습니다.
2. 첫 번째 숫자가 홀수라면 가장 우측에 두 번째 숫자를 써놓습니다.
3. 첫 번째 숫자는 2로 나눕니다.(나머지는 버립니다.) 두 번째 숫자는 2로 곱합니다.
4. 3번의 결과에서 첫 번째 숫자가 홀수라면 우측에 두 번째 숫자를 써놓습니다.
5. 이렇게 3-4번의 과정을 1이 나올 때 까지 반복합니다.
6. 우측에 써놨던 모든 숫자를 다 더합니다. 그러면 두 수의 곱과 같습니다.

이런 식으로 곱셈을 합니다. 물론 25를 16번 더하는 식으로도 가능하지만 이 방법에는 장점이 있습니다. 그게 뭐냐면 이제 그림의 하단에 2진수로 써둔 것을 봅시다.

그림에 나온 2진수는 위의 25와 16과 같은 수입니다. 잘 보시면 아시겠지만 2로 나누는 것은 그냥 우측으로 옮기는 과정이고(물론 넘어가는 숫자는 그냥 지워버립니다.) 2로 곱하는 것은 그냥 좌측으로 전부 옮기고 0을 추가하면 끝입니다. 게다가 홀수인지 판별하는 법은 2진수의 1의 자리 숫자가 1인지 0인지만 판단하면 됩니다. 따라서

1. 숫자 2개를 저장해둔다. 그리고 결과값을 저장할 공간을 0으로 만든다.
2. 첫 번째 2진수의 1의 자리가 1이면(즉 홀수이면) 두 번째 숫자를 결과값에 더한다.
3. 첫 번째 숫자를 죄다 우측으로 밀고(즉 2로 나누고) 두 번째 숫자를 죄다 좌측으로 민다.(즉 2를 곱하고)
4. 2와3번을 반복한다.
5. 첫 번째 숫자가 사라지면 멈춘다.

이러면 곱한 값이 나오게 되겠죠. 전기로 곱셈을 해보셨습니다.
집적회로(IC)나 CPU 따위를 보고 뉴스 등에서 트랜지스터 몇 개를 처넣었네 하는데 그게 이 소리입니다. 이해가 가셨는지.

PS_사실은 a la russe만 설명하려고 했는데. -_-; 뭐 이리 길어졌는지... 아무튼 a la russe의 아이디어는 웬만한 책에 다 나오지만 처음보고 놀랬던 기억이 납니다. 컴퓨터의 회로, 즉 녹색 기판 따위가 처리하기 쉬운 수준의 알고리즘이었거든요. 강력하고 아름답죠.

# by 시노조스 | 2008/03/16 05:41 | Computer | 트랙백 | 덧글(5)

트랙백 주소 : http://sino.egloos.com/tb/3662463
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]