상세 컨텐츠

본문 제목

BigFloat로 Pi를 구해보자-10. 본격 Pi 구하기: 아크탄젠트 급수

프로그래밍/Multi precision

by ∫2tdt=t²+c 2012. 11. 17. 15:45

본문


드디어! 이번 연재의 궁극적인 목표인 Pi 계산에 필요한 모든 것들이 준비되었군요.

(사실 Pi를 계산하기 위해서는 사칙연산만 구현하면 충분합니다...ㅋ)


미적분이나 급수가 등장하기 전까지 고대인들은 Pi를 구하기 위해서 여러가지 삽질...(보다는 노력!)을 했었는데요, 수학적 테크닉이 발전하면서 빠른 속도로 Pi를 구하는 방법이 어마어마하게 등장했습니다. 이제 우리는 책상머리에 앉아서 몇개의 수식을 가지고 Pi를 계산해 낼 수 있지요.


가장 널리 쓰이는 방법은 Machin의 공식입니다.


이 공식을 본 수많은 사람들은, Pi가 이렇게 단순하게 홀수들의 역수의 합차로써 계산된다는것에 충공깽했죠.

이 식은 아크탄젠트[각주:1] 급수에서 쉽게 유도될수 있습니다. (삼각함수 정도는 기본인거잖아요? 삼각함수/라디안에 대한 설명은 무심한듯 시크하게 생략합니다.)


아크탄젠트 함수를 테일러 전개하면 위와 같은 계산식을 얻어낼 수 있습니다. 여기에 x=1을 대입하면

참 쉽죠..?


문제는 이 식은 수렴속도가 너무 느리다는 것입니다. 매번 더하는 항의 부호가 바뀌어서 오르락내리락 하는데다가 분모가 2씩 밖에 안 늘어나니깐...

n항까지 더한다고 해도 오차는

늘 이런 식입니다. 만약 p비트 정밀도의 Pi를 구하고 싶다면, 오차가 2-p보다 작아야 할테니, 적어도 번째 항까지는 계산을 해야합니다... 꺅 ㅠㅠ 그렇다면 어찌할 것인가...




수학을 공부한 사람답게 머리를 써봅시다.

첫번째 식처럼 아름답지는 않지만, 급수의 수렴속도가 훨씬 빨라졌습니다. 매 항이 적어도 1/3배씩은 줄어드니, 등비수열보다 더 빨리 수렴하겠네요ㅋ 아까보단 만족스럽습니다. 코드를 짜볼까요?


여기서 RR_invu32함수는 RR_inv함수(BigFloat로 Pi를 구해보자-7)를 32비트 정수에 대해 최적화시킨것입니다. 코드는 다음과 같아요.



이 방법은 얼마나 빨리 Pi를 계산해낼까요? 시간복잡도를 계산해봅시다.

n비트 정밀도의 Pi를 계산한다고 하면 일단 반복문은 약 번 돌아가게됩니다. (탈출조건이 u가 0이 되는것이었는데,  u는 반복할때마다 1/3씩 두 번 줄어들었으니까요)

반복문 안에서는 곱셈이 6번(곱셈 4번과 나눗셈 2번)이고, 덧셈이 2번(덧셈 1번과 뺄셈 1번) 반복되지요.곱셈, 나눗셈의 시간복잡도는 O(n2)이었으니, 전체의 시간복잡도는 O(n2 log n)이 되겠군요.

(유의해야할 것은 시간복잡도는 n이 커질때 전체 연산시간이 어떤 형태로 증가하는지를 나타내는것이지, 알고리즘 자체의 속도를 평가하는 방법은 아니란 것이지요. 다음 연재에서 나올 방법은 여기서 사용한 방법과 같은 시간복잡도를 가짐에도 속도는 현저히 차이나기도 합니다.)


실제로 돌려보면 알겠지만, 이 알고리즘으로는 빠르지 않아서, 몇천자리 계산하는데도 한참 걸립니다...ㅋㅠ

더 빠르고 좋은 방법은 다음에 계속.

  1. arctan(아크탄젠트)함수는 tan(탄젠트) 함수의 역함수를 말합니다. tan(Pi/4) = 1이므로, arctan(1) = Pi/4 인거지요. [본문으로]

관련글 더보기

댓글 영역