25. 프로젝트 오일러 #25 : 1000자리 피보나치 수열항 구하기

C/C++ 언어를 배우다보면, 꼭 한번은 프로그램해보는 것이 있다면, 피보나치 수열일거라 생각합니다.  피보나치 수열은 재귀함수를 사용한 곳에서도 많이 나오지만, 동적 프로그램이 필요한 예로도 자주 사용됩니다.

피보나치 수열은 한쌍의 토끼의 개체수 증가라는 퀴즈 형태에서 출발한 것인데요.  꼭 토끼가 아니라도 대장균의 증식같은 데에서도 응용할 수 있습니다.  기하함수로 증가하는 곡선을 보이게 됩니다.

피보나치는 아주 간단한 점화식을 이용합니다.

점화식을 보면 아주 간단한 형태입니다.  전항과 전전항을 더한 값이 현재항의 값이 됩니다.

그래서  첫번째 항과 두번째 항이 초기값으로 주어져야 합니다.  첫번째 항은 1, 두번째 항은 1입니다.  자연수 범위안에서 피보나치 수열은 진행합니다.  확장해서 음수항을 만들기도 하지만, 여기서는 양수항만을 다루도록 할께요.

간단한 점화식을 사용하지만, 일반항을 구하는 방법은 좀 까다롭습니다.  수학적 방법론이 어떻게 나왔는가는 여기서 중요하지 않으니, 그것은 생략하고요.  일반항을 구하는 방법을 제 식으로 표현하면 다음과 같습니다.

위와 같이 만들면, 우리는 서로 다른 두개의 해를 구할 수 있습니다.  해는 2차방정식의 근의 공식을 이용하면 손쉽게 구할 수 있습니다.  그 해는 우리가 흔히 말하는 황금비율값입니다.  그래서 더 피보나치 수열이 유명해졌는지도 모르겠네요.  (그 외에 피보나치 소수도 있고요.)

이 값이 결정되면, 우리는 피보나치의 일반항을 구할 수 있습니다.

피보나치 일반항을 홤금비를 이용해서 표현하면 다음과 같습니다.

만약 프로그램에서 큰 수에 대한 피보나치 항을 구하라는 것이 있다면, 위의 일반항 공식을 이용해서 풀어주는 것이 필요합니다.

피보나치 일반항을 구하는 프로그램은 INT64 범위 안에서는 다음과 같이 표현할 수 있습니다만, double을 쓴 관계로 실제 큰 수에 대해서는 오차가 발생할 수 있습니다.

이번 문제는 천자리가 되는 피보나치 수열의 항을 구하는 문제인지라, 여기서는 황금비를 이용해서 그 값이 천자리가 넘는 항을 구하도록 했습니다.

일단 천자리를 표현하려면, big integer를 사용하던지, 아니면 double 과 같이 부동소수점(floating point) 숫자를 사용해주셔야 합니다.  저는 double을 사용하되, log를 이용해서 문제를 풀었습니다.  log의 경우에는 자릿수 계산하는 것이 훨씬 편하거든요.  천자리 숫자라면 실제로는 10의 999승정도입니다.  그리고 피보나치 수열에서 봤을 때, 첫번째 황금비의 n승이 뒤의 항보다 큰 숫자에서는 더 의미가 생깁니다.  왜냐하면 황금비는 약 1.618이므로 이 값에서 1을 빼면 0.618이 되어, 1보다 작은수가 되기 때문에 n이 클 수록 0에 가까워지는 숫자이기 때문입니다.

이것을 이용하면 프로그램은 아주 간단해지고, 또한 그 속도도 엄청납니다.  일일이 할려고 했다면, big int를 이용하기 때문에 몇천개의 숫자 계산을 하더라도 일반 정수 연산보다는 엄청나게 많은 시간을 소모하게 됩니다.  (그래도 시간이 많이 걸리지는 않을 것 같지만요.)

소스는 참고용으로만 봐주세요.  실제 소스만 봐서는 왜 이렇게 구현하는지는 이해하기 힘들 수 있습니다.  수학적인 부분이 들어간 것이니까요.

#include <stdio.h>
#include <math.h>

int main()
{
    double logphi = log10((1.0+sqrt(5.0))/2);
    double log5 = 0.5*log10(5);

    printf("Ans = %d\n", (int)((999.0+log5)/logphi)+1);
}