sin 1°의 정체

sin 1°는 어떤 무리수일까?

답부터 말하자면, sin 1도는 일반적인 통념과는 달리 초월수가 아니다. 이는 임의의 정수 각도도 마찬가지이다.
유한 번의 사칙연산과 거듭제곱/제곱근으로 표현 가능한 대수적 수라는 뜻이다. (사실, π나 e 같은 초월수도 사칙연산· 거듭제곱· 근호의 꼴로 나타낼 수 있다. 단지 그게 무한히 반복되는 급수의 형태가 될 뿐이지..)

삼각함수는 삼각형을 이루는 두 변의 각도가 이러할 때 변의 길이를 비율이 어떻게 되는지를 나타내는 함수이다. 기하학에서는 그야말로 필수 중의 필수 도구이지만, 대수적으로는 직관적이지 않은 굉장히 기괴한 특성을 많이 지닌다. 그래서 학교에서 수포자를 양산하는 원흉이기도 하다.

삼각함수에다 일반 자연수나 유리수를 집어넣으면, 지수나 로그함수와 마찬가지로 우리가 의미를 알 수 없는 괴랄한 초월수가 함수값으로 튀어나온다. 그러나 pi의 유리수 n배 내지 1/n배에 속하는 각도에 대해서는 꼭 그렇지만은 않다. 이미 입력값인 pi부터가 대수적이지 않은 괴랄한 수여서 그런 게 아닐까 싶다.

먼저, 특수한 각도에 대해서는 함수값이 깔끔한 수 내지 심지어 유리수 범위로 떨어질 때가 있다. 특히 15 내지 30도 간격인 0, 30, 45, 60, 90도일 때 sin 값은 각각 sqrt(n)/2 (n은 0 이상 4 이하)로 딱 떨어진다. 가장 단순한 형태다.

여기에서 파생된 각, 다시 말해 레퍼런스 각의 n배나 절반, 1/3 따위에 해당하는 각은 위대하신 삼각함수의 덧셈 정리를 통해 cos/sin 값을 구할 수 있다. 덧셈 정리라는 게 당연히 대수적인 조작들만 있으므로 대수적인 수에 대수적인 조작을 하면 그 수도 대수적인 것은 당연지사. 정수 계수 대수방정식의 근이 될 수 있다.

그리고 15도 단위 계열뿐만 아니라 18도 단위에 계열에 대해서도 삼각함수는 비교적 간단한 형태의 값이 나온다. 세배각 공식이어서 원래는 3차 방정식을 풀어야 하지만 이 각도는 그나마 1차식과 2차식으로 인수분해되는 경우이기 때문이다.

사용자 삽입 이미지

이를 이용하면, 18도와 15도의 차인 sin 3도까지도 약간 복잡하지만 답이 나온다. (그림: 영문 위키백과)

사용자 삽입 이미지

하지만 정수 도에서 그나마 해피한 결과가 나오는 정밀도의 한계는 여기까지.
sin 1도 정도가 되면 유한한 사칙과 거듭제곱, 근호만으로 정확한 값을 묘사하는 게 불가능하지는 않으나 의미가 없어진다.
반복되는 패턴에 대한 매크로 치환을 하고도 항이 열몇 개에 달할 정도로, 정말 미치도록 복잡한 형태가 되기 때문이다.

3도 간격의 수로부터 1도 단위의 삼각함수 값을 구하려면 아까 18도의 경우처럼 각을 3등분을 해야 하는데 이제는 인수분해가 되지 않는다
얄짤없이 3차 방정식이 되며(삼각함수의 3배각 공식은 3차식!), 작도 불가능한 것으로도 잘 알려져 있다. 복잡함이란 본질적으로 이런 데서 유래되는 게 아닌가 싶다. 그냥 내 감이 그렇다는 뜻.

3차 방정식의 근의 공식은... 2차 방정식의 그것하고는 비교조차 할 수 없을 정도로 머리 터지게 복잡하다. 그래서 3차 방정식의 근인 sin 1도의 값도 끔찍하게 복잡한 형태로 산출되는 것이다.

* 끝으로 보너스.
arctan 1 + arctan 2 + arctan 3 = pi 임을 증명하시오.

arctan 1이야 45도의 특성상 pi/4가 되는 게 잘 알려져 있다만, 저런 관계는 도대체 어떻게 성립하는 걸까?
세 각도의 합이 180도라는 뜻이므로, 기울기가 1, 2, 3인 세 각은 일정 비율의 닮은 삼각형을 결정하는 각이 될 수 있음을 보이면 되겠다.

삼각형의 두 꼭지점의 각의 기울기(=탄젠트)가 x, y라면, 나머지 꼭지점의 각도는 기울기가 1/x인 각과 1/y인 각 두 개의 합으로 표현된다. (나머지 꼭지점에서 맞은편 변으로 수선을 내려 보면 직관적으로 이해됨)

그런데 삼각함수의 덧셈법칙에 따라
tan(a+b) = (tan(a)+tan(b)) / (1 - tan(a)*tan(b))
이므로.. 이 공식으로 두 탄젠트를 합성하면, 나머지 꼭지점의 탄젠트는

(y+x)/(x*y-1)로 표현될 수 있다.

x,y에 1,2를 넣으면 저 값은 3이 되고, 2,3을 넣으면 값은 1이, 1,3을 넣으면 값은 2가 된다. 사실, 식의 특성상 (x,y)->z만 성립하면 (x,z)->y와 (y,z)->x는 일일이 체크하지 않아도 자동으로 성립하긴 한다.
따라서 어떤 경우든 기울기가 1, 2, 3인 세 각은 닮은 삼각형을 결정하는 각이며, 그 합은 삼각형의 내각의 합인 180도, 즉 pi임을 알 수 있다.
내가 생각하는 것보다 더 간단하게 증명하는 방법도 물론 있을 것이다.

Posted by 사무엘

2013/12/31 08:30 2013/12/31 08:30
,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/915

행렬 기초 이야기

a*x + b*y + M = 0
c*x + d*y + N = 0

이라는 두 개의 이원(x, y) 일차방정식이 있다고 치자. 흔히 연립방정식이라고도 불린다.
이 방정식을 풀려면 x, y 중 하나의 계수를 a나 c, 아니면 b나 d로 맞춰 줘서 한 변수를 소거해야 한다. 그래서 일원 일차방정식으로 바꿔서 반대편 변수의 근을 구한 뒤, 그 값을 대입하여 원래 변수의 근까지 구하면 된다.

이를 일반화하여 위의 방정식의 '근의 공식'을 구하면 다음과 같다. 뭔가 규칙성이 있는 것 같으면서도 미묘하게 잘 안 외워진다.

x = (N*b-M*d) / (a*d-b*c)
y = (N*a-M*c) / (a*d-b*c)

분모를 보니 생각나는 게 없는가?
그렇다. 이것은

[ a b ]
[ c d ]

라는 원소로 구성된 2*2 정방행렬의 행렬식을 구하는 공식이다.
이 행렬식의 값이 0이라는 건 a:b와 c:d의 비율이 동일하다는 뜻이다. 따라서 이 행렬을 구성하는 벡터들은 서로 일차(선형) 독립을 이루지 못하며, 상수항이 어떻냐에 따라서 이 방정식은 근이 무수히 많거나 근이 존재하지 않게 된다.

이런 행렬을 거친 일차변환은 2차원 평면을 1차원 선이나 점으로 찌그러뜨린다. 이런 행렬은 영벡터(모든 원소의 값이 0)가 아닌 벡터 중에서도 자신과의 곱을 영벡터로 만드는 물건이 무수히 존재하게 된다(Ax=O).
예를 들어 연립방정식 x+2*y = 0 과 3*x+5*y = 0의 근은 x와 y가 모두 0인 trivial solution 단 하나밖에 없으나, x+2*y = 0과 3*x+6*y = 0은 두 식이 동치나 마찬가지이기 때문에 x = -2*y이기만 하면(가령 2와 -1) 식이 성립한다. non-trivial solution들이 존재한다는 뜻이다. 결국, 근이 무수히 많을 수 있다는 말과 본질적으로 동일하다.

이들은 모두 필요충분조건 관계에 있으며, 이외에도 이런 행렬의 엄밀한 특성에 대해서는 선형대수학 시간에 많이 배우게 된다.

말이 길어졌는데, 그럼 변수가 세 개 이상이 되면 근을 구하는 양상이 어떻게 바뀔까?
그야말로 폭발적으로 복잡해진다.

변수가 2개일 때는 x, y 근에 최대 두 변수의 곱(최대 2차)으로 이뤄진 항이 분자와 분모에 2개씩 있었다.
그러나 3개일 때는 세 변수의 곱으로 이뤄진 항이 분자와 분모에 6개씩 들어간다.
그리고 이를 일반화하면, n원 1차 연립방정식의 근은 n개의 변수의 곱으로 이뤄진 항이 분자와 분모에 무려 n! (팩토리얼)개씩 들어간다!
이것이 '폭발적'이라는 단어의 의미이다. 예를 들어,

[ a b c ]
[ d e f ]
[ g h i ]

라는 3*3 정방행렬의 행렬식은 다음과 같다. 어떤 규칙성이 있는지, 어떻게 하면 잘 외울 수 있겠는지 한번 생각해 보시라.;;

a*e*i - a*f*h - b*d*i + b*f*g + c*d*h - c*e*g

a가 속한 행과 열을 제낀 2*2 행렬(e f / h i)의 행렬식에다가 a를 곱해서 더하고,
다음으로 b가 속한 행과 열을 제낀 2*2 행렬(d f / g i)의 행렬식에다가 b를 곱해서 빼고,
끝으로 c가 속한 행과 열을 제낀 2*2 행렬(d e / g h)의 행렬식에다가 c를 곱해서 더하면.. 이 행렬 전체의 행렬식이 나오긴 한다. 2*2 행렬식이 2개의 항으로 구성돼 있는데 그런 식이 3개가 늘어나니 총 6개가 되는 게 맞다.

이런 방식으로 행렬을 쪼개면 그 어떤 크기의 행렬의 행렬식도 구할 수는 있다. 하지만 크기가 3을 넘어가는 행렬에 대해 행렬식 내지 방정식을 푸는 일반적인 공식을 구하려는 생각은 포기하는 게 좋다. 머리 터진다..;;

참고로 1변수 n차 방정식의 경우를 생각해 보자. 2차 방정식은 잘 알다시피 비교적 외우기 쉬운 근의 공식이 존재하는 반면 3차와 4차는 근의 공식이 있기는 하나 인간의 머리로 도저히 외울 수 없을 수 없을 정도로 미치도록 복잡한 형태이다. 게다가 서로 인접한 차수끼리 규칙성 같은 것도 아예 존재하지 않는다. 5차 이상부터는 대수적인 방법만으론 깔끔하게 풀 수조차 없다.
그에 반해 n변수 1차 연립방정식은 비록 그 정도로 카오틱하게 복잡한 건 아니지만, 그래도 좀 다른 양상으로 복잡해진다는 게 오묘한 점이다.

