피보나치 수열

• 개요

과연 크기가 큰 N 번째 피보나치 수열을 구하는 알고리즘 중 어느것이 가장 효율적이고 빠를까?

Recursion 과 DP를 배우고 익히는 도중에 과연 어느 알고리즘이 시간복잡도가 가장 빠를까? 라는 호기심이 생겼고. 내가아는 모든 알고리즘을 구현해봤고, 시간을 측정해보았다. 하지만 메모리는 측정하는법을 모르기때문에 그나마 입력값이 큰 백준 10826번 문제의 AC를 받은 메모리 크기를 사용하겠다.

실험과정 정리 :

1. 입력의 크기 (수).

2. 해당 수의 피보나치 수열의 값.

3. 연산 횟수. (야매주의)

4. 연산에 걸린 시간 (ms단위)

5. 연산에 걸린 시간 (Second 단위)

• 1번 실험군

F(n) = F(n-1) + F(n-2)를 리스트로 구현한 알고리즘

from collections import deque
import time,sys
sys.set_int_max_str_digits(0)

count = 0
a = int(input())
l = deque([0,1])

start_time = time.time()	# 측정 시작
for i in range(2,a+1):
    count += 1
    l.append(l[i-2] + l[i-1])
end_time = time.time()		# 측정 종료

res = l[-1]
print('값: ',res)
print('연산 횟수: ',count)
print((end_time - start_time)*1000,"ms")
print((end_time - start_time),"sec")

입력한 수 :  500000
값: 2955561408269515125990 ... 8518469780453125
연산 횟수:  499999
3816.69282913208 ms
3.81669282913208 sec

• 시간복잡도 : O(n)
• 공간복잡도 : O(n)

+) 알고리즘 공부 초기에 무작정 피보나치 수열을 구현해본 옛날 코드다.
나름 속도도 준수한거같고 바로밑에 서술할 Recursion 보다 훨씬 좋은거같음.

• 2번 실험군

피보나치를 들으면 가장먼저 배우는 알고리즘이자
이 알고리즘을 배우면 가장먼저 피보나치를 떠올리는
재귀함수 형식

import time
count = 0

def recursion(n):
    global count
    count += 1
    if n <= 1:
        return n
    return recursion(n-1) + recursion(n-2)



n = int(input())
start_time = time.time()
res = recursion(n)
end_time = time.time()
print('값: ',res)
print('연산 횟수: ',count)
print((end_time - start_time)*1000,"ms")
print((end_time - start_time),"sec")

35
값:  9227465
연산 횟수:  29860703
1477.9107570648193 ms
1.4779107570648193 sec

• 시간복잡도 : O(2^n)
• 공간복잡도 : O(n)

+) 일단 이 친구는 시간복잡도부터 어지럽다.
메모리를 측정해보려고했는데 가장 기본적인 피보나치 수열, 테케 최댓값이 45인것도 시간제한이 걸려서 메모리 사용량을 측정할수가 없었다.

그냥 이제 수학적으로만 계산을했을때, 입력값에 1000을 넣으면

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

번의 연산을 하고
파이썬이 보통 채점서버 기준으로 1초에 20,000,000번의 연산을 한다고 알려져있으니

535754303593133660474212524530000905280702405852766803721875194185175525562468061246599189407847929063797336458776573412593572642846157021799228878734928740196728388741211549271053730253118557093897709107652323749179097063369938377958277197303853145728559823884327108383021491582631219341860283

초가 걸린다고 보면될듯

그러면 이론상

16988657521344927652401907491558155569009565899040613767151801868184268092826566137937616861685272614332421079654254579115675332284813385014301558920937289583754107081926712348971538554352569658529849076481192158828863988117857765754019942268471730184076771877803983333895750556832517773년 247일 23시간 10분 56초

가 걸림

나가라 그냥 너는.

• 3번 실험군

이 코드는 Iterative Dynamic Programming을 사용하는 방식을 코드로 구현한것이며, 계산결과를 memory라는 변수에 저장하는 메모이제이션을 구현하고있는 알고리즘이다.

import time,sys
sys.set_int_max_str_digits(0)   # increase integer limit
count = 0
def dp(n):
    global count
    count += 1
    memory = [1,1]
    if n < 0:
        return 0
    elif n < 2:
        return memory[n]
    else:
        for i in range(2, n+1):
            memory.append(memory[i-1] + memory[i-2])
            count += 1
        return memory[n]
n = int(input())-1
start_time = time.time()    # 측정 시작
res = dp(n)
end_time = time.time()		# 측정 종료
print('값: ',res)
print('연산 횟수: ',count)
print((end_time - start_time)*1000,"ms")
print((end_time - start_time),"sec")

입력한 수 :  500000
값 : 2955561408269515125990 ... 8518469780453125
연산 횟수:  499999
4598.466634750366 ms
4.598466634750366 sec

• 시간복잡도 : O(n)
• 공간복잡도 : O(n)

