콘텐츠로 건너뛰기
Home » Fast Fibonacci Transform

Fast Fibonacci Transform

큰 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() 를 사용하여 허용자릿수를 늘려주면 된다.

참고로 피보나치 수열의 이웃한 항의 비율은 황금비에 수렴하는데, 이 성질을 사용하여 피보나치 수열의 일반항을 계산하는 식이 있다. 이 식을 코드로 구현하는 경우에도 거듭제곱을 계산하는 부분의 시간복잡도는 빠른 피보나치 변환의 경우와 동일하다.

태그: