BigFloat로 Pi를 구해보자-13. 가우스-르장드르 알고리즘

Posted by 적분 ∫2tdt=t²+c
2012.12.01 15:25 프로그래밍/Multi precision


저번 연재에서는 코사인 함수를 이용하여 Pi계산속도를 비약적으로 끌어올렸었죠. 하지만 그게 최종 보스가 아닙니다. 수학자들은 수학자들답게 Pi를 구하는 무시무시한 알고리즘을 개발해냈는데, 이름만 들어도 무서운 가우스-르장드르 알고리즘(Gauss-Legendre algorithm) 입니다.


위키에도 잘 설명되어있지만, 굳이 간단하게 소개하자면 다음과 같아요.


먼저 초기값을 다음과 같이 줍니다.


그리고 아래 점화식에 따라 다음 항들을 차례로 계산해줍니다.


그러면 n이 커짐에 따라 다음값은 Pi에 수렴합니다.

으아... 전혀 이해가 되지 않는 알고리즘입니다. 산술-기하 평균의 극한이 1종 타원 적분과 연관있다는 사실을 이용하는 알고리즘이라는데... (솔직히 잘 모르겠어요 어려워요ㅠ)

중요한건 이 알고리즘은 n을 키워감에 따라 정밀도가 2배씩 증가하는 좋은 성질을 가지고 있다는 것입니다. 즉 n자리의 정밀도를 얻기 위해서는 log n번의 반복만으로 충분하다는 것이지요. 게다가 알고리즘에 이용되는 연산은 사칙연산과 제곱근 밖에 없습니다. 우리는 제곱근을 O(n2)에 계산해 낼수 있으니, 1회 반복에 걸리는 시간을 O(n2)으로 맞출수 있지요. 그 결과 우리는 O(n2log n)시간에 n자리 정밀도의 Pi를 계산해 낼수 있습니다!

(저번 연재에서 cos함수의 시간복잡도가 O(n2log n)보다 컸다는 것을 생각해보면, 가우스-르장드르 알고리즘이 얼마나 빠른것인지 알수 있을겁니다.)

이제 코드를 짜봅시다.




중간에 쓰인 i_bsu 함수는 최상위비트가 몇번째 비트에서 나타나는지 알려주는 함수입니다. 내부구현은 지저분하니, math.h의 log함수를 이용해서, (int)(log(dest->size)/M_LN2) 이렇게 작성할 수도 있습니다. 마지막에 +1은 혹시나 오차로 인해 정밀도가 충분히 도달 못할지도 모르니, 넉넉하게 한 번더 반복을 돌려주기 위함입니다.


얼마나 빠를까요? 테스트해봅시다.

512 길이 정밀도(32*512비트)입니다.


올ㅋ 또 기록갱신했네요ㅋ 게다가 오차도 Pi_cos2 함수보다 작아요!

Tags
이 댓글을 비밀 댓글로
    • classical
    • 2013.08.30 17:30 신고
    만드신 BigFloat 유용하게 잘 썼습니다 간단하고 좋네요 ㅎ
    근데 조금 아쉬운 점이 0.xxx 소수점 자리만 무한정 표현이 되고
    정수부의 경우는 그냥 int 타입 범위만큼만 표시될 뿐이네요..

    목적이 pi값 계산이라서 정수부는 필요가 없어서 그런 거 같은데
    혹시 이 부분을 확장시켜서 정수부도 무한정 크게 할 수는 없을까요?
    size 인자만큼 가수부를 표현하고 거기서 점이 찍히는 부분은
    아무데나 되도록..(물론 이건 고정소수점 이지만..)

    이걸 이용해서 뭘 짜고 있는데 다른 c++ 에서 쉽게 포팅해서 쓸 수 있는
    마땅한 BigFloat 라이브러리가 잘 보이지 않네요..
    구글에서 찾은 건 정밀도에 문제가 있어서 한 8자리만 넘어도 오차가 엄청나게 심해지구요..
    gmp/mpfr 을 쓰기는 좀 거창하고 혹시 업데이트 하실 계획은 없나요?..
    뭐 없으면 어쩔 수 없지만..
    • 예전에 말씀하신 방식대로 부동소수점 포맷으로 BigFloat를 구현한적이 있는데요, 부동소수점이라는 특성 때문에 연산시 소수점 맞추기 위해 시프트하는데 연산 시간을 많이 낭비해서 효율적이지 못하더라구요. 그때 구현했던게 생각보다 속도가 많이 느려서 그 방식엔 자신이 없습니다... 연산 목적이라면 GMP사용하시는게 속도를 비롯한 다양한 면에서 좋을거 같네요.
  1. 이거 진짜 짱짱 알고리즘이죠. 간단하면서도 수렴속도가 어마어마한. 가우스-르장드르 알고리즘이라고도 하고, 살라민-브랜트 알고리즘이라고도 하더군요. 아마 실제로 만든 사람은 살라민이랑 브랜트인것 같은데, 그 알고리즘 설계할 때 사용되는 핵심 수학 툴이 가우스와 르장드르의 이론에서 나온 것 같아 혼용해서 부르는 것 같아요.

    일본의 카나다 교수팀이 이 알고리즘을 이용해 슈컴으로 최초로 원주율 소수점아래 약 1조자리였던가? 그만큼 구했다고 들었습니다.
    • 그죠 진짜 놀라운 알고리즘인듯합니다. 수학을 잘 모르는 우매한 중생으로서 그저 우와 하면서 공식을 쳐다만 볼뿐입니다ㅎㅎ
  2. 약 3년 전 쯤 이 글을 읽었습니다. 당시엔 저도 이 가우스-르장드르 알고리즘의 비밀을 몰랐다가 제작년 쯤 그비밀을 알게 됬네요. 제가 차근차근 정리해놓은 포스팅이 있는데 주인장님이 혹시 관심있으실까 해서 소개해드립니다.

    https://m.blog.naver.com/PostView.nhn?blogId=greengb&logNo=220730355588&proxyReferer=http%3A%2F%2Fm.blog.naver.com%2FPostList.nhn%3F blogId%3Dgreengb%26categoryNo%3D11%26currentPage%3D4%26listStyle%3Dstyle2

    사실 위 포스팅은 총 7부작 중 결론부분이라 이거 하나만 보시곤 이해하시긴 힘들겁니다. 시간이 되시면 1부 부터 차근차근 읽어보시길 추천드립니다^^
    • 와 그동안 열심히 공부하시면서 정리하셨군요. 대단하십니다! 좋은 정보 공유 감사드립니다!