+) DP를 배우고 연습문제로 피보나치에 적용할때 가장 기본적으로 구현하는 방식이다. 딱히 코멘트 달게 없음.

그런데 초창기때 짰던 1번 실험군이 이 코드랑 비슷한 성능을 보이는데 이게무슨?

• 4번 실험군

이 코드는 행렬의 곱셈을 활용한 것을 코드로 구현한 것이다.
피보나치의 점화식과 이를 행렬의 곱으로 표현 및 최적화 하는과정은 아래와 같다.

import time
count = 0
def fibo(n):
    area = 2
    identity_element = [[1, 0], [0, 1]]
    sized = [[1, 1], [1, 0]]

    def multiple_square(a, b, size=area):
        new = [[0 for _ in range(size)] for _ in range(size)]

        for i in range(size):
            for j in range(size):
                for k in range(size):
                    new[i][j] += a[i][k] * b[k][j]
        return new

    def multiplied(n):
        matrix = identity_element.copy()
        k = 0
        tmp = sized.copy()
        while 2 ** k <= n:
            if n & (1 << k) != 0:
                matrix = multiple_square(matrix, tmp)
            k += 1
            tmp = multiple_square(tmp, tmp)
        return matrix
    return multiplied(n)[1][0]

n = int(input())
start_time = time.time()
res = fibo(n)
end_time = time.time()
print('값:',res)
print('연산 횟수:',count)
print((end_time - start_time)*1000,"ms")
print((end_time - start_time),"sec")

입력한 수 : 500000
값 : 2955561408269515125990 ... 8518469780453125
연산 횟수: log(500,000) ≈ 19
92.60320663452148 ms
0.09260320663452148 sec

• 시간복잡도 : O(log N)
• 공간복잡도 : O(1)

연산횟수는 사실 log를 사용해야하기때문에 여기서는 어디에 count를 넣어도 정확하게 측정이 불가능해서 아래에 수식을 따로 적어놨다.

가장 흥미로운 방법이다.
사실 이 방법은 행렬 곱셈과 Hu-Shing Algorithm에 대해 배워보면서 관련 논문이나 자료를 찾아보다가 발견했는데, 이 알고리즘은 피보나치 수열을 행렬의 거듭제곱으로 나타내는 방법이다.

예를 들어 x^16 을 구해야 한다고 하자. 그냥 x로 시작해서 거기에 x를 열다섯 번 곱해도 된다. 단 네 번의 곱셈으로 같은 답을 구하는 것도 가능하다. 매 단계마다 중간 결과의 제곱을 취하는 방식으로, 차례로 x^2, x^4, x^8, x^16 을 구하면 되는 것이다.
그러면 일반적으로 x 를 16번 곱하는 방식인 O(n)을 O(log n)으로 최적화를 할 수 있다.
그렇다면 수가 커지면 커질수록 효율을 더 체감할 수 있을것이다.

그러면 실험을 한가지만 더 해보자.
5,000,000번째의 피보나치 수가 궁금하지않나?

입력한 수: 5000000
연산 횟수 : log(5,000,000) ≈ 23
5313.332319259644 ms
5.3133323192596436 sec

값을 여기에 적기엔 수가 너무커서 불가능할거같다.
https://www.programiz.com/python-programming/online-compiler/
여기가 유일하게 sys.set_int_max_str_digits(0) attribute를 지원하는 파이썬 온라인 컴파일러이니 접속해서

import time,sys
sys.set_int_max_str_digits(0)
def fibo(n):
    area = 2
    identity_element = [[1, 0], [0, 1]]
    sized = [[1, 1], [1, 0]]

    def multiple_square(a, b, size=area):
        new = [[0 for _ in range(size)] for _ in range(size)]

        for i in range(size):
            for j in range(size):
                for k in range(size):
                    new[i][j] += a[i][k] * b[k][j]
        return new

    def multiplied(n):

        matrix = identity_element.copy()
        k = 0
        tmp = sized.copy()
        while 2 ** k <= n:
            if n & (1 << k) != 0:
                matrix = multiple_square(matrix, tmp)
            k += 1
            tmp = multiple_square(tmp, tmp)
        return matrix
    return multiplied(n)[1][0]

print(fibo(5000000))

를 실행하고 결과값을 직접보길바란다.

값의 자릿수만 1,044,239자리다 어지럽네 그냥..
저 큰수를 계산하는데 5.3초가 걸렸다.
log n 시간복잡도는 그냥 신이다.
이 방법으로 풀수있는 문제가 백준 2749번 문제이다.

• 5번 실험군

n번째 피보나치 수를 구하는 식 즉 Binet's Fibonacci Number Formula를 코드로 구현한 방법이다.

식의 유도과정과 증명은
https://medium.com/@satoshihgsn/what-is-the-general-term-for-the-fibonacci-sequence-42ffc012dd42
여기서 확인할수있다.

from decimal import Decimal, getcontext
import time,sys

count = 0

