큰 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)을 사용한다. 빠른 피보나치 변환은 피보나치 수열의 점화식을 행렬로 처리하는 것이다.
순수 파이썬에서는 아직 행렬을 제공하지 않지만, 행렬의 곱셈과 거듭제곱을 계산하는 함수를 조합하여 아래와 같이 구현한다.
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() 를 사용하여 허용자릿수를 늘려주면 된다.
참고로 피보나치 수열의 이웃한 항의 비율은 황금비에 수렴하는데, 이 성질을 사용하여 피보나치 수열의 일반항을 계산하는 식이 있다. 이 식을 코드로 구현하는 경우에도 거듭제곱을 계산하는 부분의 시간복잡도는 빠른 피보나치 변환의 경우와 동일하다.