피보나치 수¶

피보나치 수열은 다음과 같이 정의됩니다:

$$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$$

수열의 처음 몇 원소(OEIS A000045)는 다음과 같습니다:

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

성질¶

피보나치 수에는 흥미로운 성질이 많습니다. 그중 몇 가지는 다음과 같습니다:

카시니 항등식:

$$F_{n-1} F_{n+1} - F_n^2 = (-1)^n$$

이는 귀납법으로 증명할 수 있습니다. Knuth의 한 줄짜리 증명은 아래의 2x2 행렬 형태에서 행렬식을 취하여 얻어집니다.

"덧셈" 규칙:

$$F_{n+k} = F_k F_{n+1} + F_{k-1} F_n$$

앞의 항등식을 $k = n$인 경우에 적용하면 다음을 얻습니다:

$$F_{2n} = F_n (F_{n+1} + F_{n-1})$$

이로부터 임의의 양의 정수 $k$에 대하여 $F_{nk}$가 $F_n$의 배수임을 귀납법으로 증명할 수 있습니다.
$n \ge 3$일 때는 그 역도 성립합니다: $F_m$이 $F_n$의 배수이면 $m$은 $n$의 배수입니다.
GCD 항등식:

$$GCD(F_m, F_n) = F_{GCD(m, n)}$$

피보나치 수는 유클리드 알고리즘에 대해 가능한 최악의 입력입니다(유클리드 알고리즘의 라메 정리를 참고하십시오)

피보나치 부호화¶

이 수열을 사용하여 양의 정수를 이진 부호어로 부호화할 수 있습니다. 제켄도르프 정리에 따르면, 모든 자연수 $n$은 피보나치 수의 합으로 유일하게 표현될 수 있습니다:

$$N = F_{k_1} + F_{k_2} + \ldots + F_{k_r}$$

이때 $k_1 \ge k_2 + 2,\ k_2 \ge k_3 + 2,\ \ldots,\ k_r \ge 2$를 만족합니다(즉, 이 표현에서는 연속된 두 피보나치 수를 사용할 수 없습니다).

따라서 모든 수는 피보나치 부호화로 유일하게 부호화될 수 있습니다. 그리고 이 표현을 이진 부호 $d_0 d_1 d_2 \dots d_s 1$로 나타낼 수 있으며, 여기서 $d_i$는 표현에 $F_{i+2}$가 사용되면 $1$입니다. 부호어의 끝을 나타내기 위해 부호 뒤에 $1$을 덧붙입니다. 연속된 두 개의 1비트가 나타나는 곳은 이곳뿐이라는 점에 유의하십시오.

$$\begin{eqnarray} 1 &=& 1 &=& F_2 &=& (11)_F \\ 2 &=& 2 &=& F_3 &=& (011)_F \\ 6 &=& 5 + 1 &=& F_5 + F_2 &=& (10011)_F \\ 8 &=& 8 &=& F_6 &=& (000011)_F \\ 9 &=& 8 + 1 &=& F_6 + F_2 &=& (100011)_F \\ 19 &=& 13 + 5 + 1 &=& F_7 + F_5 + F_2 &=& (1001011)_F \end{eqnarray}$$

정수 $n$의 부호화는 간단한 탐욕 알고리즘으로 수행할 수 있습니다:

$n$ 이하인 수를 찾을 때까지 피보나치 수를 가장 큰 것부터 가장 작은 것 순으로 순회합니다.
이 수가 $F_i$였다고 합시다. $n$에서 $F_i$를 빼고 부호어의 $i-2$ 위치에 $1$을 놓습니다(가장 왼쪽 비트부터 가장 오른쪽 비트까지 0부터 인덱싱합니다).
나머지가 없을 때까지 반복합니다.
부호어의 끝을 나타내기 위해 마지막에 $1$을 덧붙입니다.

부호어를 복호화하려면 먼저 마지막 $1$을 제거합니다. 그다음 $i$번째 비트가 설정되어 있으면(가장 왼쪽 비트부터 가장 오른쪽 비트까지 0부터 인덱싱합니다) 수에 $F_{i+2}$를 더합니다.

$n^{\text{th}}$ 피보나치 수에 대한 공식¶

닫힌 형태의 식¶

Moivre가 이미 알고 있었지만 "Binet의 공식"으로 알려진 공식이 있습니다:

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

이 공식은 귀납법으로 쉽게 증명할 수 있습니다. 또한 생성 함수의 개념을 이용하거나 함수 방정식을 풀어서 유도할 수도 있습니다.

두 번째 항의 절댓값은 항상 $1$보다 작고 매우 빠르게(지수적으로) 줄어든다는 것을 바로 알 수 있습니다. 따라서 첫 번째 항의 값만으로도 "거의" $F_n$입니다. 이는 엄밀하게 다음과 같이 쓸 수 있습니다:

$$F_n = \left[\frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n}{\sqrt{5}}\right]$$

여기서 대괄호는 가장 가까운 정수로 반올림한다는 뜻입니다.

이 두 공식은 소수를 다룰 때 매우 높은 정밀도가 필요하므로 실제 계산에서는 거의 쓸모가 없습니다.

선형 시간에 피보나치 수 구하기¶

$n$번째 피보나치 수는 $n$까지 수를 하나씩 계산하여 $O(n)$에 쉽게 구할 수 있습니다. 하지만 뒤에서 살펴보듯이 더 빠른 방법도 있습니다.

