上篇寫到費氏數列的矩陣解法來達成 $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)$ 的空間複雜度。這邊就不繼續探討，有興趣的可以自行去閱讀。
參考資料：
- Fast Doubling method to find the Nth Fibonacci number
- Fast Fibonacci algorithms
- Calculating Fibonacci Numbers by Fast Doubling