그리고, 이건 일반적인 공식을 구하려 할 때 딸려 나오는 식이 지수함수 급으로 복잡해진다는 소리다. 일반적인 경우가 아니라 그때 그때 특정 숫자가 주어진 행렬의 행렬식을 구하는 알고리즘의 시간 복잡도가 지수함수라거나 NP 완전 문제 급이라는 뜻은 아니다. 둘은 서로 다른 개념이다.

변수가 3개를 넘어가는 방정식은 어떻게 풀어야 할까?
가령, 변수가 x, y, z라고 치면 일단 모든 방정식의 x의 계수를 1이든, 맨 위의 식의 계수로든 어쨌든 하나로 일치시켜야 한다. “등식에서 같은 수를 더하거나 빼도 등식은 성립한다.” / “등식에서 같은 수를 곱해도 등식은 성립한다” 라고.. 초등학교 산수 시간에 배우는 지극히 당연하고 기본적인 원리를 이용해서 방정식을 푸는 것이다.

그렇게 해서 x 변수를 없는 놈 취급할 수 있게 만든 뒤, 다음 방정식에 대해서 y 변수의 계수를 일치시킨다.
이런 절차를 반복하여 변수를 z만 남겨서 z 값을 구하고, 다음으로 y, x의 순으로 재귀적으로 근을 구하면 된다.
행렬이라는 물건 자체가 이런 연립방정식을 푸는 동작을 간략하게 모델링하는 과정에서 고안되었다.
앞서 말한 절차를 행렬 용어로 표현하자면, 가우스-조던 소거법으로 행렬을 대각화하는 것과 같다.

행렬이 대각화가 되고 나면 방정식을 다 푼 것이나 다름없을 뿐만 아니라, 행렬식의 값은 그 행렬의 대각선 원소들의 곱으로 쉽게 구할 수 있게 된다.
행렬을 대각화하는 데 드는 시간 복잡도는 일반적으로 O(n^3)으로, 행렬 곱셈의 비용과 같다.
이 작업을 숫자를 대상으로 곧장 곧장 업데이트하는 게 아니라, 기호를 이용해서 일반적인 경우를 다 고려하여 표현하려다 보면 항 개수가 아까 같은 팩토리얼 급으로 증가하게 되는 것일 뿐이다.

연립방정식 하니까 응용수학 내지 산업/경영공학 같은 데서 다루는 그 이름도 유명한 선형 계획법(LP)이 생각난다.
이런 데서 다루는 문제는 대체로 변수의 개수가 식의 개수보다 더 많고, 식도 등식이 아니라 부등식이다. 애초에 해 자체는 무한히 많을 수밖에 없는데 그래프의 능선을 따라다니면서 주어진 조건을 최대한 만족하는 영역을 찾는 게 목적이다. 이런 문제는 실용적인 가치도 무진장 높다.

이런 걸 푸는 제일 간단한 알고리즘으로는 simplex method가 있는데, 그 이상의 디테일은 본인도 비전공자인 관계로 잘 모른다. 변수의 차원이 최대 2차원 정도일 때나 그래프를 그려서 생각할 수 있지, 이 역시 3차원 이상으로 가면 머리에 쥐 난다. 고등학교에서 행렬을 2*2까지밖에 다루지 않는 것, 그리고 전산학에서 간단한 bool 대수 연산을 다룰 때 변수를 3개까지밖에 넣지 않는 게 다 이유가 있어서 그런 것이다.

Posted by 사무엘

2013/10/26 19:25 2013/10/26 19:25
,
Response
No Trackback , No Comment
RSS :
http://moogi.new21.org/tc/rss/response/891

퇴근길에 문득 든 아주 기초 수학 생각이다.
아래 그림은 포물선 2개 x^2+2*x (x=-2..0), -x^2+2*x (x=0..2)와, sin(x*PI/2) (x=-2..2)를 한데 포개 놓은 것이다.
원래 sin, cos 부류의 삼각함수는 주기가 2*PI인데, 이를 4로 좁혀 놓았다.
이렇게 보니까 포물선도 싸인파 곡선과 형태가 생각보다 꽤 비슷해질 수 있다는 걸 느꼈다.

사용자 삽입 이미지

0부터 2까지 구간의 넓이를 정적분으로 구해 보면 이차함수인 포물선의 면적은 4/3인 반면, 진짜 싸인파의 면적은 4/PI이다. 즉, 포물선에 속하는 면적이 약간 더 크다.

그러나 이 두 곡선은 비슷하게 생겨도 그 본질은 굉장히 다르다. 미분을 해 보면 안다. 이들의 도함수를 그래프로 그리면 다음과 같다.

사용자 삽입 이미지

싸인파는 도함수도 기준 위치와 진폭만 다를 뿐, 여전히 전구간이 미분 가능한 매끄러운 싸인파이다.
그러나 두 포물선을 인위적으로 연결한 함수는 도함수가 직선으로 바뀌었고, x=0 지점은 연속이긴 하지만 기울기의 좌극한과 우극한의 값이 서로 달라서 미분이 불가능한 점이 되었다. 마치 절대값이 들어있는 일차함수처럼 된 셈이다.

이걸 또 미분하면 어떻게 될까?
싸인파는 역시 또 싸인파이지만 저 직선은 아예 양수 아니면 음수의 상수함수로 바뀌고, x=0 지점은 이제 연속이지도 않게 된다. 마치 인간이 만든 아무리 매끄럽고 뾰족한 바늘도 확대하고 또 확대해서 보면 울퉁불퉁한 표면이 드러나듯이 말이다.

우리가 자연에서 흔히 볼 수 있는 물체의 운동 양상은 관성에 의한 등속 직선, 아니면 힘을 한 쪽으로 균일하게 받는 포물선 형태가 있다. 하지만 출렁이는 물결이나 음파 같은 진동은 삼각함수에 속하는 싸인파가 자연스러운 움직임이다. 오히려, 포물선 두 개를 갖다붙인 것에 불과해서 미분하면 딱딱한 절대값 직선으로 바뀌어 버리는 곡선이야말로 인위적이고 부자연스러운 형태인 것이다.

왜 싸인파가 자연스러운 움직임일까?
삼각함수는 무한소나 무한대로 발산하지 않고 주기를 갖고 -1에서 1 사이를 한없이 진동만 한다.
그러면서도 전구간이 단절 없이 연속이고 미분 가능하다. 미분을 해도 심지어 도함수조차 형태를 바꾸면서 주기적으로 자기 자신으로 돌아오기를 반복하기 때문이다.
내가 수학적인 통찰력이 부족해서 그 원리를 다 '이해'와 '실감'은 못 하겠지만, 적어도 이런 함수는 돼야 정말 매끄러움의 본질을 수학적으로 표현한 게 아닌가 하는 막연한 추측까지는 한다.

해석학적으로 볼 때 x^n의 x에 관한 미분은 n*x^(n-1)로 떨어진다. 지수함수 exp는 알다시피 (1/ n!)*x^n의 무한합으로 정의되어, x에 대해 미분하더라도 예전항이 바로 다음항의 미분 결과와 같은 꼴이 되는 형태이다.

그런데, 삼각함수인 sin과 cos는 exp를 홀수승 항과 짝수승 항으로 분할함과 동시에 각 항의 부호를 또 +, -로 교대로 오고 가게 바꾼 형태이다. 그래서 함수가 무한대나 무한소로 발산하지 않고 진동하게 된다. 신기하기 그지없다.

미적분학을 공부하면 삼각함수와 더불어 쌍곡선함수라는 물건도 배우게 된다.
얘는 sin과 cos에다가 h를 붙여서 sinh, cosh처럼 쓰는데, 지수함수를 이루는 무한급수에서 각각 홀수승항과 짝수승항만 쪼개서 취한 함수이다. 삼각함수와의 차이는 부호 스위칭이 없다는 점이 전부다.

그래서 쌍곡선함수는 비록 그래프의 모양은 삼각함수와 완전히 다르지만 삼각함수와 굉장히 비슷한 특성을 갖게 된다. sinh와 cosh는 미분하면 부호 스위칭이 없이 서로 상대편으로만 탈바꿈하며, 삼각함수의 덧셈정리와 비슷한 특성도 가진다. 삼각함수가 cos(x)^2 + sin(x)^2 = 1이듯이 cosh(x)^2 - sinh(x)^2 = 1이다. 전자가 원스럽다면 후자는 정말 쌍곡선스러운 형태이지 않은가?

쌍곡선함수는 사실상 수학 해석학적인 의미 때문에나 배우지, 삼각함수에 비해 실생활에서 유용한 구석은 별로 없는 것 같다. 그러나 얘도 자연에서 의외로 중요한 곳에서 자주 볼 수 있다. cosh가 바로 현수선의 방정식을 나타내는 함수이기 때문이다.

현수선이란 밀도가 균일한 줄이 자기 길이보다 짧은 간격으로 양 끝이 어떤 중력장 안에 매달렸을 때, 자신의 무게로 인해 중력의 방향(아래)으로 축 늘어짐으로써 형성되는 선을 말한다.
이것도 포물선과 비슷해 보여서 혼동되기 쉽지만, 포물선하고는 수학적인 성질이 완전히 다르다. 현수선은 증가의 폭이 이차함수가 아니라 지수함수와 같은 스케일이다.

알고 보면 아치도 포물선이 아니라 현수선을 뒤집은 모양이다. 현수선 모양으로 구조물을 건설하는 게 모양이 역학적으로 가장 안정적으로 형성된다고 한다.
왜 현수선이 cosh 함수의 형태로 형성되는지 수학적으로 증명하려면 물리학, 미적분학 등 여러 방면의 이론이 동원돼야 하지 않을까 싶다.

어찌 보면 당연한 말이지만, 현수선은 일부만 잘라 내도 그 모양이 그대로 유지된다. 다시 말해 U자 모양으로 된 현수선의 양 끝의 일부를 잘라내서 u부분만 잡고 있더라도 기존 부위가 받는 힘은 변함없으며, 그 구간의 선 모양이 바뀌지 않는다는 뜻이다.

삼각함수와 쌍곡선함수가 각자 자기 분야에서 포물선과는 다른 매끄러움, 출렁거림 등을 표현하고 있다는 게 경이롭다.
자연 현상으로부터 얻은 물리량이라는 게 태생적으로 연속적인 데이터의 형태이다 보니, 물리학의 발전을 위해서는 수학, 특히 미적분학의 발전이 반드시 선행되어야 했다는 게 느껴진다.

Posted by 사무엘

2013/10/05 08:27 2013/10/05 08:27
, , , , , ,
Response
No Trackback , 5 Comments
RSS :
http://moogi.new21.org/tc/rss/response/884

수학에서 행렬은 굉장히 흥미로운 물건이다.
행렬끼리의 덧셈이나 행렬의 상수배는 어려울 게 없는 쉬운 연산이지만, 행렬끼리의 곱셈은 그렇지 않다. 행렬 A와 B사이의 곱셈은 A의 가로 크기와 B의 세로 크기가 같아야 정의되며, 새로 생기는 행렬의 크기(dimension)는 반대로 B의 가로 크기와 A의 세로 크기로 결정된다.

