로그의 힘 - Power of Logarithm

고등학교 때 이과를 택한 사람들은 수학 시간에 한번은 log에 대해서 배운다. 여기서는 로그를 계산하는 수학 원리나 계산 방법에 대해서 논의할 생각은 없다. 단지 컴퓨터에서 알고리듬의 성능(Performance)을 측정하는 방법으로서 로그에 대한 이야기를 하려고 한다.

존 네이피어 (John Napier, 1550-1617)

로그 계산법을 최초로 창안한 사람은 스코틀랜드의 존 네이피어이다. 그는 수학자이자 천문학자로서 (지금과 같은 계산기나 컴퓨터가 없던 시기에) 잦은 천문학 계산 작업을 편하게 하기 위하여 로그를 만들었다. 이 원리는 당연히 지수들을 수학적으로 처리하는 논리이지만, 로그라는 log 수식 기호 자체는 발견이라기 보다는 발명에 더 가깝다고 - 개인적으로 - 이해한다.

존 네이피어 동상- 스코틀랜드 National Portait Gallery, (좌),  초상화(우)

 로그의 활용은 매우 광범위하여 아마도 네이피어가 살아서 돌아온다면 본인도 놀랄만큼 수많은 응용분야에서 쓰이고 있다. 화학에서 산과 염기 농도의 등급은 로그를 통해서 표현하고, 물리학에서 소리의 크기를 결정하는 데시블(Decibel) 표현 역시 로그를 통해서 수치를 계산한다.

화학 산 염기 표현 방식

하지만 이 로그가 수학적으로 가장 중요한 기여를 한 부분은 역시 자연 지수 e 값의 존재를 인류가 알게 된 것일 것이다. 이 주제는 몇 권의 책으로 나올 만큼 많은 이야기가 있어서 여기서 다룰 수는 없지만 관심이 있는 사람들에게는 [오일러가 사랑한 수 e] 라는 책을 추천한다. (오래 전에 읽은 책이지만) 수학 이론보다는 관련된 역사와 응용분야에 대한 이야기들이 쉽게 설명되어졌고, e 값과 관련된 많은 흥미로운 이야기들을 접할 수 있다. 

 

현재에도 야전 포병에서 사용되는 초기 방식의 계산 방법

네이피어가 만들어서 천문학 계산에 사용한 처음의 로그 계산 방법은 현재 야전 포병 부대에서도 동일한 원리로 여전히 사용되고 있다. 물론 현대의 자주포와 견인포는 모두 사격 계산기가 있어서 숫자만 입력하면 모든 것이 출력이 된다.

하지만 야전 포병 사격 지휘소의 계산병들은 이러한 계산기가 없는 경우를 위하여 수계산으로 직접 포탄을 사격할 사각(전방을 바라보고 좌우로 준비하는 각도)과 고각(상하로 준비하는 각도)을 100% 연필로 계산하는 훈련을 한다. 이때 이들 각자에게는 아래 그림에서와 같은 로그 대수표 책 한권 씩이 지급되어진다. 

이 대수표 한 권만 있으면 로그값을 구하는 계산기가 필요없이 모든 계산 절차를 가감승제로만 계산을 할 수 있다. 가감승제가 더하기/빼기/곱하기/나누기 인데, 25년 전 기억을 되살리면 곱하기와 나누기도 거의 필요없었던 것 같다.

로그 대수표(좌), 네이피어 테이블의 첫 페이지(우) [1]

나는 사격 지휘 장교로서 계산병들에 비해서 속도는 형편없이 늦다고 매번 비난을 받았지만, 개인적으로 이 계산 작업을 매우 재미있어 했다. 그 계산 절차를 간단히 말하면, (로그 대수 책을 옆에 두고) ① 계산하고 싶은 거리에 해당하는 숫자를 로그표에 해당하는 값을 가지고 와서 더하기 빼기를 하고 난 후, ② 그 결과를 다시 대수표에서 찾아서 원래의 거리 값으로 다시 환원하는 방식이다.

정확하게 이 절차는 네이피어가 천문학 계산을 할 때 무식하게 큰 숫자들의 곱하기를 피하고 대수표를 통해서 쉽게 더하기/빼기 작업으로 환원시킨 원리와 동일하다. 전역 후에도 거리 측량을 하는 기사들을 우연하게 볼 때나 TV에서 바다에서 항해를 하는 배를 보면, 그 배들도 방향과 거리를 지속적으로 수정하기 위해서 로그 계산이 반드시 필요할 것이라는 생각을 종종 하였다. 

 

