큰 N에 대해서 N번째 피보나치 수를 구하기
피보나치 수열의 일반항을 구하는 함수에 대해서 오일러 프로젝트 관련 글에서 한 번 언급한 적이 있는데, 점화식을 그대로 정직하게 코드로 옮겨놓은 경우, 극히 작은 일부 n에 대해서만 실용성이 있을 정도로 비효율적이다. 35 정도를 넘기면 느려지기 시작하는데 40정도만 되어도 처참한 성능을 보여준다.
def fib_1(n):
if n < 3:
return n - 1
return fib_1(n - 2) + fib_1(n - 1)
%time fib_1(40)
# 63245986
# CPU times: total: 4.19 s
# Wall time: 8.53 s성능을 개선하기 위해서 메모이제이션 같은 테크닉을 사용할 수 있다. 미리 계산한 결과를 저장해두고 있다가 재계산을 피해서 반복횟수를 줄이는 방법이다. 메모이제이션 기능을 수행하는 데코레이터를 작성하여 함수 구현의 변경 없이 메모이제이션을 적용할 수 있다. 똑같은 함수를 이렇게 작성하면 수행시간을 기적처럼 줄일 수 있다.
from functools import wraps
def memoize(f):
cache = {}
@wraps(f)
def inner(*args):
if args in cache:
return cache[args]
r = f(*args)
cache[args] = r
return r
return inner
@memoize
def fib_2(n):
if n < 3:
return n
return fib_2(n - 2) + fib_2(n - 1)
%time fib_2(1000)
# 268638100244853593861467272021....078474174626
# CPU times: total: 0 ns
# Wall time: 998 µs하지만 재귀함수는 재귀 깊이의 제한이 있기 때문에 충분히 큰 값에 대해서는 작동하지 못한다는 문제가 있다. 사실 피보나치 수열의 경우 반복문을 통해서 첫번째 행에서부터 시작하여 누적합을 구하는 것으로 대체할 수 있기는 하다.
def fib_3(n):
a, b = 0, 1
for _ in range(n - 1):
a, b = b, a + b
return a
%time fib_3(9999)
# 128511566392982....71469773408709136249 (2090 자리의 수)하지만 이 역시 ‘적당한’ 크기의 N에 대해서만 충분히 빠르다. 에를 들어 N=1,000,000 일 때 N 번째 피보나치 수를 계산하려면 루프를 백만번 돌아야한다. 이렇게 아주 큰 수에 대해서 피보나치 수를 구할 때에는 빠른 피보나치 변환 (Fast Fibonacci Transform)을 사용한다. 빠른 피보나치 변환은 피보나치 수열의 점화식을 행렬로 처리하는 것이다.
\begin{matrix} & A = & \begin{bmatrix} 0 & 1 \end{bmatrix} \\ \\ & B = & \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \\ \\
& A \times B = & \begin{bmatrix} 1 & 1 \end{bmatrix} \\ \\
& A \times B \times B = & \begin{bmatrix} 1 & 2 \end{bmatrix} \\ \\ & F_{n} = A \times B^{n} \end{matrix}순수 파이썬에서는 아직 행렬을 제공하지 않지만, 행렬의 곱셈과 거듭제곱을 계산하는 함수를 조합하여 아래와 같이 구현한다.
def multiply(x: list[int], y: list[int]) -> list[int]:
a, b = x
c, d = y
return (a * c + b * d, a * d + b * c + b * d)
def power(x: list[int], n: int) -> list[int]:
if n == 0:
return [1, 0]
elif n % 2 == 0:
return power(multiply(x, x), n // 2)
return multiply(power(multiply(x, x), n // 2), x)
def fast_fib(n):
return power([0, 1], n)[0]
for i in range(20):
print(fast_fig(i))
# 1
# 1
# 2
# 3
# 5
# 8
# 13
# ...
# 280571172992510140037611932413038677189525이 알고리듬을 이용하면 백만번째 피보나치 수를 구할 수 있다. 이 수는 약 208,998자리수로 여기에 다 쓰기에도 벅찰 정도로 큰 수이다. 참고로 파이썬의 정수는 자리 수에 제한이 없지만, 큰 정수를 출력하기 위해서 문자열로 변환할 때에는 4300자리까지 제한이 있다. 이 제한을 풀기 위해서는 sys.set_int_max_str_digits() 를 사용하여 허용자릿수를 늘려주면 된다.
참고로 피보나치 수열의 이웃한 항의 비율은 황금비에 수렴하는데, 이 성질을 사용하여 피보나치 수열의 일반항을 계산하는 식이 있다. 이 식을 코드로 구현하는 경우에도 거듭제곱을 계산하는 부분의 시간복잡도는 빠른 피보나치 변환의 경우와 동일하다.