C++를 이용한 피보나치 수열 구현 (fibonacci)

 이 포스트의 목적은 가끔 예제로 이용하는 피보나치 수열을 구현하는 방법에 대한 포스트입니다. 만들어 보니 7가지가 나왔으며, 버전에 따라 재귀 호출, 메모리제이션 등을 이용해 최적화하는 방식으로 구현됩니다.

 먼저 피보나치수열을 알아봐야죠. 피보나치수열은 아래 규칙을 따르는 수열입니다.

 

$$f_0 = 0$$

$$f_1 = 1$$

$$f_n = f_{n-1} + f_{n-2} \quad ( n \in\left \{2,3,4,\cdots\right\} )$$

 

 구조는 단순하지만 구현 시 오버플로우와 중복 연산에 주의해야 합니다. 그럼 먼저 간단히 구현해 보겠습니다. 별다른 소프트웨어 공학의 기술이 들어 가진 않지만 설계 시엔 약간 두통을 유발합니다.

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char ** argv){
    int n = atoi(argv[1]);

    int b1 = 0;
    int b2 = 1;
    int c = n > 0 ? 1 : 0;

    for(int i = 2 ; n > i ; i++){
	b1 = b2;
	b2 = c;
	c = b1+b2;
    }

    cout << c <<endl;

    return 0;
}

 n은 몇 번째 피보나치 수를 원하는지 입력받는 변수이고,  b1, b2, c 세 가지 변수가 이용됩니다. 각각 f_(n-2), f_(n-1), f_n을 의미합니다. 특수한 상황으로 n이 2보다 작은 경우 for 루프는 동작하지 않습니다. 이 경우에는 c가 0인지 1인지 알아야 하니 n에 따라 선택적으로 지정합니다. (n이 0이나 1이면, c가 출력되어야 하니 0 혹은 1로 설정하고, 2 이상인 경우, f_2로 설정되어야 하니 1이 됩니다.)

 이후의 과정은 for loop가 구동된 뒤, c값을 출력합니다. 구동 결과는 아래 스냅숏과 같습니다.

 이번엔 두 번째 예제로 넘어갑니다. 소프트웨어 공학 기법 중 재귀 호출을 이용합니다. fibonacci함수를 만들고, 함수 안에서 함수를 호출합니다.

#include <iostream>
#include <vector>

using namespace std;

int fibonacci(int i){
    if(2 > i){
	return i;
    }

    return fibonacci(i-1) + fibonacci(i-2);
}

int main(int argc, char ** argv){
    int n = atoi(argv[1]);

    cout << fibonacci(n) << endl;

    return 0;
}

 두 번째 예제는 가독성이 크게 향상됩니다. 첫 번째 예제에서는 코드 분석이 조금 필요하지만 두번째 예제는 그렇지 않죠. 간단한 문법만 알면 피보나치 수열을 구하는 코드라는 것을 알게됩니다. 첫번째 예제 보다 가독성이 높으니 좋은 코드(?) 겠죠. 이 코드의 구동 결과는 아래 스냅숏과 같습니다.

 결과는 첫 번째 예제와 같습니다. 하지만 한가지 문제가 생기게 됩니다. f_40을 계산하는데 첫번째 예제는 3 msec가 필요했습니다. 하지만 두 번째 예제는 481 msec가 필요합니다. cpu사용율도 높았습니다. 코드의 가독성은 향상되지만 시간은 오래 걸립니다. 원인은 중복 연산입니다. 간단히 표현하면 f_5를 연산하기 위해 fibonacci 함수는 총 15회 호출됩니다. 중복 연산에 대한 포스트는 근 시일에 추가하겠습니다.

 

 그럼 3번째 예제로 넘어가죠. 여기부터는 중복 연산 문제를 해결하기 위해서 메모이제이션 기술을 이용하겠습니다. 메모이제이션에 대한 설명은 다른 글로 대신하겠습니다.

2021.03.25 - [Program Language and Algorithm] - 메모이제이션 : 중복 연산 해결 (러시안 페인트공 알고리듬)

메모이제이션 : 중복 연산 해결 (러시안 페인트공 알고리듬)

 이번 예제는 첫 번째 예제를 변형합니다. 첫번째 예제의 경우, 이런 기술이 필요 없을 수도 있습니다. 하지만 너무 많은 변수 업데이트 작업이 요구되니, 메모이제이션으로 해결합니다. 이후의 결과들은 출력 스냅숏을 제외하였습니다.

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char ** argv){
    int n = atoi(argv[1]);

    vector<int> arr(n+1, 0);

    arr[1] = 1;

    for(int i = 2 ; n >= i ; i++){
	arr[i] = arr[i-1] + arr[i-2];
    }

    cout << arr[n] <<endl;

    return 0;
}

 메모리제이션을 위해 vector를 만들고, 초기화한 후, for loop를 이용해 수치를 업데이트합니다. 첫 번째 예제보다 간결해지고, for loop가 끝났을 때 0부터 n까지의 수열 값을 모두 가지게 된다는 장점이 있을 수 있습니다. 하지만 메모리 사용량이 증가한 단점이 생기죠. 대부분의 경우, 메모리제이션은 중복 연산을 방지해서 더 좋은 성능을 보이지만 메모리가 부족한 환경에서는 사용이 어렵기도 합니다.

 이번엔 두 번째 예제를 변형해서 네 번째 예제를 만듭니다. 함수가 이용되어야 하니, 지역변수로 만들어진 arr vector는 전역으로 변환됩니다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr;

int fibonacci(int i){
    if(-1 == arr[i]){
	arr[i] = fibonacci(i-1) + fibonacci(i-2);
    }
    return arr[i];
}

