[Python] 피보나치 수열 7.7배 빠르게 계산하는 방법

파이썬으로 피보나치 수열을
빠르게 구하는 방법

 

피보나치 수열이란

0과 1로 시작하여 이전 두 숫자의 합을 나열하는 것을 말합니다

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

 

피보나치 수열에서 1,000,000번째 수를 계산하기 위한

최적의 방법을 찾아봤습니다

---

이번 포스팅에서 살펴볼 내용은 다음과 같습니다

 

1. 간단한 재귀를 사용하는 방법

2. 재귀와 캐시를 사용하는 방법

3. 반복문을 사용하는 방법

4. 비네 공식을 사용하는 방법

5. 1,000,000번째 숫자 계산

---

 

 

간단한 재귀를 사용하는 방법

파이썬에서 n번째 피보나치 수를 반환하는

매우 간단하고 쉬운 방법입니다

 

def recursiveFib(n):
    if n==1 or n==2:
        return 1

    return recursiveFib(n-1) + recursiveFib(n-2)

 

재귀를 사용하는 방법은 너무 느리고 매우 비효율적입니다

피보나치 수열 35번째 숫자를 구하는데 1.43초가 걸렸습니다

 

캐시를 사용하는 방법

functools 모듈을 사용하면

가장 최근에 사용한 캐시를 사용할 수 있습니다

이를 통해 속도를 개선할 수 있습니다

 

from functools import lru_cache

@lru_cache()
def recursiveFibCached(n):
    if n==1 or n==2:
        return 1
        
    return recursiveFibCached(n-1) + recursiveFibCached(n-2)

 

먼저 함수 앞에 lur_cache를 불러와야합니다

캐시에 저장할 개수를 maxsize로 입력해야 하지만

디폴트값으로 128개가 적용됩니다

 

캐시를 사용하면 0.0002252초만에 200번째 피보나치 수열을 구할 수 있습니다

 

그러나 501번째 숫자를 계산하려고 하면

RecursionError : maximum recursion depth exceeded in comparison

에러가 발생합니다

 

 

 

이때 다음과 같이 depth를 높게 설정하여

문제를 해결할 수 있습니다

 

import sys

sys.setrecursionlimit(5000)

 

1,000번째 피보나치 수를 계산하는데

0.001198초밖에 걸리지 않습니다

 

그러나 1,553번째 숫자를 구하는데 에러가 발생했습니다

아무리 depth를 늘려도 문제가 해결되지 않습니다

 

 

반복문을 사용하는 방법

일반적으로 안좋은 방법이라고 알려진

반복문을 사용하는 방법도 있습니다

 

def iterativeFib(n):
    a, b = 0, 1
    
    for i in range(n):
        a, b = b, a+b
        
    return a

 

매우 빠릅니다

10,000번째 수를 계산하는데 0.0028195초밖에 걸리지 않았습니다

100만번째 수를 계산할 수는 있지만 시간이 조금 많이 걸립니다

 

비네의 식(Binet's formula)을 사용하는 방법

비네 공식은 피보나치 수열의 n번째 수를 구할 수 있는 공식으로

프랑스 수학자 Jacques Philippe Marie Binet의 이름을 따서 비네의 식이라고 불립니다

 

 

여기서 파이(ϕ)는 황금비율과 같습니다

 

 

위 공식을 파이썬으로 구현하면

다음과 같이 작성할 수 있습니다

 

def formulaFib(n):
    root_5 = 5 ** 0.5
    phi = ((1+root_5)/2)
    
    a = ((phi**n) - ((-phi)**-n))/root_5
    
    return round(a)

 

이제 루프없이 답을 즉시 계산할 수 있습니다

하지만 1,475번째 숫자 이상을 계산하려고하면 오류가 발생합니다

OverflowError: (34, result too large)

 

이에 대한 해결방법은 매우 간단합니다

 

import decimal

def formulaFibWithDecimal(n):
    decimal.getcontext().prec = 10000
    
    root_5 = decimal.Decimal(5).sqrt()
    phi = ((1+root_5)/2)
    
    a = ((phi**n) - ((-phi)**-n))/root_5
    
    return round(a)

 

정밀도값을 10,000자리 길이로 설정하고

root_5 값을 변환하여 사용합니다

 

10,000번째 수를 구하는데 0.0692986초 걸렸습니다

음? 반복문을 사용할 때보다 오래 걸렸네요

 

 

1,000,000번째 숫자 계산

n=10,000일때 반복문을 사용하는 방법이 더 빠르다는 것을 알았습니다

Decimal 객체를 생성하여 방정식에 사용하기 때문에 속도가 느려진 것입니다

 

하지만 대략 89,200번째 수를 구할 때부터

비네 공식의 속도는 반복문의 속도보다 빨라지기 시작합니다

 

값을 올바르게 계산하기 위해서는

decimal.getcontext().prec=30000으로 변경하여

Decimal 객체의 정밀도를 높여야 합니다

 

100만번째 피보나치 수를 계산하는데 소요된 시간

반복문을 사용한 방법 : 8.832661초

비네 공식을 사용하는 방법 : 1.151380초

무려 7.7배가 빠릅니다

 

10억번째 피보나치 수를 구하려면

310.8467초가 걸립니다