이런 특성상 행렬의 크기는 세로, 즉 row부터 먼저 써 주는 게 직관적이다. 세로 x줄 가로 y줄짜리 x,y 행렬과 y,z 행렬의 곱은 x,z 크기가 된다고 표기가 가능하기 때문이다.

또한, 앞에 있는 행렬과 뒤에 있는 행렬이 원소가 서로 연산되는 방향이 다르기 때문에 행렬의 곱셈은 교환 법칙이 성립하지 않는다. A×B가 일반적으로 B×A와 같지 않다는 뜻. 그러나 결합 법칙은 성립한다. (A×B)×C와 A×(B×C)는 동일하므로, 같은 방향만 유지하면 아무 순서로나 행렬을 곱해 줘도 된다.

그래서 이것과 관련하여 흥미로운 문제가 하나 있다.
크기가 들쭉날쭉 다르지만 순서대로 곱셈은 가능한(= 인접한 행렬끼리는 앞 행렬의 가로 크기와 뒤 행렬의 세로 크기가 일치) N개의 행렬들이 있다. 우리는 이들을 모두 최소의 계산량만으로 곱하고 싶다.

역행렬이나 행렬식 값을 구하는 비용에 비할 바는 아니겠지만 행렬의 곱셈은 꽤 비싼 연산이다. 일반적으로 x,y 크기와 y,z 크기의 행렬을 곱하는 데는 원소들간에 x*y*z회의 곱셈이 필요하다. n 크기의 정사각행렬의 경우 이는 n^3으로 귀착된다. (뭐, 분할 정복법을 활용하여 n^2.x승으로 줄이는 복잡한 알고리즘이 있긴 하지만 이것은 초기 준비 오버헤드가 굉장히 크기 때문에 행렬이 무진장 클 때에나 의미가 있다.)

예를 들어 A는 4*2 크기, B는 2*3 크기, C는 3*1크기의 행렬/벡터라고 치자.
이것을 A*B*C 순으로 진짜 순서대로만 곱하면 A*B를 곱하는 데 4*2*3=24회의 곱셈이 동원되고, 그 결과물인 4*3 행렬을 C와 곱하느라 12회의 곱셈이 필요해서 계산량은 총 36이 된다.

사용자 삽입 이미지

그러나 B*C부터 먼저 곱한 뒤 A를 거기에다 곱하면 열수가 적은 C 덕분에 B*C는 겨우 6회 만으로 끝나고, 거기에다 4*2*1=8회의 곱셈이 추가되어 총 14의 계산량만으로 A*B*C를 구할 수 있다. 답은 결국 똑같은데도 (AB)C보다 A(BC)가 훨씬 더 나은 전략인 것이다.

신기하지 않은가? 그래서 이런 configuration을 일반화하여 {4, 2, 3, 1}이라고 표현하고, 더 나아가 n>=3인 n개의 자연수라고 치자.
이 입력에 대해서 최소 곱셈 횟수와 실제 곱셈 순서를 구하는 것이 문제이다.

정올 공부를 한 분이라면 아시겠지만, 이것은 다이나믹 프로그래밍, 혹은 동적 계획법이라는 알고리즘 설계 방법론을 학습하면서 예시로 다뤄지는 아주 기본 문제이다. 다이나믹 프로그래밍은 다음과 같은 경우에 유용하다.

  • 전체 구간에 대한 최적해가 부분 구간의 최적해에다가 추가 연산을 함으로써 구하는 게 가능하다.
  • 그리고 한번 답을 구해 놓은 부분 구간의 최적해는 더 바뀌지 않는다는 게 보장된다.

이 행렬의 곱셈 문제에서 가장 작은 구간은 3이며, 이때의 답은 그냥 두 말할 나위 없이 세 정수의 곱이다.
그리고 전체 구간 [1..n]에 대해서 최적해는 바로..

  • 1을 [2..n]과 곱했을 때의 계산량 (맨 앞의 행렬과 나머지)
  • [1..n-1] 과 n을 곱했을 때의 계산량 (앞의 행렬들과 맨 뒤의 행렬)

중 더 작은 놈이라고 간주하면 된다.

그럼 [2..n]과 [1..n-1]은? 각 구간에 대해서 또 동일한 해법을 적용하여 재귀적으로 구간을 계속 쪼개 나가는 것이다. 언제까지? 구간의 길이가 3이 될 때까지 말이다.
이렇듯, 다이나믹 프로그래밍은 재귀성을 띠고 있다. 이것은 수학적으로는 점화식으로 표현되며, 코드로는...

const int dat[]={4,2,3,1,2,6,5,8,3,2}; //배열

int GetMin(int f, int t)
{
    int i=t-f, j;
    if(i<3) return 0; //should not reach here
    else if(i==3) return dat[f]*dat[f+1]*dat[f+2]; //obvious case
    else {
        //사실은 i가 3인 경우도 이 조건의 특수한 케이스라고 간주할 수 있다.
        //단지 GetMin값이 0이고, t-2와 f+1이 동일한 값이 될 뿐이다.
        i=GetMin(f,t-1) + dat[f]*dat[t-2]*dat[t-1]; //(A*B)*C
        j=GetMin(f+1,t) + dat[f]*dat[f+1]*dat[t-1]; //A*(B*C)
        return i<j ? i:j;
    }
}

int answer = GetMin(0, 10);

과연 이렇게 하면 답이 구해질까?
프로그램을 돌려 보면, 10개의 정수로 표현된 9개의 서로 다른 크기의 행렬들의 곱은..
146회의 곱셈만으로 계산이 가능하다고 나온다.

구체적인 계산 순서는 이러하다.

4 (2 (3 (((((1 2 6) 5) 8) 3) 2)))

이 경우, 각 단계별 계산 순서는 다음과 같이 되기 때문에,

x y z x*y*z
1 2 6 12
1 6 5 30
1 5 8 40
1 8 3 24
1 3 2 6
3 1 2 6
2 3 2 12
4 2 2 16

곱을 전부 합하면 진짜로 146이 맞다!
참고로, 이런 전략을 쓰지 않고 진짜 FM대로 앞에서부터 뒤로 행렬을 순서대로만 곱하면 계산량은 최적해의 세 배를 넘는 492에 달한다.
이것이 바로 알고리즘이 만들어 내는 차이이다.

다이나믹 프로그래밍에는 반드시 수반되어야 하는 작업이 있다. 바로 예전에 구했던 구간 계산값들을 배열에다 저장해 두는 것이다. 그렇게 하지 않으면, 마치 피보나치 수열을 f(x) = f(x-1)+f(x-2)라고만 구현하는 것만큼이나 계산량이 n이 커짐에 따라 기하급수적으로 커지게 된다. 그것도 예전에 한번 했던 똑같은 계산을 매번 반복하느라 말이다.
그래서 이 방법을 사용한 알고리즘은 대체로 시간 복잡도와 공간 복잡도가 모두 O(n^2)이 된다. 시간 복잡도가 지수함수에서 그래도 다항함수로 바뀐다.

구간별로 최적해 자체뿐만이 아니라 구간 분할을 어떻게 했는지에 대한 정보도 따로 보관해 놓으면 아까와 같은 구체적인 계산 순서도 그 정보를 추적함으로써 구할 수 있다.

정올에서 다이나믹 프로그래밍의 중요성은.. 두 말하면 잔소리이다.
본인은 20세기에 정올 공부를 한 세대인지라 그 시절의 문제밖에 기억을 못 한다만..

1997년 한국 정보 올림피아드의 고등부 3번인 벽장 문제는 최적해를 구하고자 할 경우 공간과 시간 복잡도가 O(n^3)인 다이나믹 프로그래밍으로 풀 수 있다. 이 때문에, 16비트 환경임을 감안하더라도 이 문제는 입력의 범위가 작다. 벽장의 개수와 벽장 사용 순서가 최대 겨우 20까지밖에 안 올라가는 소규모이다. 실용적인 상황에서는 이런 부류의 시뮬레이션 문제는 휴리스틱이 동원되어야 할 것이다.

이 외에,

1999년 고등부 1번 검은 점 흰 점 연결,
2000년 고등부 1번 수열 축소

도 다이나믹으로 푸는 문제이다.
국제 정보 올림피아드의 기출 문제 중에는
10회(1998)의 둘째 날 마지막 문제인 폴리곤 게임,
11회(1999)의 첫째 날 첫 문제인 꽃 진열이 기억에 남는다. 특히 꽃 진열은 상당히 기초적인 다이나믹 프로그래밍 문제로, <날개셋> 타자연습의 문장 정확도 측정도 이와 거의 같은 발상의 알고리즘을 사용하고 있다.

난 이 바닥은 손 놓은 지가 너무 오래 돼서 기억이 가물가물하다.
정보 올림피아드에서 경시와 공모는 마치 과학과 공학, 어학과 문학의 차이와 비슷한 것 같다.

Posted by 사무엘

2013/08/14 08:34 2013/08/14 08:34
, ,
Response
No Trackback , 8 Comments
RSS :
http://moogi.new21.org/tc/rss/response/866

두 벡터의 내각을 이등분하기

원점 O에서 시작하는 벡터 A, B가 있다. 그런데 A와 B가 형성하는 내각을 이등분하는 중앙을 지나는 벡터 C를 구하려면 어떡하면 좋을까? 각도를 결정하는 방향만 정확하게 나오면 되며, 길이가 어떻게 되는지는 신경 쓰지 않아도 된다.

사용자 삽입 이미지

단순히 벡터 A와 B를 더하기만 해서는 내각을 정확하게 이등분할 수 없다는 것을 알 수 있다.
더하기만 해서 얻은 벡터는 삼각형 OAB의 '무게중심'을 지나게 된다.
그러나 내각을 이등분하는 벡터는 삼각형 OAB의 '내심'을 지나게 해야 하기 때문이다.

이 문제는 의외로 어렵지 않다.
선분 AB의 위에 있는 점 C를 설정하되, 선분 OA: OB의 길이의 비와 선분 AC: BC의 길이의 비가 일치하는 지점 C를 찾으면 된다. 그러면 원점에서 시작하는 벡터 C가 바로 벡터 A와 B의 내각을 이등분하는 벡터가 된다.

그렇게 되는 이유를 해석학적으로 따져 보면 다음과 같다.

위의 그림에서 점 A의 좌표는 (1, tan α)이고 B의 좌표는 (1, tan(α+2β) )이다.
그리고 선분 OA의 길이는 피타고라스의 정리에 따라 sqrt(1 + (tan α)^2)이요, 선분 OB의 길이는 더 복잡한 sqrt(1 + (tan (α+2β))^2)가 되는데..

