Python 費氏數列解法(三):Fast Doubling

上篇寫到費氏數列的矩陣解法來達成 $O(\lg n)$ 的時間複雜度,實際上可以再做一些變化來簡化計算。如果目標時間複雜度是 $O(\lg n)$,代表我們要能每次直接計算當 n 變成兩倍時的數值。

下面介紹的 Fast Doubling 方法就是這個例子。

推導

先直接從 2n+1 和 2n 的矩陣開始出發:

$$
\begin{bmatrix}
F(2n+1)\\
F(2n)
\end{bmatrix} = \begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{2n}\begin{bmatrix}
1\\
0
\end{bmatrix}
$$

上篇最後的公式告訴我們,中間 1 1 1 0 的矩陣 n 次方可以替換成費氏數 n 附近的矩陣:

$$
\begin{bmatrix}
F(2n+1)\\
F(2n)
\end{bmatrix} = \begin{bmatrix}
F(n+1) & F(n)\\
F(n) & F(n-1)
\end{bmatrix}\begin{bmatrix}
F(n+1) & F(n)\\
F(n) & F(n-1)
\end{bmatrix}\begin{bmatrix}
1\\
0
\end{bmatrix}\\
= \begin{bmatrix}
F(n+1)^2 + F(n)^2\\
F(n)(F(n+1) + F(n-1))
\end{bmatrix}\\
= \begin{bmatrix}
F(n+1)^2 + F(n)^2\\
F(n)(2F(n+1) - F(n))
\end{bmatrix}
$$

最後一次運算我們把 $F(n-1)$ 用費氏數列的定義替換掉了,即 $F(n-1) = F(n+1) - F(n)$。

整理一下結果,對於奇數和偶數的不同算法如下:

  • $F(2n+1) = F(n+1)^2 + F(n)^2$
  • $F(2n) = F(n)(2F(n+1) - F(n))$

因此我們每次都可以把 n 變成兩倍,需要進行遞迴次數和第一篇的遞迴解法相比,從 $O(n)$ 變成 $O(\lg n)$,所以時間複雜度也跟著變成 $O(\lg n)$。

實作

遞迴解法

def fibonacci(n):
    return recursive(n)[1]

def recursive(n):
    # calculate f(n+1) and f(n)
    if n == 0:
        return 1, 0
    
    q, r = divmod(n, 2)
    f2, f1 = recursive(q) # f2 is the larger one
    f2, f1 = f1 ** 2 + f2 ** 2, f1 * (2 * f2 - f1)
    if r == 0:
        return f2, f1
    return f1 + f2, f2

可能有個疑問是,這個遞迴解法會不會像第一篇的遞迴那樣,做了許多重複計算?
答案是不會,因為每次進入 recursive 的數字一定是前一個的一半,而且 recursive tree 不會有增長,每次呼叫只會重複呼叫自己一次而已,因此不需要另外再做 cache 了。

迭代解法

迭代解法的思考方向,就是去分析我們在遞迴中每步做了什麼,並用迴圈代替。

這邊比較麻煩的是,遞迴中有個邏輯判斷,當 recursive 接受到的輸入是奇數時,必須多一個額外步驟,這樣結果才是正確的(因為奇數和偶數的算法不同,而我們預設的是偶數的計算公式)。

所以我們將 n 往上增長時,會不確定下一步要算到的是 2n 還是 2n+1,不知道需不需要額外的步驟。

簡單舉個例子,如果我們要計算的 n 是 21,則遞迴計算的是 [21, 10, 5, 2, 1]。用迭代做 bottom-up 的話,就會是 [1, 2, 5, 10, 21]。我們在計算到 2 的下一項時,沒辦法直接預測下一個要算的是 2n 的 4,還是 2n+1 的 5。

如果沒辦法預測,就記起來就好了 XD

所以解法就是建立一個 tracker,先記錄我們需要計算的值,然後 bottom-up 組回來。這邊的 tracker 其實就是個 stack,符合 LIFO 的特性(Last-in, First-out)。

def fib_fast_double_iter(n):
    # stack construction
    tracker = []
    while n > 1:
        tracker.append(n)
        n //= 2

    # initialization
    f1, f2 = 1, 1

    # bottom-up
    while tracker:
        n = tracker.pop()
        f1, f2 = f1 * (2 * f2 - f1), f1 ** 2 + f2 ** 2
        if n % 2 == 1:
            f1, f2 = f2, f1 + f2
    return f1

這篇文章還用了更進階的技巧,利用二進位表示法其實就是不斷除以二的餘數的特性,把 stack 也省下來了,只需要 $O(1)$ 的空間複雜度。這邊就不繼續探討,有興趣的可以自行去閱讀。

參考資料:

 
comments powered by Disqus