getcontext().prec = 104500	# 소수점 아래 104500 자리까지 정밀도 설정

def fibonacci(n):
    global count
    count += 1
    sqrt_5 = Decimal(5).sqrt()
    phi = (1 + sqrt_5) / 2
    psi = (1 - sqrt_5) / 2
    return int((phi ** n - psi ** n) / sqrt_5)


n = int(input())
start_time = time.time()
res = fibonacci(n)
end_time = time.time()
print('값:', res)
print('연산 횟수:', count)
print((end_time - start_time) * 15000, "ms")
print((end_time - start_time), "sec")

입력한 수: 5000000
연산 횟수: 1
1036.581039428711 ms
1.036581039428711 sec

• 시간복잡도 : O(log n)
• 공간복잡도 : O(log n)

이 코드에 대해서도 할말이 많다.
이 코드에 사용된 Binet's Fibonacci Number Formula는 부동소수점 수를 다루고 파이썬에서는 부동소수점 수가 내부적으로는 C의 double타입을 사용하고 이는 고정된 크기의 용하기때문에 큰 수에 대해 결과값이 제대로 나오지않는다.

다시말하면, 계산할때 무한소수등 무한반복이 일어나는 계산이 발생하면 컴퓨터의 메모리도 한계가 있으므로 결국 컴퓨터는 이 무한반복 되는 값에서 근사값을 저장하게 되고 바로 여기서 오차가 발생하게 되는 것이다. 컴퓨터는 부동소수점을 이용해서 2진수로 근사값을 저장하고, 이 때문에 C의 double타입 끼리의 저장 또는 연산에서 정확한 계산이 일어나지 않는다는 것이다.

그래서 파이썬의 부동소수점 수에 대한 오버플로우 제한은 내부적으로 사용하는 C의 double타입의 제한으로 결정이되서
직접적으로 제한을 푸는등으로 해결하는건 어렵다.

그러나 부동소수점 수의 정밀도를 높이는 방법은 존재한다.

from decimal import Decimal, getcontext
getcontext().prec = 104500	# 소수점 아래 104500 자리까지 정밀도 설정
sqrt_5 = Decimal(5).sqrt()

Python의 decimal모듈 또는 fractions모듈을 사용하는것이다.

자세한 사용방법은
https://docs.python.org/3.9/library/decimal.html
아래의 링크에서 확인 가능하다.
우리가 공통적으로 실험에 사용하는 N번째 피보나치수열은
500,000 번째이므로
그 수열은 104495의 자릿수를 가지고있다.
하지만 우리가 사용하는 Binet's Fibonacci Number Formula에서는 Square root 즉 제곱근을 사용하기때문에 소수점에서의 연산을 하게되는것이고 최소 소수점 아래 104495 자리까지 정밀도를 설정을 해주면 값을 볼수있다는것이다.

값이 맞다는게 아니라 값을 볼수있다?
예를 들어

getcontext().prec = 100000

이렇게 설정을 해줬다고하자.

그러면 100000자리까지는 정상적으로 출력이 되고 그 다음부터는 0이 출력되는 모습을 볼수있다.
그러면 500,000번째 피보나치 수열의 자릿수가 104495니까 '적어도' 출력된 값을 보려면 prec값을 104495로 설정해줘야 한다는것이다.

104495로 설정했을때 출력은 끝까지 잘되는것을 볼수있다.
하지만 실제 피보나치 수열과 같은지 판단했을때는 False가 출력이되니 실제로는 틀린값이 출력되고있는거다.

이 이유또한, 부동소수점 숫자는 H/W에서 2진수 분수로 표현되고 어떤 유한한 비트 수에서라도 멈추면 근사치를 얻게되고
파이썬은 저장된 이진 근사치의 실제 10진수값을 근사화하여 출력하기때문에 생각보다 많은 소수점아래에서 오차가 발생하는것이고, 특히 Binet's Fibonacci Number Formula에서 제곱근을 사용하고있고, 제곱근은 정확한 결과를 얻기 위해서는 무한한 정밀도가 필요한 연산이므로, 부동소수점 숫자를 사용하여 계산할 때 오차는 필연적으로 발생하기 때문이다.

https://docs.python.org/3/tutorial/floatingpoint.html

getcontext().prec = 104500

이 경우일때 정확한 값을 출력하는 걸 확인할수 있었다.

정리를 하면 이번 글에서는 피보나치 수열 알고리즘을 구하는 5가지 방법을 알아보았다. 이 글을 쓰기위해 여러가지 정보를 찾아보고 논문도 찾아보고하는 과정에서 정말 재밌었다. 코드를 구현하고 시간복잡도 차이가 극명하게 보일때마다 쾌감을 느끼기도했다. 코드 구현시간 다 포함해서 거의 도합 32시간정도 걸린거같은데 1학기때 배운 CS와 파이썬을 전체적으로 한번 복기해보는 느낌을 느껴서 오히려 괜찮은 경험이였다.

아 또 밤샜네ㅅㅂ