이 둘의 비율이 AC와 BC의 길이의 비와 같다는 뜻이다. AC와 BC는 각각 (tan α+β - tan α), (tan α+2β - tan α+β)로 표현될 것이다.
한쪽은 탄젠트값의 제곱에다가 제곱근이 나오고, 다른 한쪽은 제곱 연산은 없지만 서로 다른 탄젠트 함수의 뺄셈이 나온다. 언뜻 보기에 둘은 서로 비슷한 구석을 찾을 수 없다. 그렇다면 이들이 비율이 서로 일치한다는 걸 어떻게 보일 수 있을까?

사용자 삽입 이미지

여기서 탄젠트 제곱과 제곱근을 쉽게 정리하는 방법이 있다. tan x = sin x / cos x이므로, 1을 분모와 분자가 모두 cos^2 x 인 분수로 간주하여 1 + tan^2 x는 (cos^2 x + sin^2 x)/cos^2 x라고 볼 수 있다.
그럼 분자는 얼씨구나 1로 약분된다. 근호 안에는 1/cos^2 x밖에 남지 않으니, 전체 식은 단순히 1/cos x로 줄어든다.

비례식에서 내항과 외항의 곱은 같아야 하므로, 내항의 곱을 분자에, 외항의 곱을 분모에다 얹은 분수를 설정해 보겠다. 이 수의 값이 1이면 목적이 달성되는 것이므로 어느 걸 분자에, 어느 걸 분모에 얹을지는 그리 중요하지 않다.
식에서는 α+2β, α+β, α라는 세 종류의 각이 쓰이는데, 일단 시각적인 혼동을 줄이기 위해서 앞의 두 아이템을 이제부터는 각각 A, B라는 매크로로 치환하였다.

사용자 삽입 이미지

이제 예전보다 문제가 꽤 단순해졌다.
분자와 분모가 또 분수로 구성되어 있는데, 이것을 통분하는 방법은 간단하다. 분자와 분모에 모두 똑같이 cos A cos B cos α를 한꺼번에 곱해 주면 된다.
그러면 각 분자와 분모에 이중으로 분모로 남아 있던 cos α나 cos A는 약분되어 없어지고, tan 함수도 내부적으로 갖고 있던 cos 나눗셈이 약분되면서 sin으로 바뀐다. 그리고 약분되지 않은 변수에 속하는 cos만이 남는다.

사용자 삽입 이미지

그 뒤의 절차는 일사천리이다.
sin 함수와 cos 함수의 곱이 규칙적인 패턴으로 남는데, 이것은 딱 정확하게 sin(x-y) 꼴로 정리가 된다.
그리고 이제야 매크로 A, B를 원래의 각으로 전개해 보면, A-B와 B-α의 각은 애초에 같은 값이었다는 것을 알 수 있다. 따라서 분자와 분모는 동치이고 원래의 비례식도 항등식으로서 성립한다는 게 밝혀진다.

뭔가 당연한 사실을 필요 이상으로 너무 복잡하게 파헤친 거라는 느낌이 든다. =_=
삼각함수, 벡터 이런 쪽은 컴퓨터에서 기하를 다루는 데 없어서는 안 될 마법과 같은 도구임이 분명하다.

Posted by 사무엘

2013/07/07 08:32 2013/07/07 08:32
, ,
Response
No Trackback , a comment
RSS :
http://moogi.new21.org/tc/rss/response/851

숫자 드립 + 기타

10 이하의 소수(prime number)인 2, 3, 5, 7을 소재로 수집한 여러 잡생각들이다.

※ 2

짝수 중에 유일한 소수라는 점에서 큰 의미를 가지며, 2진법 정도면 0과 1, 같고 다름을 분별할 수 있는 최소한의 숫자 체계가 성립하기 때문에 2는 이산수학과 전산학에서 매우 큰 의미를 갖는다. 그 분야에서는 2가 로그 함수의 밑(base)으로도 즐겨 쓰인다. 이분법, 흑백 논리, 음양설 등의 사상적 근간이 되는 수라는 것은 덤.

2가 지니는 전통적인 의미는 위와 같은데, 2010년대부터 한국에서는 모 스타크래프트 프로게이머 때문에 '콩라인'이라는 의미로 2가 매우 유명해지기도 했다.
또한, 본인이 특별히 주목하는 2의 특성으로는,

  • 태양계의 행성 중 태양에서 둘째로 가까운 금성만이 유일하게 짙은 이산화탄소가 가득한 끔찍한 불지옥이다. 그것도, 지구와 가장 가깝고 지구 다음으로 생명체가 살기에 가장 적합할 수도 있었을 행성이 말이다.
  • 성경의 창세기 1장을 보면, 창조 기간 중 둘째 날에만 “하나님 보시기에 좋았더라”라는 말이 없다.
  • 서울 지하철 중 2호선만이 유일하게 순환선이며, 낡은 플랩식 전광판이 2010년까지 가장 늦게까지 남아 있었다.
  • 주찬양 선교단의 과거 앨범 중 2집만이 구성이 특이했으며, 10주년 기념 음반에는 1~7집 중 유일하게 2집의 곡만 단 한 곡도 수록되어 있지 않다.

이러한 징크스도 있다.

※ 3

삼위일체라든가 영-혼-몸 같은 개념 때문에, 3은 성경과 기독교의 관점에서 상당히 친근하고 긍정적인 수이다.

세상에는 '3요소'라는 특성으로 이뤄진 것들이 무척 많다. 우리가 사는 공간이 가로-세로-높이의 3차원이고, 시각 정보를 구성하는 색상 역시 RGB든 그 어떤 형태로든 3요소로 분할된다는 건 우리에게 시사하는 바가 매우 크다.
거기에다 인간의 언어의 음운조차도 크게 세 부분으로 이뤄져서 한글이 초· 중· 종성의 세벌식으로 구성된 것은 덤이다. 어쩌면 삼라만상이 어딜 가든 개념적으로 3으로 가득한 걸지도 모른다.

또한 컴퓨터 소프트웨어도 허접한 버전 1이 처음 나왔다가 과도기인 2를 거친 후, 제 3의 메이저 버전에 와서야 후대에까지 이어지는 뼈대가 완전히 정착된 경우가 적지 않다.
마이크로소프트 Windows는 3.0부터가 상업적으로 성공한 버전인 건 잘 알려진 사실이거니와, 국산 소프트웨어 중에서도 안 철수 씨의 바이러스 백신은 Vaccine III에서 유래된 V3이라는 브랜드가 정착한 것이다.

본인이 개발한 <날개셋> 한글 입력기도 에디팅 엔진과 기본적인 파일 구성, 그리고 각종 클래스 구조의 뼈대는 2004년에 완성된 3.0에서야 정착했으며, 그 여파로 인해 커널의 파일 이름도 ngs3.dll이다. 또한 최 정한 씨가 과거에 개발했던 셸 유틸리티인 MDIR도 정식 명칭은 MDIR-III이다.

※ 5

사람의 손가락과 발가락이 5개 단위이기 때문에 이 수는 우리에게 아주 친숙하다. 약수가 더 많아서 더 유용한 8이나 12가 아니라, 10이 기수법의 기준으로(10진법) 전세계에 보편적으로 통용되게 된 것은 전적으로 이것 때문이다.

그에 반해 손· 발가락이 5개보다 더 많아서 6개 정도 되는 건 전형적인 기형(다지증) 내지 괴물의 상징으로 간주되었다. 성경에도 고대에 손· 발가락이 6개인 거인 괴물 혈통이 있었다는 기록이 전해지며(삼하 21:20; 대상 20:6), 로스웰 추락 UFO 외계인 시체 해부 동영상에도 문제의 외계인의 사지엔 가락이 6개 달려 있다.
(비록 그 동영상은 훗날 낚시 자작극으로 판명이 됐지만, 1947년에 일어난 로스웰 사건 자체는 존재를 부정하기 어려운 듯하다. 그 자작극을 꾸미고 외계인 세트를 만든 사람도, 외계인이니까 손발가락을 5개가 아니라 일부러 6개로 설정했다는 것에 주목할 필요가 있다.)

5에서 수학적으로 더욱 큼직한 의미가 들어있다. 하필 5차 방정식부터가 대수적인 방법으로 일반해를 구하는 게 불가능하다는 것. 쉽게 말해 근의 공식 같은 만능 공식이 있을 수가 없다는 뜻이다.
3차나 4차의 경우, 비록 2차 방정식의 근의 공식 따위와는 비교도 못 할 정도로 복잡하고 어려운 형태이긴 하지만 근의 공식이 있긴 하다. 왜 5차부터 그마저 원천적으로 안 되는 걸까?

유한한 횟수의 사칙연산과 거듭제곱/제곱근의 묶음만으로는 표현할 수 없는 수가 방정식의 근으로 튀어나올 수 있기 때문이다. 근의 공식이 사용하는 연산 수단의 범위 자체를 넘어서는 수가 대수방정식의 근이 될 수 있다는 뜻이다. 그러면서도 정의상 초월수는 아니다. 흠..

예를 들어, 5차보다 한 차원 더 높은 6차 방정식 x^6+x^2-7=0 의 근 중 하나는 다음과 같다.

사용자 삽입 이미지

식은 정말 간단한 형태이지만 근은 가히 미치도록 복잡한 형태이지 않은가? 사람 손으로 계산하기란 거의 불가능한 경지임을 알 수 있다. 그래도 이 수의 6제곱과 2제곱을 더하면 딱 정확하게 7이 나오긴 한다. 이건 그나마 대수적인 범위에 근이 존재하는 사례이다.

그런데 이런 형태로 나오지 않는 근은 도대체 정체가 뭘까?
이걸 제대로 증명하고 이해하려면 군론을 비롯해 온갖 추상적이고 복잡하고 어려운 수학 이론을 동원해야 하며, 나도 거기까지는 잘 모른다. 다만, 초간단한 방정식 x^n=1만을 생각해 보자. 이 방정식의 근은 드 무아브르의 공식에 따라 복소평면에서 원점이 중심이고 반지름이 1인 원에 내접하는 정n각형의 꼭지점을 이루고 있다.

그러므로 180/n도 중, cos/sin값이 대수적인 수로 딱 떨어지지 않는 각도라면, 응당 대수적인 방법으로 나타낼 수 없는 근이 존재하게 된다고 대략 짐작 정도는 할 수 있을 것이다. 가령, n=7인 정칠각형 같은 것 말이다. 그리고 x^n=1부터가 그러하니, 다른 낮은 차수의 계수까지 섞이면 7차가 아닌 5차에서부터 다항식 기반 방정식의 복잡도가 안드로메다로 치솟는가 보다. 나의 수학 감각으로는 이해력이 여기까지가 한계이다.

그런데 어째 수학 패키지들은 그런 복잡한 방정식에 대해서도 근을 numerical한 방법으로 그것도 실수뿐만이 아니라 복소수 범위에서까지 다 찾아 주며, 5차 이상의 방정식이라도 대수적인 방법으로 근을 구할 수 있는 형태라면 아까의 예에서 본 것처럼 근사값이 아니라 symbolic하게 정확한 근을 찾아 주기까지 한다. 도대체 무슨 귀신같은 수치해석 알고리즘을 썼는지 모르겠다.

