상세 컨텐츠

본문 제목

BigFloat로 Pi를 구해보자-12. 코사인 함수를 이용한 계산법

프로그래밍/Multi precision

by 적분 ∫2tdt=t²+c 2012. 11. 26. 00:19

본문


저번 연재까지는 아크탄젠트 급수와, 이를 이용한 Machin 급수로 Pi를 계산하는 방법에 대해서 다뤘습니다. 이번에는 저번 방법보다 훨씬 빠른 코사인 함수를 이용한 계산법에 대해서 소개합니다.



위 점화식은 n이 무한히 커짐에 따라 Pi/2에 수렴합니다. x 값의 정밀도가 어느 정도인지에 상관없이 항상 그보다 더 정밀한 근사값을 계산해줍니다. 

오차가 얼마나 빨리 줄어드는지 계산해 볼까요?


오차를 입실론이라고 하면 다음과 같이 식을 세울 수 있습니다.


함수 꼴로 바꿔보면 조금더 보기 쉽겠네요


테일러 급수를 이용하면 다음 사실이 자명함을 알 수 있습니다.



그러므로 역시 다음도 성립합니다.


즉 오차는 매 반복마다 세제곱 한것보다 더 줄어듭니다. 다르게 말하면, 매 반복마다 정밀도가 최소 3배씩은 증가한다는 말입니다.

수렴속도도 빠를 뿐만 아니라, incremental 하다는 장점도 있습니다. (나눗셈 구현할때 사용했던 Newton-Raphson 방법처럼ㅋ : 7. 나눗셈 최적화와 큰O 표기법(Big-O Notation))

즉 처음에는 작은 정밀도로 계산해나가다가, 나중에 차차 정밀도를 키워가는 테크닉을 사용할 수 있다는 것이지요.




이 방법을 구현하기 위해서는 먼저 코사인 함수를 구현해야 합니다. 코사인 함수의 테일러 전개는 널리 잘 알려져 있지요.

분모가 팩토리얼로 늘어나면서 x값이 무엇이든간에 상관하지 않고 다 수렴시켜버립니다!! (오오미 팩토리얼 증가의 위대함!)

하지만 이 전개가 모든 값에 다 수렴한다고 해도, 빠른 수렴속도를 위해서는 최대한 작은 x를 고를 필요가 있습니다. 그래야 수렴속도가 빨라지니까요. 우리가 x로 사용할 값은 Pi/2 근처값이니 1보다 큽니다. 1보다 작으면 수렴 속도가 빨라서 참 좋을텐데요...


일단 코사인 함수를 구현해봅시다!

매번 x^2을 계산하는것은 시간/에너지 낭비니깐, 먼저 x^2을 계산해서 저장해두면 좋겠네요.

그리고 처음 계산한 x^2/2!는 다음에 x^4/4!를 계산할때 이용하면 좋겠네요. x^2/2! 에다가 x^2을 곱하고, 3*4를 나누면 바로 다음 항을 구할 수 있으니까요. 이런 테크닉을 이용해 3번의 곱셈과 1번의 덧셈을 이용해 하나의 항을 계산할 수 있습니다.



불행히도 우리는 저 반복문이 몇번이나 돌지를 사전에 예측할 수가 없습니다 ㅠ(O(n)보다는 작지만, O(log n)보다는 큰 그 사이 어딘가에...). 확실한 건 초기값 a가 작아서, 항이 빠르게 감소하길 기대하는 것 뿐이지요. 곱셈이 시간복잡도가 O(n2)이었으니 코사인함수 전체의 시간복잡도는 O(n2log n)보다는 크고 O(n3)보다는 작게 되겠습니다.


하지만 저 속도에는 만족못하겠네요. 삼각함수의 반각공식이 있습니다.

cos x 를 계산하는 대신에, cos x/2를 계산해서 이것으로 cos x를 구하는 겁니다. 이 방법을 재귀적으로 사용하면 빠른 속도로 cos 을 계산해 낼수 있을 겁니다. x를 너무 많이 반으로 쪼개어 계산하면 오차가 누적되어 다른 값이 나올 수 있으니 주의해야합니다.

이 방법을 이용한 cos2함수입니다.



RR_cos2함수는 RR_cos함수보다 훨씬 빠릅니다. 문제는 약간 오차가 발생한다는 건데, 그 정도는 충분히 감수할 만하지요. 오차문제는 dest의 size를 처음에 넉넉하게 잡음으로써 해결할 수 있습니다.


자 이제 우리의 최종 목표였던 Pi를 계산해봅시다.



32비트 512 길이 (즉 32*512비트 정밀도)

RR_pi_cos2 함수의 압도적인 승리입니다!

태그

관련글 더보기

댓글 영역

  • 프로필 사진
    2014.01.02 11:12
    흥미로운 방법인데요!!

    그러면 이것은 cos함수를 테일러급수로 근사하는 함수랑, Xn재귀함수랑 따로따로 돌아가겠군요?
    • 프로필 사진
      2014.01.02 22:34 신고
      따로따로 돌아간다는게 멀티스레딩이 가능하다는 뜻이면, 그리 간단하지는 않을것같아요.
      코사인값이 연산이 끝나야 그 결과를 Xn재귀함수에서 사용할수있으니까요. 물론 방법이 없지는 않을겁니다... 고민해볼만한 문제네요