int main(int argc, char ** argv){
    int n = atoi(argv[1]);

    arr.resize(n+1);

    for(int i = 0 ; n >= i ; i++){
	arr[i] = -1;
    }

    arr[0] = 0;
    arr[1] = 1;

    cout << fibonacci(n) << endl;

    return 0;
}

 arr이 전역 변수가 되었으니, 초기화가 복잡해집니다. fibonacci 함수가 i번째 변수를 계산했는지 알 수 있도록, 초기 값은 -1로 설정되고, i번째 변수가 계산된 이후라면, 중복 연산 없이 결과를 반환합니다.

 다섯 번째 예제에서는 네 번째 예제를 계량합니다. 전역 변수는 편리하지만, 많은 문제를 발생시킬 수 있습니다. arr을 지역 변수로 변환해 보겠습니다.

#include <iostream>
#include <vector>

using namespace std;

int fibonacci(int i, vector<int> &arr){
    if(-1 == arr[i]){
	arr[i] = fibonacci(i-1, arr) + fibonacci(i-2, arr);
    }
    return arr[i];
}

int main(int argc, char ** argv){
    int n = atoi(argv[1]);

    vector<int> arr(n+1, -1);

    arr[0] = 0;
    arr[1] = 1;

    cout << fibonacci(n, arr) << endl;

    return 0;
}

 arr이 지역 변수가 되었으니 fibonacci함수의 입력 변수도 둘이 됩니다. call by reference로 arr을 전달해서, 메모리 사용량도 줄이고, arr 값이 제대로 업데이트 되게 만들어 줍니다.

 여섯 번째 예제는 세 번째 예제를 변형합니다. 배열의 index 접근은 가독성이 뛰어나지만, 하드웨어 입장에서는 리소스 소비를 늘릴 수 있습니다. 이를 해결하기 위해 iterator를 이용합니다.

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char ** argv){
    int n = atoi(argv[1]);

    vector<int> arr(n+1, 0);

    arr[1] = 1;

    vector<int>::iterator i1 = arr.begin();
    vector<int>::iterator i2 = i1+1;
    vector<int>::iterator i3 = i2+1;
    
    while(i3 != arr.end()){
	*i3 = *i1 + *i2;
	i1++;
	i2++;
	i3++;
    }

    cout << arr[n] <<endl;

    return 0;
}

 하드웨어가 좋아하는 포인터 사용이죠. 일반적으로 이용되는 랩탑이나 데스크 탑은 높은 성능의 하드웨어 아키텍처와 컴파일러 이용하기 때문에, 성능 발전에 큰 도움이 없습니다. 하지만 저사양 컴퓨팅 시스템에서는 가독성이 떨어져도 하드웨어가 이해하기 쉽게 만들어 주는 게 성능 향상에 도움이 됩니다. 위 예제를 간단히 설명하면 세 손가락을 접은 아이에게 네 번째 손가락을 접으라고 하기보다, 다음 손가락을 접으라고 하는 형식입니다. (아마도 아이가 이해하기 더 쉽겠죠.)

 저사양 컴퓨팅 시스템을 이용하실게 아니라면 굳이 이런 최적화까지 하실 필요는 없습니다.

 

 그럼 이 포스팅의 마지막 예제입니다. 이번엔 위 예제들과 방식을 다르게 합니다. n번째 피보나치수열 값을 얻기 위해 꼭 0번째부터 계산할 필요는 없습니다. 아래 항등식은 n번째 피보나치 수를 계산하는 항등식입니다. (출처 : 위키피디아)

$$F_n = { \varphi ^n - \left( 1 - \varphi \right)^n \over \sqrt{5} } = { 1 \over \sqrt{5} } \left( \left( {1 + \sqrt{5} \over 2} \right)^n - \left( { 1 - \sqrt{5} \over 2 } \right)^n \right) = { \left( 1 + \sqrt{5} \right)^n - \left( 1 - \sqrt{5} \right)^n \over 2^n \sqrt{5} }$$

위 수식을 이용하면 메모리제이션을 이용할 필요 없이 쉽게 원하는 값을 알아낼 수 있습니다. 코드는 아래 코드와 같습니다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(int argc, char ** argv){
    int n = atoi(argv[1]);

    float a = 1./sqrt(5.);
    float b = (1 + sqrt(5.))/2;
    float c = (1 - sqrt(5.))/2;

    cout << static_cast<int>(a * (pow(b,n) - pow(c,n))) << endl;;
}

 항등식의 마지막 등식이 아니라 두 번째 등식을 이용한 건 pow 함수의 사용 횟수가 줄기 때문입니다. 마지막 예제의 장점은 n이 1이든 100이든 동일한 시간에 연산이 종료된다는 것입니다. 이건 만약 이상 적인 컴퓨터(오버플로우가 없는)를 이용한다고 했을 때 1억 번째 수열 값을 계산하기 위해 1억 번의 연산을 하지 않는다는 장점을 가지게 됩니다. 하지만 현실적으로는 오버플로우 문제로 인해 계산 가능한 n의 값이 제한적이며, 실수를 사용해야 해서 오히려 계산 가능 범위가 줄어들게 됩니다.

 그럼 모든 예제를 설명하였으니, 마지막으로 계산 가능한 n의 크기에 대해서 설명하고, 마치겠습니다.

• 32비트 정수 : 46
• 32비트 실수 : 40
• 64비트 정수 : 92
• 64비트 실수 : 81

 변수의 오버 플로우로 인해 컴퓨팅 시스템은 위 순서 이상의 피보나치수열을 계산할 수 없습니다. (실수형 계산으로 근삿값을 구할 수는 있습니다.) 위 수치는 기본 int, long long, float , double을 사용한 수치입니다. 컴파일러나 컴퓨팅 시스템에 따라 달라질 수 있습니다. 

 

 그럼 긴 글 읽어 주셔서 감사합니다.