※ 7

열 손가락 안에 드는 수 중에서 가장 큰 소수인 7은 역수를 10진법으로 나타냈을 때 꽤 긴 순환소수가 등장하는 최초의 수이다. (0.142857...)
정다각형 중에서도 정칠각형은 3~6이나 심지어 8, 10에 비해서는 정말 듣보잡이다. 5는 그래도 황금비하고라도 관련이 있고 작도도 가능한데 반해, 7은 생긴 모습이 안정적이거나 예쁜 구석이 도무지 없고, 수학적으로 작도가 불가능한 최초의 정다각형이다. 자동차의 바퀴를 봐도 휠너트가 7개가 달린 경우는 전혀 없다.

그럼에도 불구하고 현실에서 7의 존재감이 가장 분명하게 나타나 있는 분야는 크게 두 곳인데, 한 주가 전세계 공통으로 7일이라는 점, 그리고 음악에서 한 옥타브의 음계가 하필 7음으로 구성된다는 점이다.

더 나아가 성경에서 숫자의 쓰임에 대해 면밀히 연구해 본 일부 사람들은, 하나님은 이런 불편하고 괴상한 숫자인 7을 무척 좋아하며, 내부적으로 7진법을 사용하시는 게 분명하다고 주장한다. 그래서인지 성경의 책들 중에서도 특히 요한계시록은 온통 7패턴으로 넘쳐나는 책이지 않던가. 무지개의 색깔이 관습상 7개로 분류되고 7이 웬지 행운의 숫자로 여겨지는 게 완전 터무니없는 엉뚱한 심상은 아니라는 뜻 되겠다.

여호수아기에서 여리고 성을 함락시키는 작전을 보면 이스라엘 백성은 6일 동안은 성을 한 바퀴 돌고, 일곱째 날에는 성을 일곱 바퀴 돈 뒤에 함성을 질렀는데 성이 무너졌다(수 6). 그와 비슷한 맥락으로, 계시록에서는 일곱 개의 봉인이 열리는데 마지막 봉인이 열리자 일곱 나팔이 나오고, 마지막 나팔 타이밍 때 재앙이 담긴 일곱 병.. 이런 식으로 이벤트가 꼬리에 꼬리를 잇는다.

과거에 스탈린 휘하의 구소련은 1930년대에 달력에서부터 종교색을 완전히 걷어내겠다는 의도로 독자적인 달력과 1주 5~6요일 체계를 사용한 적이 있었다. 그러나 그 시도는 오래 가지 못하고 실패했다. 7의 존재감은 아무래도 우리가 이제 와서 부정할 수 없을 정도로 깊숙히 파고든 게 분명하다.

※ 기타

1. 5차 방정식 얘기가 기왕 나왔으니 말인데, 수학에서 이런 식의 미지의 영역은 방정식 근 찾기뿐만 아니라 적분에도 있다. 미분은 합성함수나 곱에 대한 미분이 general하게 정립이 돼 있기 때문에 어떤 함수든 미분하기는 쉬운 편이다. 그러나 적분은 그렇지 않다. 부분적분은 말 그대로 식의 형태를 치환 같은 다른 적분 테크닉을 적용하기 유리한 형태로 변형하는 것일 뿐이기 때문에 만능이 아니다.

위키백과에 예가 제시되어 있듯, x^x, exp(-x^2), sin(x)/x, 1/ln(x) 같은 함수들은 부정적분이 어떤 특성을 갖는 함수인지 기존 초월함수들의 조합만으로는 형태가 기술이 되지 않는다.

까짓거 조립은 분해의 역순이고, 적분은 미분의 역순이 아닌가 하는 생각이 들지도 모르나, 수학의 세계는 그렇지 않은 모양이다. 마치 1/x를 적분했더니 ln x(+C)라는 완전히 생소한 함수가 튀어나온 것처럼, 미지의 발상의 전환이 필요한 듯하다.

2. 과학은 창조론과 진화론, 그리고 심지어 천동설-_-과 지동설 같은 이슈 때문에 종교계와 충돌할 거리가 있었다. 하지만 수학은?
“그래도 지구는 돈다.”도 아니고, “그래도 루트 2는 무리수이다.”, “그래도 파이는 초월수이다” 이런 것 때문에 교황청으로부터 무슨 수학자가 박해 받았다거나 하는 역사는 내가 알기로 없다.
설마 대하 4:2 같은 구절을 들고서 원주율은 3이라고 드립을 쳤다거나 하지는 않았을 테니 말이다. -_-;; 그럴 거면 차라리 H2O가 산소라고 드립을 치는 게 낫겠다. ㅋㅋㅋ

Posted by 사무엘

2012/10/19 08:21 2012/10/19 08:21
, , , ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/745

우리는 학교에서 산수를 배우면서 덧셈을 가장 먼저 배우고, 그 뒤 이들을 묶은 형태인 곱셈을 배운다. 그리고 나중에는 곱셈을 묶은 거듭제곱이라는 걸 배운다. 그런데 덧셈이나 곱셈과는 달리, 거듭제곱은 같은 수를 곱하기를 반복한다는 직관적인 정의만 적용해서는 정수가 아닌 형태의 거듭제곱을 생각하기가 쉽지 않다.

지수법칙이 있으니 유리수 승까지는 그래도 괜찮다. 정수 승과 정수 제곱근으로 설명이 가능하기 때문이다. 하지만 이를 초월하여 2^sqrt(2)처럼 임의의 실수 승은 어떻게 해야 계산하고 표현할 수 있을까?

거듭제곱을 모든 실수 범위에서 정의함으로써 지수함수라 불리는 연속인 함수의 형태로 영역을 확장하는 데는, '연속'이라는 개념에서 알 수 있듯, 미분의 도입이 큰 기여를 했다. 자연상수 e가 발견되고 로그 함수라는 게 생기면서 지수함수는 로그의 역함수로서 정체성을 확립하게 되었다.

이 글에서 수학적으로 엄밀한 디테일을 다 말할 수는 없지만, e는 임의의 수에다 제곱근을 반복하면서 지수가 0에 가까워지고 원래 수가 1에 한없이 가까워질 때 그 수의 소숫점, 다시 말해 숫자에서 1을 뺀 값이 지수와 어떤 비례 관계가 있는지를 규명하는 과정에서 발견되었다. (1+1/n)^n에서 n의 무한대 극한이라는 원론적인 정의가 바로 거기서 유래되었으며, 사실, (1+x/n)^n라고 해 주면 그냥 exp(x)를 바로 구할 수 있다.

exp(x)는 0인 지점에서 기울기가 1이다. 그리고 미분해도 도함수가 자기 자신과 같다는 매우 중요한 특징이 있다. 즉, y=exp(x)에 있는 점 (x, y)의 기울기는 곧 y라는 뜻. 그럼 이놈의 역함수는 어떻게 될까? 본디 함수와 그 역함수는 y=x에 대해 대칭이므로, 점 (y, x)의 기울기는 곧 1/y여야 한다.

미분하면 1/x가 되는 함수를 찾아보니 다름아닌 ln x이다. 복잡한 거듭제곱을 곱셈으로, 곱셈은 덧셈으로 바꿀 수 있는 놀라운 함수 말이다. 그래서 exp는 로그의 역함수인 고로 그 정체가 e^x인 지수함수라는 결론이 도출되고, 그래서 로그와 지수의 함수 관계가 완성될 수 있었다.

a^b = e^(b ln a)이다. ln a^b는 b ln a이므로 양변에 자연로그를 씌우면 아주 자연스럽게 유도 가능하다.

또한 굳이 밑이 e가 아닌 임의의 a인 로그를 생각하더라도, log[a] b = ln b / ln a이다. 이것은 지수보다는 약간 연상이 쉽지 않을지 모르나, 이 경우를 생각해 보자. 로그의 정의상 당연히 a^(log[a] b) = b이다. 이 식 자체에다가 자연로그를 씌우면 log[a] b * ln a = ln b가 되고, 그 후의 논리 전개는 생략. ㄲㄲ

이건 굉장히 유용한 특징이다. 이 덕분에 exp와 ln만 있으면 우리는 임의의 지수의 값도 구할 수 있고, 임의의 로그의 값도 구할 수 있게 된다.
그럼 이 함수의 값을 실제로 컴퓨터로 어떻게 계산하면 좋을까?

이걸 연구하는 분야는 기호, 순수함, 추상성만을 좋아하는 전통적인 수학에서 벗어나 일면 '지저분한 이단아'처럼 보일 수도 있는 수치해석 쪽으로 가게 된다. 컴퓨터에서 exp, ln, cos, sin 같은 기초적인 초월함수의 값을 조금이라도 더 빠르고 정확하게 구하는 기법은 이미 천재 컴덕후, 수학자, 공학자들이 연구할 대로 다 연구해서 소프트웨어 정도가 아니라 아예 하드웨어에 회로에 다 코딩되어 있을 정도이다.

그러니 내가 거기에 뭔가를 더 기여할 게 있다고 여겨지지는 않는다. 단지 본인은 핵심적인 아이디어만 직접 짜 보고 넘어갈 생각이다.
초월함수들의 근사값을 계산하는 아이디어도 미분에서 유래되었다. 단순히 1차함수 접선을 구하는 것을 넘어서 곡선과 가장 가까운 n차 근사 다항식을 구하는 것으로 생각을 확장하면 '테일러 근사 다항식'이라는 걸 구할 수 있고, 무한히 미분 가능한 함수에 대해서는 무한합인 그 이름도 유명한 테일러 급수라는 걸 유도할 수 있다.

* 이말년 씨리즈와 Taylor series는 서로 느껴지는 포스가 확 다르다. 흠.;;;

exp(x)는 예전에도 글로 썼듯이, 원론적인 정의를 이용해서 값을 구할 리는 절대 없고, 테일러 급수를 쓴다. 아래의 코드는 16항 정도까지 계산했다.

double pseudo_exp(double x)
{
    double v=1.0, p=x,q=1.0;
    for(int i=1; i<=16; i++, v+=p/q, p*=x, q*=i);
    return v;
}

단, 이 급수는 x=0인 지점을 기준으로 구한 것이기 때문에 x가 8~9 정도만 넘어가도 오차가 상당히 커진다. 하지만 컴퓨터 부동소숫점에도 한계가 있으니 항을 한없이 많이 계산할 수도 없는 노릇이고, 큰 수에 대해서는 다른 방법으로 보정이 필요할 듯하다.

한편, 로그는 어떻게 구할까?
자연로그도 다음과 같은 직관적인 형태의 테일러 급수가 있긴 하다.

ln (1+x) = x (+-) x^n/n (n이 짝수일 때는 빼기, 홀수일 때는 더하기)

그런데 이 급수는 x가 -1 초과 1 미만일 때만 유효하고, 따라서 0과 2 사이의 로그값만 구할 수 있다. 나머지 범위는 항을 제아무리 많이 계산해 줘도 아예 원천적으로 원함수와 전혀 일치하지 않게 된다. 테일러 급수가 모든 범위에 대해서 무조건 만능은 아님을 알 수 있다.

