14장. 루트를 찾아라!

14장. 루트를 찾아라!


언젠가 현장에서 일하면서 제곱근 문제를 풀어야 할 경우가 생겼다. 평소에 수학하고는 담쌓고 지낸터라 막막하기만 했다. 나에게 주어진 임무는
줄자, 산소 절단기, 막연하게 생긴 철판때기 뿐이었다. 이를 이용하여 가로와 세로는 1m이되 가로:세로가 직각이 되는 삼각형 (직각 이등변 삼각형,
equilateral right triangle 인가 ?) 모양으로 철판을 잘라내는 것이었다.

줄자로 대략 1m를 표시하여 쭉 잘라냈다. 앗, 여기서 정확히 90도로 가로:세로를 맞춰줄 수 없었다. 나에게 주어진 것이라곤 줄자와 철판, 절단기
뿐이지 각도기는 없었으며, 더구나 그 철판도 한번 정도 잘라낼 크기 밖에 못되었다. 오래되서 어떻게 해결했는지 기억이 잘 나지 않지만, 여튼
아주 단순한 그걸 해결하려 애먹었던 기억이 있다. 아 각도기를 주고 90도를 맞추라고 하던가...

그 이후로 프로그래밍 하면서 수학, 특히 제곱근이 아주 골칫거리가 될 때가 많았다. 근런데 이건 나만의 문제가 아니라는 걸 수학책 뒤져보면서
알게되었다. 제곱근 (square root), 이 녀석 pi 보다 더 자주 사용되면서 수학에서 막강한 위세를 가진 괴물 정도에 해당한다. 이 녀석이 없으면
삼각함수 (trigonometric function) 계산은 어림도 없다. 그럼에도 불구하고 그리 만만치가 않다.