알고리듬에서 로그 값의 사용

이 로그 값이 알고리듬의 성능을 설명할 때 진가를 발휘하는 가장 큰 이유는 트리 구조 때문이다. 물론 트리 구조가 아닌 다른 방식의 자료 구조들도 있지만 이 트리 구조 때문에 로그를 통해서 성능(Performance)을 설명하는 것이 가장 효율적이게 되었다 (특히 데이터베이스를 설계하는 알고리듬은 거의 대부분이 트리 구조이다).

컴퓨터 알고리듬 과목을 배우기 시작하면 알고리듬의 속도에 따른 성능을 계속 논의하기 위하여 빅오 표현(Big-O Notation) 을 소개 받는다. 사실 이 빅오 라는 표현은 영문 대문자 O 를 가지고 성능을 표현하겠다는 약속이다. 만약 당신에게 100개의 데이타가 순서대로 주어진다면 (1,2,3, ... 100) 이 100의 데이타 숫자만큼 일일이 한번 검색을 할 때 O(100) 만큼 돌아간다고 수식을 표현하기로 약속을 한다.

항상 숫자가 100개가 주어지는 것이 아니라 가변할 수 있으니까 (당연히 컴퓨터에서 100 개의 데이터만 처리하지는 않는다) 일반적으로 N 개가 주어진다고 가정을 하자. 그러면 한번 전체 검색을 할 때 O(N) 이라고 다시 표현을 할 수 있다.

이제 아래 그림과 같이 여러가지 종류의 트리 구조를 바라보면 이들을 로그로 다시 표현할 수 있다(로그를 처음 접하는 사람들은 log 수식이 익숙하기까지는 다소의 연습이 필요하기 때문에, 그 설명을 여기서 하지는 않겠다).

만약 처음 시작하는 뿌리 노드(Root Node)에서 2개씩 새로운 트리의 노드가 나온다면 이는 log ₂N 으로 표현이 되고, 3개씩 나온다면 log₃ N 이 된다. 이 트리의 관점에서 log ₂8 라는 값이 주어질 경우의 해석은 이렇다. 

결론적으로 log ₂8 의 값은 3이고, 이는 8개의 데이타가 주어졌을 때 처음 뿌리 노드에서 마지막 노드까지 찾아가는 횟수가 3번이면 끝난다는 의미이다. (아래 그림 가운데 상단에 있는 트리 구조에서 말한다면 27이라는 수에서 아래 19까지 찾아갈 때 3번만 움직이면 끝난다는 말이다)

구글 이미지 검색에서 나오는 트리 구조 예들

 

이제 실제로 알고리듬이 적용되어야 하는 실제 상황에서 데이타의 수가 천만개 이상이라고 가정을 하면 이제 N과 log N의 차이는 보다 선명해진다. 데이타의 갯수가 지구와 달의 거리만큼 주어지고 이를 미터 단위로 표시하면 대략 384,400,000 미터(384,400 km)이다. 이는 미국 내에서 보스톤에서 LA 로 가는 거리가 4,800,000 미터 (4,800 km) 라고 할 때 대략 80번 곱한 값이다. 

이제 로그를 이용해서 이 데이터를 처리할 수 있다고 하면 지수가 2인 log ₂N 로 계산을 하면 log ₂ (384,400,000) = 28.51 미터가 나오고 지수가 10일 경우는 대략 8.58 미터가 나온다. 이러한 사례는 알고리듬을 짤 때 항상 발생하는 편인데 대략 3억 8천만 개(384,400,000)의 데이터를 처리할 때 좋은 알고리듬으로 처리가 되면 9번이나 29번 이내의 검색 횟수로 결과가 나오지만, 무식하게 전체를 검색할 때는 384,400,000 번을 모두 돌고서야 값이 나온다.

문제는 이렇게 한번만 검색을 돌려야 하는 경우보다는 384,400,000 X 384,400,000과 같이 중복해서 검색해야 하는 경우도 자주 있기 때문에 이런 경우는 아무리 좋은 컴퓨터라 하더라도 상당한 시간을 멈춰 있어야 한다.

지구-달 거리를 로그 값으로 계산한 결과

 

 

[1] 네이피어

www.maa.org/press/periodicals/convergence/logarithms-the-early-history-of-a-familiar-function-john-napier-introduces-logarithms

[]

 

(모든 글은 동의 없이 전체나 부분의 무단 복제를 금지합니다. COPYRIGHT ⓒ 2020 SUNGMIN PARK ALL RIGHTS RESERVED.)