하지만 지수함수와는 달리 로그는 ln ab = ln a + ln b라고 큰 숫자를 한없이 쪼개는 마법과 같은 공식이 있다. 그러므로 저것만 있어도 아무 수의 로그라도 구할 수 있다.

즉, ln 2의 값을 미리 갖고 있다가 임의의 수에 대해서 2보다 작아질 때까지 ln 2를 따로 더하면서 계속 2로 나누면 된다. 2는 잘 알다시피 2진법을 쓰는 컴퓨터가 좋아하는 수이기도 하고 말이다. 그래서 주어진 수가 2 이하의 범위에 들어오면 그때 급수를 써서 최종적으로 구한 로그값을 또 더하면 된다.

double pseudo_ln(double x)
{
    #define LN_2  0.693147180559945
    double v=0;
    while(x>2.0) x/=2.0, v+=LN_2;

    double x_min1 = x-1, xm = x_min1;
    for(int i=1; i<=16; i++, xm*=x_min1)
    if(i&1) v+=xm/i; else v-=xm/i;
    return v;
}

단, 이 급수의 아쉬운 점은 x가 0이나 2라는 양 극단에 가까워질 때 정확도가 꽤 크게 떨어진다는 점이다. 이는 계산하는 항의 수를 충분히 크게 잡아도 쉽게 극복되지 않는다.

그래서 성능면에서 실용적인 가치는 별로-_- 없지만, ln이 exp의 역함수라는 점을 이용하여, 기존 exp 함수로부터 방정식 근 찾기 기법을 이용하여 로그를 구하는 방법도 이 기회에 실습하게 되었다. 그게 없으면 무엇보다도 초기에 정확하게 값이 구해진 채 공급되어야 하는 LN_2 내장값은 또 어떻게 구하겠는가?

일변수 방정식의 근을 찾는 기법은 수치해석 교재에서 가장 먼저 다뤄지는 기초 주제이다.
exp(x)는 기복이 없으며 그래프 모양이 워낙 예쁘고 원천적이기-_- 때문에, 근이 존재하는 초기 구간만 잡아 주면, 어떤 근 찾기 알고리즘을 쓰더라도 근을 구할 수는 있다. 단지 얼마나 빨리 수렴하여 구해 내느냐가 문제일 뿐이다. 애초에 지수 함수 정도면 범용적인 방정식 근 찾기 알고리즘이 과분하게 느껴질 정도로 특징이 너무 분명하기도 하고 말이다.

가장 먼저 나오는 것은 이분법(bisect)이다. 이게 자료구조에서는 이분법이라고 하면 이분 검색처럼 log n 시간 만에 문제를 푸는 효율적인 알고리즘이라고 불리는 반면, 수치해석에서는 정수 개의 discrete한 데이터가 아니라 사실상 연속인 구간을 다룬다. 그렇기 때문에 통상적인 이분법조차도 수렴이 느린 비효율적인 방법으로 간주된다.

double solve_bisect( double (*pfn)(double), double v )
{
    double f=-10.0, t=10.0; int nt=0;
    while(1) {
        double d = (f+t)/2.0;
        double p = pfn(d) - v;
        if(fabs(p) < 0.000001) break;
        if(p > 0) t=d; else f=d; nt++;
    }
    return f; //nt는 계산 횟수 counter
}

double pseudo_ln2(double x)
{
    return solve_bisect(pseudo_exp, x);
}

근 찾기 알고리즘 중에서는 뉴턴-랩슨(혹은 그냥 뉴턴) 법이 수렴이 매우 빠른 알고리즘으로 여겨지고 있다. 이 방법은 이분법과는 달리 시작점과 끝점이라는 구간을 잡고 시작하는 게 아니라 시작점에서 해당 방정식의 접선을 그은 뒤, 접선과 x축이 만나는(y=0) 지점을 다음 점으로 잡는다. 이 작업을 방정식의 값이 근인 0과 충분히 가까워질 때까지 반복한다.

사용자 삽입 이미지


방정식 f(x) 위의 점 (x_0, f(x_0))을 지나는 접선의 방정식은 기울기가 f'(x_0)일 테니 y=f'(x_0)*x + f(x_0) -f'(x_0)*x_0이 된다. 그래야 x에다가 x_0을 집어넣었을 때 f'(x_0) 나부랭이는 소거되고 함수값으로  f(x_0)만 남기 때문이다.
이 접선이 y=0을 만족시키는 다음 점 x_1을 방정식으로 풀면 x_1=x_0 - f(x_0)/f'(x_0)이라는 생각보다 깔끔한 식이 나온다. 이를 코딩하면,

double solve_newton( double (*pfn)(double), double (*pfn_prime)(double), double v )
{
    double d = 0.0; int nt=0;
    while(1) {
        double p = pfn(d) - v;
        if(fabs(p) < 0.000001) break;
        d = d - p / pfn_prime(d); nt++;
    }
    return d;
}

double pseudo_ln3(double x)
{
    return solve_newton(pseudo_exp, pseudo_exp, x);
}

뉴턴 법 함수는 도함수의 포인터를 별도로 받는데, exp는 어차피 도함수가 자신과 동일하므로 자신을 한번 더 넘겨주면 된다는 점도 특징이다.

프로그램을 실제로 돌려 보면 알겠지만, 동일 오차 범위를 줬을 때 뉴턴 법은 이분법보다 통상 2~5배나 더 빨리 수렴하는 걸 볼 수 있다. 마치 퀵 정렬이 pivot을 기준으로 자료가 그럭저럭 이미 정렬돼 있을수록 더욱 빨리 동작하고 자료의 상태에 민감하듯, 뉴턴 법은 접선과 가까운 형태의 부드러운 곡선일수록 수렴이 더욱 빨라진다.

자, 지금까지 공대 학부 수준의 아주 허접한 수학 덕질을 감각 유지 차원에서 잠시 복습해 보았다. 각종 공식들이 유도되는 원리를 좀 더 깊이 생각해 보고 싶으나 시간과 여유가 부족하다.

아, 수학에서는 거듭제곱뿐만이 아니라 팩토리얼까지도 자연수가 아닌 실수, 그리고 복소수 범위에까지 정의하고 그 증가폭을 측정하는 방법에 대해 연구가 진행돼 있다. 그 일환으로 ln n!이 n log n - n과 얼추 비슷하다는 스털링의 공식이 있고, 그보다 더 괴랄한 감마 함수라는 것도 있어서 z! = Γ(z+1)이다. 머리 좋은 똘똘이들의 수학 덕질의 끝은 도대체 어디까지인지를 다시 생각하게 된다.

Posted by 사무엘

2012/09/10 19:32 2012/09/10 19:32
, , , , ,
Response
No Trackback , 2 Comments
RSS :
http://moogi.new21.org/tc/rss/response/731

조화평균, 조화수열, 황금비

1. 조화평균과 조화수열

우리는 중등 학교의 수학에서 산술, 기하, 조화평균을 배운다.
물론, 대부분의 일상생활에서 숫자를 다룰 때는 단순히 합계를 자료의 개수로 나누기만 하는 산술평균 하나만 있어도 충분하다. 그러나 다른 개념의 평균이 필요할 때도 있다.

가령, 어떤 수치가 1년 간격으로 예전보다 3배, 4배, 5배씩 증가해서 총 60배가 되었다면, 이를 해마다 4배씩 증가했다고 싸잡아 간주할 수는 없는 노릇이다. 4의 3승은 64이지 60이 아니기 때문이다.

이런 식으로 비율 내지 배율을 좋아하는 계산 분야에서는 기하평균이 필수이다. 앞의 예에서는 (3+4+5)/3이 아니라, 3*4*5의 세제곱근인 약 3.915가 정확한 값이다.

그럼 조화평균은 무엇이며 어떤 용도로 쓰일까?
역수의 산술평균을 또 역수로 취한 값이 바로 조화평균이다. 두 수 a, b의 조화평균을 그 정의대로 구해서 식을 정리하면 2ab / (a+b)가 나온다. 쉽게 말해 곱을 합으로 나눈 셈이다.

자동차가 동일한 길이의 두 구간을 달리는데 한 구간은 시속 30km로, 다른 구간은 시속 60으로 달렸다면, 전체 구간에 대한 자동차의 표정 속도는 30과 60의 조화평균인 시속 40이 나온다. 한 구간의 길이가 30km였다고 생각해 보면 가는 데 시속 30으로 1시간, 시속 60으로 30분이 걸렸을 터이니 전체 60km를 1시간 반 만에 주파하는 속도는 시속 40이기 때문이다.

반대로 길이가 중요하지 않고 소요 시간의 절반을 시속 30으로 달리고 나머지 소요 시간 동안 60으로 달렸다면 자동차의 표정 속도는 응당 산술평균인 시속 45가 될 것이다. 관점의 차이를 이해하시겠는가?

학교에서 조화평균은 병렬 연결된 저항들의 전체 저항값을 구할 때 정도에나 쓰였지만 교통 관련 계산을 할 때 더욱 유용히 쓰일 수 있다.
어떤 노선에 버스가 5분 간격으로 다닌다고 치자. 그런데 5분으로도 모자라서 그 상태에서 3분 간격의 버스가 추가로 더 투입되었다면, 실질적인 배차 간격은 얼마로 좁혀졌다고 볼 수 있을까?

답부터 말하자면 이 값은 5와 3의 조화평균의 절반과 같은 1.875분이다.
5와 3의 최소공배수인 15분이라는 시간을 생각해 보면, 그 동안 5분 간격 버스는 3대가 다닐 수 있다. 그러나 3분짜리 버스는 5대가 다닐 수 있으므로 15분 동안 버스가 총 8대로 늘어난 셈이 된다.

따라서 실질적인 평균 배차간격은 15를 8로 나눈 1.875분이다. 5와 3의 조화평균인 3.75는, 5분 간격 버스와 3분 간격 버스를 합친 것이 3.75분 간격 버스 두 대를 합친 것과 동일한 증차 효과를 낸다는 걸 의미한다.

임의의 동일한 수들에 대해서 기하평균(G)은 산술평균(A)보다 크지 않으며, 조화평균(H)은 기하평균(G)보다 크지 않다는 것이 증명되어 있다. 그리고 아예 H=G^2 / A라는 항등식도 알려져 있다. 어떤 데이터에 대해서 두 종류의 평균값을 알고 있으면 다른 한 평균값은 그로부터 유도해 낼 수 있다는 뜻이 되겠다.

한편, 1/3, 1/4, 1/5 ~처럼 역수가 등차수열을 이루는 수열은 조화수열이라고 한다. A, A와 B의 조화평균, B으로 구성된 세 수는 응당 조화수열이다.
이건 등차나 등비수열도 아니고 도대체 무슨 의미가 있는지 궁금할 것이다. 하지만 자연에서 조화수열은 아주 직관적으로 쉽게 찾을 수 있다. 이름에 괜히 harmonic이 붙은 게 아니다.

