피보나치 수열의 일반항을 꼬리재귀로 만들기

트램폴린을 이용한 피보나치 일반항 함수 최적화

사실 이 문제는 피보나치 수열의 일반항을 구하는 재귀 함수를 어떻게 꼬리 재귀로 바꾸느냐가 핵심 아이디어임.

트램폴린 기법을 써서 피보나치 일반항 함수를 최적화해보자. 그러려면 우선 피보나치 일반항을 구하는 함수를 작성해보자.


func fib(n: Int) -> Int {
    guard n > 1 else { return n }
    return fib(n: n-1) + fib(n: n-2)
}

위 함수는 다들 알겠지만, 숫자가 조금만 커지면 성능이 극도로 나빠진다. 이를 극복하기 위해서 (이전에 설명했듯이) 메모이제이션을 하는 것도 방법이지만, 꼬리재귀 최적화를 통해서 성능을 향상시키는 방법도 있다. 위 함수는 어떻게 꼬리재귀 형태로 바꿀 수 있을까? 보통의 꼬리 재귀의 경우에는 누적값 파라미터를 하나 더 넣어준다. 그런데 여기서는 누적값을 추적하기 위해서 파라미터가 두 개가 되어야 한다. 피보나치 수열의 일반항을 꼬리재귀로 만들기 더보기

오일러 프로젝트 25

오일러 프로젝트 25 번은 1000자리 이상이 되는 수가 피보나치 수열의 몇 번째 항에서 처음 나타나는 가를 묻는 문제이다.

피보나치 수열은 아래와 같은 점화식으로 정의됩니다. Fn = Fn-1 + Fn-2 (단, F1 = 1, F2 = 1). 이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다.

F1 = 1

F2 = 1

F3 = 2

F4 = 3

F5 = 5

F6 = 8

F7 = 13

F8 = 21

F9 = 34

F10 = 55

F11 = 89

F12 = 144

 

수열의 값은 F12에서 처음으로 3자리가 됩니다. 피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까? (http://euler.synap.co.kr/prob_detail.php?id=25)

접근

어떤 수 x에 대해서 10을 밑으로 하는 로그를 취하면 그 정수부값 + 1이 자리수가 된다. 예를 들어 10은 log_{10} 10 = 1이고 두 자리 자연수이다. 따라서 피보나치 수열을 계산해 나가면서 로그값을 취해 999 이상이 되는 첫 항을 구해보면 된다. 다른 큰 수가 등장하는 문제들에서도 그렇고 파이썬이라면 큰 수 계산에 그렇게 큰 부담을 가지지 않아도 된다. 상용로그 함수는 math 모듈 내에 포함되어 있다.

from math import log10

def e25():
  n, a, b = 2, 1, 1
    while 1:
        if log10(b) >= 999:
            print(n)
            return
        a, b,n  = b, a+b, n+1

%time e25()
#4782
#Wall time: 6 ms

큰 수를 사용할 수 없을 때

Swift처럼 큰 수를 사용할 수 없는 경우에 어떻게 처리할까? 이미 만들어본 BigNumber를 사용하는 방법이 있을것이다. 그러나 정작 효율은 매우 좋지 못하다. 겨우 4782번항까지 계산하는 것치고는 너무 심하게 오래 걸리는게 문제이다. (그나마 최적화 옵션줘서 컴파일했을 때 실행해보면 4~5초대가 나오기는 하는데…) 그래서 좀 다른 접근법이 필요하다.

위키 백과에서 피보나치 수열을 찾아보면 비네의 식이라는 피보나치 수열의 일반항의 근사치를 구하는 식이 나온다.

F_n = \frac{\phi^n - (1 - \phi)^n}{\sqrt{5}}

그리고 이 식으로부터 F_n\frac{\phi^n}{\sqrt{5}} 에 가장 가까운 정수라는 사실을 알 수 있다. 그리고 이 값이 1000자리가 되어야 하므로 다음과 같은 부등식을 세울 수 있다.

\begin{array}{rcl}  \frac{\phi ^ n}{\sqrt{5}} & > & 10^{999} \\  \phi ^{n} & > & \sqrt{5} \cdot 10^{999} \\  n \cdot \log{10}{\phi} & > & 999 + log{10}{\sqrt{5}} \\  n & > & \frac{999 + log{10}{\sqrt{5}}}{log{10}{\phi}} \end{array}

따라서 다음과 같이 빠르게 계산할 수 있다.

이 때 \phi는 황금비율로 \frac{1 + \sqrt{5}}{2} 로 계산된다.

import Foundation

let phi: Double = (1 + sqrt(5.0)) / 2
let x: Double = (999 + log10(sqrt(5)) / log10(phi)
print(Int(x + 0.5))

 

재귀호출과 피보나치 수열 탐구

재귀호출은 함수가 그 내부에서 자신을 다시 호출하는 것이다. 이는 언뜻 이상하게 보일 수 있고, 경우에 따라서는 의도치 않은 동작을 하게 할 수 있어서 일반적으로는 지양되는 방법이기는 하나, 대신에 코드가 짧아질 수 있고 실행 로직 자체가 어느 정도 제한된 경우라면 충분히 사용할 수 있다. 특히 하스켈과 같은 함수형 언어에서는 반복문을 돌리는 로직이 없기 때문에 재귀호출을 하는 함수를 자주 사용하게 된다. 재귀호출과 피보나치 수열 탐구 더보기