57. 프로젝트 오일러 #57 : 제곱근의 수렴

이번 문제는 수학 문제인 듯 보이지만, 그냥 단순 계산 문제입니다.

프로젝트 오일러 사이트 난이도 평가 5% 문제네요.

문제의 내용은 2의 제곱근을 구할 때, 연분수 전개를 할 수가 있습니다.  연분수 전개에 관련해서는 펠의 방정식(http://sdev.tistory.com/213) 글을 참조하세요.

와 같이 2의 제곱근을 표시할 수 있습니다.

이 문제에서는 이것이 중요한 것이 아니고, 이 연분수 전개를 할 때, 분수로 표현하게 되면, 분모와 분자가 모두 정수가 되는데, 분자의 정수부가 분보의 정수부보다 자릿수가 많은 것이 몇개가 있는 가가 문제입니다.

연분수 전개를 분수로 만들면 되는 것이지만, 연분수 전개 자체가 상당히 큰 자릿수가 나옵니다.  물론 double 형을 이용해서 근사치로 계산해도 되겠지만, 실제 double을 이용해서 계산하면, 이 문제의 답이 틀려지게 됩니다.  그만큼 예민해서, 어쩔 수 없이 BigInt를 이용해서 풀어야 합니다.

BigInt를 이용해서 푸는 것은 사실 C/C++ 언어보다는 Python과 같이 BigInt 라이브러리가 기본 제공되는 것을 이용하는 것이 편합니다.

저는 제가 직접 만든 BigInt 라이브러리를 이용했습니다.  

#include <stdio.h>
#include <time.h>
#include "NxBigInt.h"

void solve1()
{
    NxBigInt d = 2, n = 3, d1 = 1, n1 = 1;
    int count = 0;
    for( int i = 2 ; i <= 1000 ; i++ )
    {
        NxBigInt t;
        t = 2*d+d1; d1 = d; d = t;
        t = 2*n+n1; n1 = n; n = t;
        uint8_t s[1000];
        int l1 = d.ConvertToArrayLE(s, 1000);
        int l2 = n.ConvertToArrayLE(s, 1000);
        if( l2 > l1 ) count++;
    }
    printf("Ans = %d\n", count);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}

python에 비해서 C/C++로 제가 효율이 그렇게 훌륭하다고 생각치는 않지만, 2~3배 빠르게 수행이 되었습니다.  인터넷에서 BigInt 라이브러리를 찾으셔서 C/C++에 적용해도 되고요.  

알고리즘 자체는 그다지 어렵지는 않습니다.