일단 우리 눈에 사물이 비쳐 들어오는 원근법이란 게 반비례이기 때문에 조화수열과 관계가 있다. 직선으로 뻗은 도로에 균일한 간격으로 그어진 차선을 보자. 멀리 떨어진 놈일수록 중앙의 소실점에 가까워지고 겉보기 간격이 더욱 조밀해진다. 그 간격이 수학적으로는 바로 조화수열인 것이다.

거시적으로 보면 태양은 달보다 N배나 더 크지만 지구로부터의 거리도 똑같이 N배나 더 멀리 떨어져 있다. 그렇기 때문에 지구에서의 겉보기 크기가 둘이 거의 같으며 일식도 일어날 수 있다.

사람의 뇌는 두 눈이 보내 준 2차원 영상을 합성하여 3차원 공간을 인지하는 능력이 대단히 발달해 있다. 그런데 그 능력은 수학적으로 따지자면, 2차원 조화수열 간극으로부터 3차원 등차수열 간극을 유추하는 게 상당수를 차지하고 있을지도 모른다. 그만큼 조화수열은 우리에게 친숙한 존재이다.

그 다음으로 우리가 조화수열을 시각적으로 볼 수 있는 흥미로운 분야는 음악이다. 실로폰도 그렇고 파이프 오르간이나 하프도 그렇고, 음을 만들어 내는 매체는 저음이 언제나 길고 고음은 한 치의 예외 없이 짧다.

그런데 그 짧아지는 간격이 조화수열이다. 매체를 그런 간격으로 만들면 소리의 파형 주기는 기하급수적으로(=등비수열) 짧아지는 평균율 음계가 나오는가 보다. 어떻게 그게 물리적으로 가능한지는 잘 모르겠다.

2. 황금비

조화수열이라는 말이 나왔으니 말인데, 아름다움이나 조화 같은 걸 수학적으로 설명할 때 빠짐없이 등장하는 건 황금비이다.

기본 발상은 a:b = (a+b):a 비례식을 만족하는 a와 b의 비율이다. 음, 뭔가 심오하지 않은지? 쉽게 말해 긴 변과 짧은 변의 비율이, 긴 변과 짧은 변을 합한 것하고 긴 변과의 비율과 같은 걸 말한다. 이걸 식으로 표현하면 이차방정식으로 귀착되고, 황금비의 값은 (1+sqrt(5))/2, 대략 1.618이 된다.

황금비 상수는 뭔가 심오함이나 신비로움, 괴팍함이 느껴지는 초월수도 아니고, 간단한 이차방정식만으로 값을 구해서 모든 특성을 파악할 수 있는 평범한 대수적 수에 불과하다. 그런데 이게 왜 그렇게 중요한 걸까?

인간이 보편적으로 새벽 2시에 가장 깊이 잠들어 있는지, 저녁 8시에 죄책감 없이 가장 잔인해지는지는 잘 모르겠지만, 저 비율이 인간이 보편적으로 가장 심리적인 안정감과 균형과 조화를 느낀다고 그런다. 오죽했으면 golden ratio라는 이름이 붙었겠는가? 이것 말고 golden이라는 말이 붙은 개념은 “자신이 대접받고 싶은 만큼 남에게도 대접해 줘라”로 요약되는 golden rule 정도밖에 없다.

1 1 2 3 5 8 13 21~ 로 이어지는 그 유명한 피보나치 수열도 현재 항과 이전 항의 비율이 황금비로 수렴한다는 건 잘 알려진 사실이다. 일반항을 구하는 공식엔 응당 황금비 상수가 들어간다.

또한, 0부터 시작해서 x=sqrt(1+x)를 무한 반복해도 x는 황금비로 수렴한다. 계산 과정의 특성상 x는 sqrt(2)도 한 번 거치지만, 궁극적으로는 다른 수로 수렴하게 된다는 게 흥미롭다.
황금비는 역수가 자신에서 1을 뺀 값과 같다는 특징이 있기도 하다. (0.618...) 1/x = x-1인데, 이는 특별한 게 아니라 황금비의 정의의 특성상 당연한 귀결이다.

도형 중에서는 정오각형이 변 길이와 대각선 길이의 비가 황금비이다.
1마일이 대략 1.609km인 건 아무래도 황금비와는 관계가 없고 전적으로 우연인 듯하다.
또한 종래의 4:3 aspect ratio를 깨고 컴퓨터 화면이 가로로 좀 더 길쭉한 추세로 가는 것 역시, 사람들이 황금비를 심리적으로 더 좋아해서인지는 모르겠다.

한편, A4나 B4 같은 용지의 길이 비율은 황금비가 아니라 sqrt(2)이다. 본인은 A4 용지의 크기가 210*297mm인 건 알고 있었지만 그 비율이 sqrt(2)를 표방한 것인 줄은 전혀 모르고 있다가 최근에 알게 되고는 크게 놀랐다. 심심해서 297을 210으로 나눠 봤는데 딱 1.414...가 나왔으니 말이다.

이런 비율의 장점은 우리가 이미 실생활에서 적지 않게 경험한 적이 있지 싶다. 종이를 반으로 접어도 크기 비율이 접기 전과 동일하게 유지된다는 것.
즉, 황금비가 a:b = (a+b):a를 추구했다면, 용지는 a:b = b:a/2를 추구한 셈이다.
황금비가 길이가 1인 정오각형의 대각선 길이라면, sqrt(2)는 길이가 1인 정사각형의 대각선 길이이다.

원래는 조화수열에 대해서만 글을 쓰려고 했는데 어쩌다가 황금비까지 나오면서 얘기가 옆길로 샜는지 모르겠다. 둘은 실용적인 의미가 약간 유사점이 있다 보니 미묘하게 한 글로 엮이게 된 것 같다.

Posted by 사무엘

2012/07/25 08:26 2012/07/25 08:26
, ,
Response
No Trackback , 4 Comments
RSS :
http://moogi.new21.org/tc/rss/response/711

1.

수학에서 원주율 pi와 자연상수 e는 가장 유명하고 친근한 상수임이 틀림없다. 이들은 유리수를 계수로 가지는 대수방정식의 근이 되지 않는 초월수임이 증명되어 있고, 이들의 정의나 다른 특성에 따라 값을 구하는 식이 여럿 존재한다.

pi = 4(1/1 - 1/3 + 1/5 - 1/7 + 1/9 ... )
e = lim (1 + 1/n )^n (n → 무한대)

pi의 저 공식은 정말 이보다 더 쉬울 수 있을까 싶을 정도로 너무 깔끔하고, 저게 도대체 파이와 어떻게 관계가 있을까 하는 생각이 들기도 한다. 사실, 저것은 arctan(tan의 역함수) 함수의 테일러 급수에다가 1을 대입하여 얻은 식이다. 45도일 때 기울기(=탄젠트)가 딱 1이 되니, 저 값은 pi/4가 나오고, 따라서 pi를 구하기 위해 4를 곱한 것이다.

e의 경우, 숫자를 무한대로 띄우는 n승과, 그 지수 연산의 발산 효과를 무효로 만드는 1/n (1에다가는 아무리 큰 지수 연산을 해도 그대로 1..)의 극한이 저렇게 가까워지는 게 신기하기 그지없다.

그러나 위의 두 공식은 둘 모두 n 값이나 항의 개수가 100000이 넘어가도 소숫점 겨우 네댓 자리까지밖에 일치하지 않을 정도로 수렴이 대단히 느린 게 흠이다. 이 방식으로는 소숫점 n째 자리까지 일치하려면 계산량이 n의 지수함수 형태로 증가해야 한다. 알고리즘으로 치면 엄청나게 비효율적인 알고리즘이다.
그래서 실제로 pi나 e의 값을 계산할 때는, 매 회에 좀 더 복잡한 계산이 수행되더라도 적은 횟수로도 더 빠르게 수렴하는 다른 식을 찾아 쓴다.

자연상수 e는 exp(x), 즉, 미분해도 자신과 동일한 함수의 테일러 급수로부터 얻은 식을 이용해 값을 구할 수 있다. 바로 n팩토리얼의 역수의 무한합인데, 직관적일 뿐만 아니라 수렴 속도도 아주 빠르다. 물론 팩토리얼이 숫자를 폭발적으로 키우는 연산이긴 하지만, 그만큼 정확도도 커져서 14!까지만 계산해도 소숫점 8~9자리까지 정확한 값이 나온다. 그래서 이걸로 끝이고 다른 계산법을 찾을 필요가 사실상 없다.

자연상수라는 이름엔  '자연'이라는 단어가 괜히 붙은 게 아니다. 얘는 수학의 입장에서는 특성이 매우 자연스럽고 직관적이고 사랑스럽기까지(!) 한 수이기 때문에, 초월수라는 증명도 상당히 초창기에 이뤄졌다. 리우빌 상수--10진법 기준 n!에 속하는 소숫점 자리만 1이고 나머지는 0인 좀 괴랄한 0.110001000… --처럼 초월수의 존재를 증명하기 위해 일부러 설정된 수가 아닌 수 중에서는 초월수라는 게 증명된 최초의 수가 바로 자연상수이다.

pi는 e보다 더 오묘한 수여서 초월수 증명도 10년 남짓 더 늦게 나왔으며, 더욱 복잡하고 다양한 유도식들이 존재한다. 특히 컴퓨터가 발명되고 원주율 계산이 컴퓨터의 성능을 측정하는 잣대로 통용되기 시작한 뒤부터는 컴퓨터의 입장에서 더욱 계산하기 쉬운 형태의 식이 연구되기 시작했다. 그래도 어느 것이든 e만치 형태가 간단하면서도 빨리 수렴하는 식은 존재하지 않는 것 같다.

비록 컴퓨터 시대에 발견된 식은 아니지만,
sqrt(2) / 2 라는 분수에서 시작하여
sqrt( 2+ sqrt(2) ) / 2와 같은 식으로 분자에다가만 x → sqrt(2 + x)로 변환을 하면서 생성된 수들을 계속 곱하면 2/파이 (파이의 역수의  두 배)에 수렴하는데,
이것도 e만치는 아니지만 계속되는 곱셈과 제곱근 버프 덕분인지 수렴 속도가 빠른 편이다.

2.

1부터 n까지 자연수가 있고 이들의 역수를 나열하면 조화수열이 된다. 조화수열의 무한합은 비록 무지막지하게 느리지만 무한대로 발산한다는 것이 알려져 있다.
한편 n!의 역수의 무한합은 아까 말했듯이 e가 되는데,
그럼 n^2의 역수의 무한합은 무엇이 될까?

거듭제곱의 지수가 1보다 커지는 순간부터 역수의 무한합은 유한한 값으로 수렴하긴 한다. 그러나, 그 수렴값의 특성을 알아내는 건 아주 어려운 일이어서 지금까지도 알려진 게 그리 많지 않다.
n^x의 역수의 무한합을 일반적으로 x에 대한 리만 제타 함수값이라고 한다.