나는 제곱근을 어떻게 어림잡을 수 (estimate) 있는지 인터넷을 찾아봤다. 그러다가 문득, 예전에 도서관에서 심심풀이로 읽었던 과학 동아
(http://www.donga.com/pdf/donga/200703/02/2007030240A23230107.pdf)의 홍길주식 제곱근 풀이법이 떠올랐다. 홍길주는 "바보가 아니면 얘들도
푼다"고 했듯이, 놀라울 정도로 간단 명료했다. 과학 동아 내용을 인용하면 이렇다:

"홍길주의 풀이법은 간단하다. 먼저 수를 반으로 나누고 나눈값을 1부터 오름차순으로 뺀다. 9의 경우
반으로 나눈 값 4.5에서 1을 빼고, 남은값 3.5에서 2를 빼는 식이다. 그렇게 더는 뺄 수 없을 때 남은
수를 2배한 뒤 그 수가 뺄 수와 같으면 제곱근이라는 것. 3.5에서 2를 빼고 남은수 1.5는 3으로 더는
뺄 수 없고 이를 2배한 3이 빼려는 수 3과 같기 때문에 9의 제곱근은 3이 된다는 것이다. "

하지만, 과학 동아에서 이 글을 잘 읽어보면 몇가지 함정으로 인해 과학이 아닌 소설이 되버렸다.

1. 빼서 1.5가 되었을 때 1.5라는 실수를 자연수로 어떻게 처리할 것인가 ?
2. 더는 뺄 수 없어서 2배했을 때, 만약 빼려는 수와 같지 않으면 어떻게 될 것인가 ?
3. 최종적으로 2배한 값을 빼려는 수와 어떻게 비교할 것인가 ?

비록 엉터리 해석이지만, 이 훌륭한 아이디어를 우리는 코딩해보자.

;================== Hong Kil Ju's Natural Roots ============

.model small
.stack 100h
.data
result dw ?
.code
main proc
  mov ax, @data
  mov ds, ax

  mov ax, 25                ; test value
  mov bx, 1                 ; initial guess
  shr ax, 1                 ; temp = test / 2

L1:
  sub ax, bx                ; temp = temp - guess
  inc bx                    ; guess + 1

  cmp ax, bx                ; if (temp <= guess)
  jbe L2                    ;   result = guess
  jmp L1                    ; else goto L1

L2:
  mov result, bx

exit:
  mov ax, 4C00h
  int 21h
main endp
end main

워낙에 아이디어가 간단해서인지 코드 자체도 별것없다. 다만, 한가지 의심이 갈 만한 부분이라면 왜 guess라는 현재까지 추정된 카운터를 루트라고
단정했는가 ? 이는 자연적인 현상이라고 해야하겠다. 신기하게도 홍길주의 알고리즘에서 카운터가 바로 루트로 인정해도 되는 현상이 일어났다. 즉,
최후에 2를 곱할 필요가 없다는 뜻이며, 단지 확인하려는 수준에 불과하다고 할 수 있다.

홍길주의 알고리즘은 분명 획기적이랄 수 있다. 지금 대부분의 전산에서 루트를 구하는 표준 방식이 뉴턴 방식 (Newton method)인데 이는 많은
나눗셈이 들어가므로 굉장히 속도가 느리다. 그래서 예전에 언급한적 있는 상수를 곱하는 방법과 쉬프트해주는 방법으로 어느 정도 느린 속도를
만회하는 방식을 쓰고 있다. 반면, 홍길주의 알고리즘은 루프 안에서 단지 뺄셈/비교-분기 만으로도 해결이 가능하니 디지털로 잘 융합되면
세상을 놀라게할 만한 획기적인 루트 찾기 알고리즘이랄 수 있다.

근본적으로 루트에서 우리가 필요한 것은 소수점 이하의 값이 아니다. 설령 소수점 이하의 값이라하더라도 정작 더 중요한 것은 정수 자리를 차지한
값이라고 할 수 있다. 3.7 이라는 수에서 3이 중요한가 .7이 중요한가만 생각해봐도 충분히 납득할 것이다. 그런 이유로 디지털에서 가장 왼쪽
비트를 "most significant" bit라고 부르는 것이다.

홍길주의 알고리즘은 아이디어 자체는 분명 획기적이지만 문제는 숫자가 커질 때이다. 어머어마한 큰 수를 다른 어마어마한 큰 수로 나눈다면 여러번
빼는 방식이 어쩔 땐 한번의 나눗셈만 못할 수 있기 때문이다. 그런 이유로 그는 세상을 잘 타고태어났는지 모른다. 이 시점에서 홍길주의 풀이는
뒤로 하고 다른 사람들은 루트를 어떻게 찾으려 했는지 알아보자.

나는 루트의 소숫점 이하를 어떻게 계산하는지 인터넷을 검색하여 몇가지 동영상을 찾을 수 있었다.

http://www.youtube.com/watch?v=XTwx6q1Yspg
http://www.youtube.com/watch?v=TayKw7jaMi8
http://www.youtube.com/watch?v=3i94NWF39nU
http://www.youtube.com/watch?v=GvTFfLGCMV4

이들 동영상을 자세히 보면 반복 나눗셈 (즉, 두 수를 곱하여 뺌)을 하되, 넘지 않는 가장 근접한 곱수 (multiples)를 계속 구해나가는 방식이며,
16비트 레벨에서는 소숫점 4자리가 한계였다. 일명 "박스 테크닉"이라고 부르며, 자릿수가 늘어나면 뺄셈하다가 지치기 딱 좋은 방법임을 알 수
있다. 계산을 해나가는 동안 찾으려는 소숫점 값이 박스에 들어갈 숫자와 같은 점은 주목할 만하다. 다만, 이해가 안가는 점은 십진 나눗셈에선
바로우로 한자리 0 만 내려주면 되는데, 이 계산에선 왜 두자리 00 을 내려주냐는 것이다.

나는 예전에 주판으로 루트를 계산해보려 한 적 있다. 인터넷을 검색하여 주판으로 루트를 계산하는 방법을 찾았지만, 주판을 배운적이 없으면,
오히려 낯설기만 할 것이다 (http://webhome.idirect.com/~totton/soroban/SqRt2/). 주판에서는 나눗셈을 하듯이 곱을 빼가는 방법이며, 위에서
처럼 머리로 (mental) 근접한 곱을 빼가는 방법과 아주 흡사했다.

주판에서 사용한 방법도 위와 아주 근사하며 Root(2)를 구할 경우 02. 00 쌍 (pairs)으로 계산하는 것은 별반 차이가 없다. 주판이 소숫점 이하
자릿수를 더 빠르게 많이 얻어낼 수 있지만, 역시 소수점 이하 자릿수를 많이 구해야할 경우 복잡해지는 것은 마찬가지다. 주판이 뭔지 모르는
사람도 있을 것이므로 주판은 단지 진화를 거부한 과거의 컴퓨팅 방식이라는 것만 기억해두고 원점으로 돌아와 위의 동영상식 해석 방법을 다시
살펴봐야겠다.

이 계산법은 위키 (http://en.wikipedia.org/wiki/Methods_of_computing_square_roots)에 자세히 나와있으며, 예로 Root (2)를 계산한 그림을
인용하면 다음과 같다:

동영상에서 설명한 것과 같은 방식이며, 제곱근 위에 적을 숫자와 계산 중간에 오른쪽 옆에 임시로 구한 결과가 일치함을 알 수 있다. 이상하게도
홍길주 방법에서 카운터를 루트의 값으로 인정하는 것이나 중간에 한 자리씩 답이 나오는 서양식 방법이나 말로 설명하기 힘든 묘한 숫자의 농간이
느껴졌다. 아직까지 루트는 미확인 괴물에 불과하다. 하지만 이 계산법은 알고리즘이랄 수 없다. 왜냐하면 머리로 계산하는 과정 (mental process)
으로 대소를 판정하기 때문이다. 이 시점에서 루트를 찾기 위한 노력은 잠시 중단해야겠다. 실수에 대한 정리가 없는 과정에서 다뤄봤자 부정확한
알고리즘으로 끝나기 때문이다. 실수 (float)에 대해 한바퀴 삥 둘러보고 다시 루트를 찾아 떠나기로 한다.

루트 찾기 링크 : http://en.wikipedia.org/wiki/Category:Root-finding_algorithms