$F_n = F_{n-1} + F_{n-2}$ 공식을 이용하는 반복적 접근법에서 시작할 수 있습니다. 구현할 때는 기저 사례인 $F_0$과 $F_1$에서 시작하여 가장 최근의 두 값만 저장하면 됩니다.

int fib(int n) {
    int a = 0;
    int b = 1;
    for (int i = 0; i < n; i++) {
        int tmp = a + b;
        a = b;
        b = tmp;
    }
    return a;
}

이렇게 하면 $O(n)$ 시간과 $O(1)$ 추가 메모리를 사용하는 선형 해법을 얻습니다.

행렬 형태¶

$(F_n, F_{n-1})$에서 $(F_{n+1}, F_n)$으로 넘어가기 위해 선형 점화식을 2x2 행렬 곱셈으로 나타낼 수 있습니다:

$$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} F_n + F_{n-1} \\ F_{n} \end{pmatrix} = \begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix} $$

이렇게 하면 점화식을 반복하는 과정을 행렬 곱셈의 반복으로 다룰 수 있으며, 행렬 곱셈의 반복에는 유용한 성질이 있습니다. 특히,

$$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} = \begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix} $$

여기서 $F_1 = 1, F_0 = 0$입니다. 실제로 다음이 성립하므로

$$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix} $$

행렬을 직접 사용할 수 있습니다:

$$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} $$

따라서 $F_n$을 $O(\log n)$ 시간에 구하려면 행렬을 n제곱해야 합니다. (이진 거듭제곱 참조)

struct matrix {
    long long mat[2][2];
    matrix friend operator *(const matrix &a, const matrix &b){
        matrix c;
        for (int i = 0; i < 2; i++) {
          for (int j = 0; j < 2; j++) {
              c.mat[i][j] = 0;
              for (int k = 0; k < 2; k++) {
                  c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
              }
          }
        }
        return c;
    }
};

matrix matpow(matrix base, long long n) {
    matrix ans{ {
      {1, 0},
      {0, 1}
    } };
    while (n) {
        if(n&1)
            ans = ans*base;
        base = base*base;
        n >>= 1;
    }
    return ans;
}

long long fib(int n) {
    matrix base{ {
      {1, 1},
      {1, 0}
    } };
    return matpow(base, n).mat[0][1];
}

빠른 더블링 방법¶

위의 행렬 식을 $n = 2\cdot k$에 대해 전개하면

$$ \begin{pmatrix} F_{2k+1} & F_{2k}\\ F_{2k} & F_{2k-1} \end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^{2k} = \begin{pmatrix} F_{k+1} & F_{k}\\ F_{k} & F_{k-1} \end{pmatrix} ^2 $$

다음과 같은 더 간단한 방정식을 얻을 수 있습니다:

$$ \begin{align} F_{2k+1} &= F_{k+1}^2 + F_{k}^2 \\ F_{2k} &= F_k(F_{k+1}+F_{k-1}) = F_k (2F_{k+1} - F_{k})\\ \end{align}.$$

따라서 위의 두 방정식을 사용하면 다음 코드로 피보나치 수를 쉽게 계산할 수 있습니다:

pair<int, int> fib (int n) {
    if (n == 0)
        return {0, 1};

    auto p = fib(n >> 1);
    int c = p.first * (2 * p.second - p.first);
    int d = p.first * p.first + p.second * p.second;
    if (n & 1)
        return {d, c + d};
    else
        return {c, d};
}

위 코드는 $F_n$과 $F_{n+1}$을 쌍으로 반환합니다.

p를 법으로 하는 주기성¶

$p$를 법으로 하는 피보나치 수열을 생각해 봅시다. 이 수열이 주기적임을 증명하겠습니다.

이를 귀류법으로 증명해 봅시다. $p$로 나눈 나머지를 취한 피보나치 수의 처음 $p^2 + 1$개 쌍을 생각해 봅시다:

$$(F_0,\ F_1),\ (F_1,\ F_2),\ \ldots,\ (F_{p^2},\ F_{p^2 + 1})$$

$p$로 나눈 나머지는 $p$가지뿐이고 나머지 쌍은 많아야 $p^2$가지이므로, 이들 가운데 똑같은 쌍이 적어도 두 개 있습니다. 피보나치 수는 바로 앞의 두 수만으로 결정되므로, 이것만으로도 수열이 주기적임을 충분히 증명할 수 있습니다. 따라서 연속한 두 수의 쌍이 반복된다면, 그 쌍 뒤에 오는 수들도 같은 방식으로 반복된다는 뜻입니다.

이제 수열에서 인덱스가 가장 작은, 나머지가 같은 두 쌍을 고릅니다. 이 두 쌍을 $(F_a,\ F_{a + 1})$와 $(F_b,\ F_{b + 1})$이라고 합시다. $a = 0$임을 증명하겠습니다. 이것이 거짓이라면 바로 앞의 두 쌍 $(F_{a-1},\ F_a)$와 $(F_{b-1},\ F_b)$가 존재하며, 피보나치 수의 성질에 따라 이 두 쌍도 같아야 합니다. 그러나 이는 인덱스가 가장 작은 쌍을 골랐다는 사실에 모순되므로, 전주기가 없다는 것(즉, 수열은 $F_0$부터 주기적이라는 것)이 증명됩니다.