그리고 그 x가 짝수일 때는 놀랍게도 pi와 관련이 있는 값으로 수렴한다는 것이 천재 수학자 오일러에 의해 밝혀졌다. 가령, 2일 때는 이렇다.

1 + 1/4 + 1/9 + 1/16 + 1/25 ... = pi^2 / 6

그러니 이것도 응당 파이를 구하는 데 쓸 수 있는 공식이다.
비록 이것 역시 아까의 1/3 1/5 1/7 공식 만만찮게 수렴 속도가 몹시 느리기 때문에 실용성은 떨어지지만 말이다.

여기서 갑자기 pi가 튀어나오는 것도 신기하지만, 이 수의 진짜 놀라운 면모는 또 다른 곳에 있다.
바로 이 수는 자연수에 존재하는 소수의 분포와 관계가 있다.

1부터 N 사이에 있는 임의의 두 자연수를 뽑았을 때 이것이 서로 소일 확률은 N이 커질수록 바로 저 수, 다시 말해 (pi^2)/6의 역수로 수렴한다! 그 확률은 대략 60.8%이다.

아니, 리만 제타 함수에서 파이가 왜 조건부로 튀어나오며, 게다가 미적분· 해석학하고는 아무 관계가 없는 정수론과 관련된 의미가 왜 이런 데서 발견되는 걸까? 이걸 알아 낸 사람도 오일러이다.

2를 포함해서 리만 제타 함수의 짝수승의 값은 그래도 pi가 얽혀 있으니 초월수라는 건 확실히 인증이다만 홀수승의 값들은 무리수인 것만 알려져 있지 다른 특성은 알려진 바가 없다. 초월수일 게 거의 확실시되고 있긴 하나, 그조차도 정식으로 증명되지는 못했다.

3일 때의 값은 '아페리 상수'라 하여 일부 공학 분야에서도 쓰인다. 이 수가 무리수라는 증명을 1978년에 한 프랑스의 수학자 아페리의 이름을 딴 것이다. 정의대로 각 자연수들을 3승한 뒤 역수를 구해서 더하면 값을 구할 수 있지만, FM 방식은 역시 수렴이 더디기 때문에 훨씬 더 복잡하지만 더 빨리 수렴하는 별도의 급수 전개를 써서 값을 구한다.

그런데 이 값의 역수는 임의의 세 자연수가 서로 소일 확률이라고 한다. 마치 가위바위보에 참여하는 인원이 많아질수록 무승부가 나올 확률이 치솟듯, 세 자연수는 두 자연수일 때보다 서로 소일 확률이 올라가서 그 값은 약 83.1%에 달한다.

작은 범위에서라도 정말 얼추 그렇게 되는지는 프로그램을 짜서 간단히 확인해 볼 수 있다.
1부터 N까지 3중 for 문을 작성해서 모든 숫자 조합에 대해서 최대공약수를 구해서 1이 나오는 경우를 세면 되는데, N이 몇천 정도만 돼도 3중 for 문은 오늘날의 최신 컴퓨터에서도 버벅대는 작업량이다.

3.

그래서 본인, 이 기회에 멀티코어 프로그래밍을 실습해 봤다.
i5 쿼드코어답게 CreateThread 함수로 스레드를 4개 만들어서 뺑뺑이를 돌리는 분량을 인위로 분할한 뒤, 계산 결과를 취합했다. 그랬더니...

809615629/973620600 0.831551 (7753)
809615629/973620600 0.831551 (3448)

코어 하나밖에 못 쓰고 고로 CPU를 최대 25%만 쓰던 싱글스레드 오리지널 코드는 7.8초가 걸린 반면,
스레드를 여러 개 만드는 코드는 CPU를 95% 가까이 점유하면서 제 속도를 내더니, 싱글스레드의 절반이 채 안 되는 3.5초 남짓한 시간 만에 처리를 다 끝내는 걸 알 수 있었다. 실제로 서로 소인 조합이 전체의 83.1%가량을 차지하는 것도 사실이었다.

요즘 세상에 CPU를 70% 이상 한꺼번에 점유하는 프로그램을 내 손으로 직접 만들 일은 없었는데 참 오랜만에 보는 광경이었다. 요즘은 단일 프로그램이 CPU 성능을 제대로 활용하려면 이런 식의 테크닉을 동원해야 한다는 걸 더욱 절실히 느끼게 됐다.

Posted by 사무엘

2012/06/07 08:21 2012/06/07 08:21
, ,
Response
No Trackback , 9 Comments
RSS :
http://moogi.new21.org/tc/rss/response/692

삼각함수와 회전 변환

사용자 삽입 이미지
요 그림이 고등학교 수학 II에서 배우는 진정한 묘미 중 하나입니다.

(0, 0), (x, 0), (0, y)의 직각삼각형을 원점을 축으로 θ만큼 돌리니까 원점은 그대로고 밑변은 (x cosθ, x sinθ)가 됩니다.
그런데 밑변보다 y만치 위로 떠 있던 점은, 회전 과정에서 가로로는 높이 y의 sin값만치 “감소”(왼쪽으로)하고, 세로로는 cos값만치 증가합니다.

그러니 (x cosθ - y sinθ, x sinθ + y cosθ)의 형태가 되는데, 이는 원래 점인 x, y에 대한 일차변환으로 일반화할 수 있습니다. 결국

(cosθ, -sinθ)
(sinθ,  cosθ)


가 됩니다. “꼬마신 신꼬”라고 외우는 그 유명한 회전변환 행렬입니다.
이걸 모르면 특히 컴퓨터그래픽에서 현란한 벡터 조작이나 3차원 그래픽 같은 건 상상도 할 수 없습니다.

이 행렬식의 값은 1 (임의의 각도의 cos 제곱과 sin 제곱의 합은?), 따라서 이렇게 도형을 일차변환 시키더라도 원래 도형의 넓이를 바꾸지 않는다는 걸 알 수 있습니다. 역행렬은 sin 쪽 부호만 맞바꾸면 됩니다. 기하학적으로, 상식적으로, 역행렬 공식에 맞춰 생각해도 전부 명확합니다.

공통수학에서는 삼각함수란 게 있다는 것, 그리고 한 삼각형의 세 변과 세 각이 주어졌을 때 삼각함수가 이런 특성을 갖는다는 것을 배웁니다. 기하학인지 대수학인지 감을 못 잡는 이 괴상한 함수는 흥미보다는 학생들에게 어마어마한 암기를 강요하면서 악몽 같은 기억으로 남아 있을 것 같습니다.

그러다가 수학 II로 오면서 단순히 삼각형과 관련된 것이 아닌 삼각함수 자체의 특성을 더 깊게 공부하게 됩니다. 이 회전행렬은 삼각함수의 덧셈 정리를 유도시킵니다.
특히, 저 행렬에다가 회전 행렬과 같은 각인 (cosθ, sinθ) 열벡터를 뒤에 곱해 주면 cosθ와 sinθ 값으로부터 cos 2θ, sin 2θ의 값을 얻을 수 있게 되고, 그 값으로는 아예 cos²θ, sin²θ의 값도 구할 수 있게 됩니다.

  cos 2θ = cos²θ - sin²θ,  cos²θ = (cos 2θ + 1)/2
  sin 2θ = 2 cosθ sinθ

공을 공중을 향해 몇 도로 던져야 가장 멀리 날아가는지를 삼각함수를 계수로 하는 이차방정식으로 풀어 보면, 결국 cosθ sinθ 값(곱)을 최대로 하는 θ 값을 구하는 문제로 귀착됩니다. 이는 sin 2θ의 값을 최대화하는 것과 같으므로 θ는 45도임이 명확해집니다.

sin과는 달리 cos은 양 함수의 제곱의 합으로 바뀐다는 점도 흥미롭습니다. 2θ보다 더 일반적인 α와 β의 경우를 생각해 보면 더욱 흥미로운 결과가 나오는데요, 덧셈 대신 두 각의 차이를 나타내는 뺄셈만을 예로 들어 보겠습니다.

  cos(α-β) = cosα cosβ + sinα sinβ
  sin(α-β) = sinα cosβ - cosα sinβ

cos을 보면 이는 정확하게 벡터 내적과 관련이 있음을 알 수 있습니다. x, y 성분인 벡터를 거리와 각도로 바꿔서 표현해 보면, Ax·Bx + Ay·By가 왜 |A||B| cosθ인지가 명확해집니다. 공통수학 때 배운 코사인 제 2법칙과도 이미 관련이 있고요.
cos은 90도일 때 0이 되기 때문에 두 벡터가 기하학적으로 직각인지 판단할 때 유용히 쓰일 수 있습니다. 부호가 갈리는 기점이 직각이죠. 시계에서 3시를 향하고 있는 벡터가 있다면, 5시나 1시를 향하는 벡터와는 양수이고, 7시나 11시 벡터와는 음수가 되는 셈입니다.

그럼 sin은 무슨 관련이 있는 걸까요? sin은 90도가 아닌 0도를 기점으로 부호가 바뀝니다. 3시를 향하는 벡터 기준으로 5시나 7시를 향하는 벡터의 부호가 서로 같고, 1시, 11시 벡터와는 서로 다릅니다.
정보 올림피아드 대비하여 기하 알고리즘 공부할 때, 특히 convex hull 같은 거 구할 때 단골로 등장하는 게 세 점이 시계 방향인지 반시계 방향인지 판단하는 공식인데요, 그게 바로 sin과 관련이 있습니다. Bx·Ay - By·Ax입니다. 이 식은 두 벡터가 일직선상에 있을 때 값이 0이 됩니다.

그러나 cos 계열인 벡터의 내적은 sin과는 달리 3차원 이상에서도 일관되게 구하는 공식이 있고 임의의 차원에서도 의미를 갖는다는 점에서 더욱 의미 깊다고 할 수 있습니다. 시계 방향 여부는 2차원 평면에서만 의미를 가지며, sin과 관련이 있는 벡터의 외적 역시 3차원 공간에서만 정의됩니다.

이렇게 한바탕 수학 II 초· 중반에서 홍역을 치른 삼각함수는 나중에 아예 sin(x)/x의 0 극한을 구하고 삼각함수를 미· 적분함으로써 더욱 해석학적으로 접근하게 됩니다. 고등학교 수학 교육 테크트리에서 맨 마지막으로 지어지는 최고급 건물 내지 유닛은 단연 미적분이라 할 수 있습니다.

Posted by 사무엘

2011/11/02 19:31 2011/11/02 19:31
, , , , ,
Response
No Trackback , 15 Comments
RSS :
http://moogi.new21.org/tc/rss/response/592

« Previous : 1 : 2 : 3 : 4 : Next »

블로그 이미지

철도를 명절 때에나 떠오르는 4대 교통수단 중 하나로만 아는 것은, 예수님을 사대성인· 성인군자 중 하나로만 아는 것과 같다.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2021/10   »
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            

Site Stats

Total hits:
1674407
Today:
69
Yesterday:
622