피보나치 수열을 구하는 효율적인 방법

Fibonacci

피보나치 수열이란 첫 번째와 두 번째 항이 1이고 세 번째 항부터는 이전 두 개의 숫자를 더한 점화식을 갖는 수열이다.

$$\begin{align} & F_{i+1} = F_{i} + F_{i-1} \\ & F_{1} = F_{2} = 1 \end{align}$$

흔히 재귀 함수나 memoization 등으로 한 번쯤 구현해봤겠지만 여기서는 속도에 집중해서 빠르게 구하는 방법들을 알아보자.

 

N번째 수 구하기

1. 무작정 연산 $O(n)$

피보나치수열의 정의에 맞게 초기화를 한 후 모든 항을 구한다.

int byLoop(int n) {
  int f[3] = {0,1,1};
  for(int i = 3; i <= n; i++) {
    f[i%3] = f[(i-1)%3] + f[(i-2)%3];
  }
  return f[n%3];
}

 

2. 행렬을 이용한 연산 $O(log n)$

피보나치수열의 정의를 다시 보면서 행렬식으로 바꿔보자.

$$\begin{align} & F_{i+1} = F_{i} + F_{i-1} \\ & F_{i} = F_{i} + 0 \end{align}$$

 

여기서 각 항을 상수와 $F$ 로 나눠서 보면 행렬의 곱으로 바꿀 수 있다.

$$\begin{align} \begin{bmatrix} F_{i+1} \\ F_{i} \\ \end{bmatrix} & = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} F_{i} \\ F_{i-1} \\ \end{bmatrix} \\ & = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} ^{i} \begin{bmatrix} F_{1} \\ F_{0} \\ \end{bmatrix} \\ & = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} ^{i} \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix} \end{align}$$

이처럼 피보나치수열을 행렬의 식으로 바꾸고 오른쪽 끝 항을 계속 내리다 보면 피보나치의 정의에 있는 $F_{0}$과 $F_{1}$까지 변환했다. 이제 단순히 행렬 계산만 하면 된다. 기존의 수열 연산과 달리 행렬의 n승 연산은 $log_{2}(n)$ 만에 행렬 곱셈으로 아래와 같이 빠르게 구할 수 있다.

struct Matrix {
  int n;
  vector< vector > mat;

  Matrix(int n): n(n) {
    mat.resize(n, vector(n,0));
  }

  Matrix operator*(const Matrix &r) const {
    Matrix res(n);
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        for(int k = 0; k < n; k++) {
          res.mat[i][j] += mat[i][k] * r.mat[k][j];
        }
      }
    }
    return res;
  }
};

Matrix exponentiation(Matrix m, int power) {
  if(power == 0) {
    Matrix id(m.n); 
    for(int i = 0; i < m.n; i++) id.mat[i][i] = 1;
      return id;
  }
  Matrix half = exponentiation(m, power/2);
  return power % 2 ? half * half * m : half * half;
}

 

3. 일반항을 이용한 연산

$$\begin{align} & F_{i+1} = F_{i} + F_{i-1} \\ & F_{1} = F_{2} = 1 \end{align}$$

위 두 개의 식을 이용해서 $F_{i}$ 의 일반항을 구해보자.

 

$$\begin{align} & \alpha + \beta = 1 \\ & \alpha \beta = -1 \end{align}$$

새로운 방정식을 유도하기 위해 위와 같은 $\alpha$와 $\beta$ 를 정의한다.

 

$$\begin{align} F_{i+1} - F_{i} - F_{i-1} & = 0 \\ F_{i+1} - \alpha F_{i} & = \beta (F_{i} - \alpha F_{i-1}) \\ & = \beta ^{2} (F_{i-1} - \alpha F_{i-2}) \\ & ... \\ & = \beta ^{i-1} (F_{2} - \alpha F_{1}) \\ & = \beta ^{i-1} (1 - \alpha) \end{align}$$

 

위와 비슷하게 방정식을 또 하나 유도한다.

$$\begin{align} F_{i+1} - F_{i} - F_{i-1} & = 0 \\ F_{i+1} - \beta F_{i} & = \alpha (F_{i} - \beta F_{i-1}) \\ & = \alpha ^{2} (F_{i-1} - \beta F_{i-2}) \\ & ... \\ & = \alpha ^{i-1} (F_{2} - \beta F_{1}) \\ & = \alpha ^{i-1} (1 - \beta) \end{align}$$

 

이렇게 새로운 방정식 두 개를 유도했다.

$$\begin{align} & F_{i+1} - \alpha F_{i} = \beta ^{i-1} (1 - \alpha) \\ & F_{i+1} - \beta F_{i} = \alpha ^{i-1} (1 - \beta) \end{align}$$

 

위 식에서 아래식을 빼고 적절히 식을 정리하면 아래식이 된다.

$$\begin{align} F_{i} & = \frac{1}{\alpha - \beta} {\alpha ^{i-1}(1 - \beta) - \beta ^{i-1}(1 - \alpha)} \\ & = \frac{\alpha ^{i} - \beta ^{i}}{\alpha - \beta} \end{align}$$

 

이로써 $F_{i}$ 의 식을 F꼴이 아닌 $\alpha$와 $\beta$로 이루어진 일반항으로 나타내었다.
위에 정의한 $\alpha$와 $\beta$는 간단한 이차방정식이므로 근을 쉽게 구할 수 있다.

$$\begin{align} & \alpha = \frac{1+\sqrt{5}}{2} \\ & \beta = \frac{1-\sqrt{5}}{2} \end{align}$$

 

이를 유도했던 식에 대입하면 완성이다.

$$F_{i} = \frac{1}{\sqrt{5}} {(\frac{1+\sqrt{5}}{2})^{n} - (\frac{1-\sqrt{5}}{2})^{n}}$$

double byFormula(int n) {
  double sqrt5 = sqrt(5);
  return (1/sqrt5) * (pow((1+sqrt5)/2, n) - pow((1-sqrt5)/2, n));
}

 

주의

피보나치는 n = 48 만 되어도 integer(4byte) 범위를 초과하는 무시무시한 수열이다.
따라서 위 예제에서는 전혀 고려하지 않았지만 연산에 의한 오버플로우에 항상 주의해야 한다.