--- tags: linux kernel --- # 研讀 Algorithms for Computing Fibonacci Numbers Quickly contributed by < [`Risheng1128`](https://github.com/Risheng1128) > ## [Algorithms for Computing Fibonacci Numbers Quickly](https://ir.library.oregonstate.edu/downloads/t435gg51w) 這篇論文針對以下不同的算法分析費氏數列的效能 :::info 目標 - [x] Natural recursive - [x] Repeated addition - [ ] Binet's formula - [x] Matrix Methods of Gries, Levin and Others - [x] Matrix Methods - Three Multiply Matrix Method - Two Multiply Matrix Method - [x] Extending N. N. Vorob'ev's methods - [ ] Binomial Coefficients - [ ] Generating function - [ ] Product of Factors ::: 接著會分析每個不同的演算法的數學理論及效能分析 ## 1. Natural recursive ### 演算法 這是在演算法學習費氏數列時都會學到的方法 $fib(n)=\left\{ \begin{array}{l} 0 &if&0\leq n=0\\ 1 &if&n=1\\ fib(n-1)+fib(n-2) &if& n\geq2 \end{array} \right.$ 我們可以產生以下虛擬碼 (參考論文第 7 頁) ``` fib(n) if n = 0 return 0 else if n = 1 return 1 else return fib(n-1) + fib(n-2) ``` > 參考 Figure 2.1: Recursive algorithm to compute $f_n$ ### 分析效能 我們可以計算產生第 n 個數的計算時間 T~n~ ，其中: > T~n-1~ 為產生第 n - 1 個數的 bit operations > T~n-2~ 為產生第 n - 2 個數的 bit operations > Nn 為 T~n-1~ 和 T~n-2~ 相加所花的 bit operations 且初始條件 > T~0~ = 0 > T~1~ = 0 方程式: $T_n = T_{n-1} + T_{n-2} + Nn$ 接著發現上述方程式為 [Linear recurrence with constant coefficients](https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients) 可以先解 recurrence relation ($a_n = \lambda^n$) ，原方程式會改寫為 $\lambda^n = \lambda^{n-1} + \lambda^{n-2}$ 接著同除以 $\lambda^{n-2}$ 得到 $\lambda^2 - \lambda - 1 = 0$ 解方程式可以得到 $\left\{ \begin{array}{l} \lambda_1 = \frac{1 + \sqrt5}{2} \\ \lambda_2 = \frac{1 - \sqrt5}{2}\\ \end{array} \right.$ 因此 gerneral solution 為 $a_n = \alpha_1\lambda_1^n + \alpha_2\lambda_2^n$ 接著開始找 particular solution 假設 particular solution $v$ 的形式為 $v = C_1Nn + C_2$ 將 $v$ 代入 $T_n = T_{n-1} + T_{n-2} + Nn$ 可得: $(C_1Nn + C_2) - (C_1N(n - 1) + C_2) - (C_1N(n - 2) + C_2) = Nn$ 比較係數後可以得到 $\left\{ \begin{array}{l} C_1 = -1 \\ C_2 = -3N \\ \end{array} \right.$ 最後得到通解 $T_n = v + \alpha_1\lambda_1^n + \alpha_2\lambda_2^n$ 將初始條件代入我們可以得到 $\left\{ \begin{array}{l} \alpha_1 = N(3-\frac{4 - 3\lambda_1}{\lambda_2 - \lambda_1}) \\ \alpha_2 = N(\frac{4 - 3\lambda_1}{\lambda_2 - \lambda_1}) \\ \end{array} \right.$ 最後根據論文令 ==$\beta = \alpha_1$== 可以得到跟論文一樣的結果: ==$T_n = \beta\lambda_1^n + (3N - \beta)\lambda_2^n - Nn - 3N$== :::success 分析結果 - $0 < \beta < 3$ 且 $\alpha_1$ 和 $\alpha_2$ 都為正數 - $-1 < \lambda_2 < 0$ 且 $1.5 < \lambda_1 < 2$ - 由以上兩點可以推論 bit operation 的數量為 $\theta(\lambda_1^n)$ ，加上 $1.5 < \lambda_1$ 及 這個演算法為 $n$ 的指數，因此==對很大的數非常不適合== ::: ## 2. Repeated addition ### 演算法 接著不考慮第一種使用的方法，而是使用迭代的方式將每個數值計算出來，以下為虛擬碼 (參考論文第 8 頁) ``` fib (n) previous = 0 fibonacci = 1 for loop = 2 to n temp = fibonacci fibonacci = fibonacci previous previous = temp return fibonacci ``` > 參考 Figure 2.2: Repeated addition algorithm ### 分析效能 從上述的虛擬碼，可以先歸類以下幾點 > 1. $f_i = f_{i-1} + f_{i-2}$ , $2 \leq i \leq n$ > 2. 為了計算 $f_n$ ，每次的加法會使用到 $N(n-1)$ 個 bit operations 由以上兩點可以得到計算 $f_n$ 的 bit operations 總數 $\begin{split} T(n) &= T(n-1) + N(n-1), T(0) = 0, T(1) = 0 \\ &= \sum_{i=2}^nN(i-1) \\ &= N\sum_{i=0}^{n-2}(i+1) \\ &= N(\frac{(n-2)(n-1)}{2}) + N(n-1) \\ &= N(\frac{n^2}{2} - \frac{n}{2}) \end{split}$ 此外，論文也有計算 order-k Fibonacci sequcence 的方法，以下直接提供結果 > $T_k(n) = N(\frac{(k-1)n^2}{2} - \frac{(k-1)n}{2})$ > 參考論文 (3.4) 當 $k = 2$ 時，可以得到一開始的結論 &rarr; ==$T_2(n) = N(\frac{n^2}{2} - \frac{n}{2})$== ## 3. Binet's formula ### 演算法 這邊參考[費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number)搭配論文閱讀，可以得知其實費氏數列是有一個「公式解」的，如以下所示 ==$f_n = \frac{1}{\sqrt5}(\lambda_1^n - \lambda_2^n)$== ，其中: $\left\{ \begin{array}{l} \lambda_1 = \frac{1 + \sqrt5}{2} \\ \lambda_2 = \frac{1 - \sqrt5}{2} \\ \end{array} \right.$ 根據論文敘述，以下為推導出「公式解」係數 $\frac{1}{\sqrt5}$ 的方法 首先，根據上一個方法的方程式 $f_n = f_{n-1} + f_{n-2}$ ，我們可以得到特徵多項式 (Characteristic Polynomial): $\lambda^2 = \lambda + 1$ 接著可以解出特徵值 $\left\{ \begin{array}{l} \lambda_1 = \frac{1 + \sqrt5}{2} \\ \lambda_2 = \frac{1 - \sqrt5}{2} \\ \end{array} \right.$ 可以得到 ==$f_n = a\lambda_1^n + b\lambda_2^n$== ，並代入 $f_0 = 0$ 及 $f_1 = 1$ ，可以得到以下聯立方程式 $\left\{ \begin{array}{l} b = -a \\ 1 = a(\lambda_1 - \lambda_2) \\ \end{array} \right.$ 代入 $\lambda_1$ 及 $\lambda_2$ 得到 a 及 b $\left\{ \begin{array}{l} a = \frac{1}{\sqrt5} \\ b = -\frac{1}{\sqrt5} \\ \end{array} \right.$ 因此最後可以的到完整的公式解 ==$f_n = \frac{1}{\sqrt5}((\frac{1 + \sqrt5}{2})^n - (\frac{1 - \sqrt5}{2})^n)$== 接著由於 $\lambda_2 = -0.61803$ ，且 $\lambda_2$ 會隨著 n 越大而越來越小，因此根據以下論文可以近似成更簡單的公式解 > Knuth, D. E., "The Art of Computer Programming," Vol. Reading MA; 1973. $f_n = [\frac{1}{\sqrt5}(\frac{1 + \sqrt5}{2})^n + 0.5], n \geq 0$ 最後提供==遞迴==及==非遞迴==的虛擬碼 > 非遞迴 fib(n) $\quad$ compute the $Nn + logn$ most significant bits of $\sqrt5$ $\quad$ return $[\frac{1}{\sqrt5}(\frac{1 + \sqrt5}{2})^n + 0.5]$ > 參考 Figure 2.4: Approximation of Binet's formula > 遞迴 fib(n) $\quad$ if n = 1 $f_1$ &larr; 1 $\quad$ else $f_n$ &larr; $[(fib(n/2))^2\cdot\sqrt5]$ $\quad$ return $f_n$ > 參考 Figure 2.5: Recursive Binet's approximation ### 分析效能 在計算上述==非遞迴==的演算法之前，需要先考慮以下三種 operations > 1. The $Nn + logn$ bits of the square root of five > 2. $Nn + logn$ bit number must be exponentiated to the $n^th$ power > 3. $Nn + logn$ bit division $\begin{split} T(n) &= T(n/2) + D(Nn/2) \\ &= \frac{(Nn)^2}{4} + \frac{(Nn)^2}{16} + \frac{(Nn)^2}{64} + ... \\ &= \sum_{i=1}^\infty\frac{(Nn)^2}{2^{2i}} \\ &= (Nn)^2\sum_{i=1}^\infty(\frac{1}{4})^i \\ &= \frac{(Nn)^2}{3} \end{split}$ :::warning ToDo: 分析的更完整 ::: ## 4. Matrix Methods of Gries, Levin and Others 在這個章節，提到數個論文用來計算 ==order-k Fibonacci sequcence== 第 n^th^ 數的演算法，並參考了以下兩篇論文，裡頭提到上述演算法的 Running time 、 number of multiplies 及 number of additions ，以 bit operations 為單位 > - Er, M. C., "A fast algorithm for computing order-k Fibonacci numbers," in The Computer Journal,26, 224-227; 1983. > - Fiduccia, C. M., "An efficient formula for linear recurrences," in SIAM Journal of Computing,14, 106-112; 1985. > Time to comput $f_n^k$ > | Author | Running time | Multiplies | Additions | > | --------- | ------------ | ---------- | --------- | > | Gries | $\theta(1.5k^2logn)$ | $\theta(1.5k^2)$ | $\theta(3k^2)$ | > | Shortt | $\theta(k^2logn)$ | $\theta(k^2)$ | $\theta(k^3)$ | > | Pettrossi | $\theta(1.5k^3logn)$ | $\theta(1.5k^3)$ | $\theta(1.5k^3)$ | > | Urbanek | $\theta(k^3logn)$ | $\theta(k^3 + 0.5k^2)$ | $\theta(k^3 + 0.5k^2)$ | > | Fiduccia | $\theta(\mu(k)logn)$ | $\theta(\mu(k)logn)$ | $\theta(\mu(k)logn)$ | > > 其中 $\mu(k)$ 表示總共所需要的 arithmetic operations (用來計算 multiply two polynomials of degree k - 1)。 如果 fast Fourier transform 可以使用，運算操作的數量會變成 $\theta(k\cdot logk\cdot logn)$ > 參考論文 Table 2.1: Running times of algorithms to compute $f_n^k$ 論文接著提到了上述表格第一列 Gries and Levin 所使用的方法 令 $A=\left[ \begin{array}{l} 1& 1& ...& 1& 1 \\ 1& 0& ...& 0& 0 \\ 0& 1& ...& 0& 0 \\ & & \ddots \\ 0& 0& ...& 1& 0 \\ \end{array} \right]$ 並且使用 recurrence relation: $\left[ \begin{array}{} f_n^k \\ f_{n-1}^k \\ f_{n-2}^k \\ \vdots \\ f_{n-k+1}^k \\ \end{array} \right] = A\left[ \begin{array}{} f_{n-1}^k \\ f_{n-2}^k \\ f_{n-3}^k \\ \vdots \\ f_{n-k}^k \\ \end{array} \right]$ 為了計算 $f_n^k$ ，由於下列式子，我們只需要計算 $A^{n-k+1}$ 就可以得知 $\left[ \begin{array}{} f_n^k \\ f_{n-1}^k \\ f_{n-2}^k \\ \vdots \\ f_{n-k+1}^k \\ \end{array} \right] = A^{n-k+1}\left[ \begin{array}{} f_{k-1}^k = 1 \\ f_{k-2}^k = 0 \\ f_{k-3}^k = 0 \\ \vdots \\ f_{k-k}^k = 0 \\ \end{array} \right]$ 接著要降低計算時所消耗的成本，以下為論文的方法 1. 利用 $A$ 和 $A^{i-1}$ 計算出 $A^i$ ，且除了第一列的值，新矩陣 $A^i$ 的其他列都會和 $A^{i-1}$ 有對應關係，例如 $A^i$ 第 2 列 會和 $A^{i-1}$ 第 1 列一樣 > By noticing that any row, except the first, of $A^i$ is the same as the previous rowof $A^{i-1}$ Gries and Levin were able to construct an algorithm that computes $A^{i+1}$ from $A$ and $A^i$ by computing the bottom row of $A^{i+1}$ and copying the remaining rows from $A^i$ 2. 由第一點得知，我們只需要計算每個矩陣的第一列，而其他列則直接複製即可，使用這樣的方法可以把矩陣乘法的時間從 $\theta(k^3)$ 降為 $\theta(k^2)$ ，加上計算 $A^{n-k}$ 只需要 $logn$ 的時間，因此使用 Gries and Levin 的方法所消耗的時間為 $\theta(k^2logn)$ > This reduced the number of multiplies from $\theta(k^3)$ to $\theta(k^2)$ to do the matrix multiply. Since $A^{n-k}$ can be computed using $\theta(log n)$ matrix multiplies by using repeated squaring, the time to compute $f_n^k$ using Gries and Levin's algorithm is $\theta(k^2logn)$. ## 5. Matrix Methods ### 矩陣定義 首先定義矩陣，該矩陣可以用來計算 Fibonacci numbers $\left[ \begin{array}{l} 1& 1 \\ 1& 0 \\ \end{array} \right]^n = \left[ \begin{array}{} f_{n+1}& f_n \\ f_n& f_{n-1} \\ \end{array} \right]$ 接下來證明下列等式是否成立 $\left[ \begin{array}{l} 1& 1 \\ 1& 0 \\ \end{array} \right]^{n+1} = \left[ \begin{array}{} f_{n+2}& f_{n+1} \\ f_{n+1}& f_{n} \\ \end{array} \right]$ 證明方法很單純，直接乘上一個 $A$ 即可，如下所示 $\left[ \begin{array}{l} 1& 1 \\ 1& 0 \\ \end{array} \right]\left[ \begin{array}{l} 1& 1 \\ 1& 0 \\ \end{array} \right]^n = \left[ \begin{array}{} f_{n+1} + f_n& f_n + f_{n-1} \\ f_{n+1}& f_n \\ \end{array} \right] = \left[ \begin{array}{} f_{n+2}& f_{n+1} \\ f_{n+1}& f_n \\ \end{array} \right]$ 得到等式成立！ 接下來可以跳脫思考，不一定要每次都乘上 $A$ ，也可以一次乘上 $A^n$ ，這樣的話可以從矩陣 $\left[ \begin{array}{} f_{n+1}& f_n \\ f_n& f_{n-1} \\ \end{array} \right]$ 計算出 $\left[ \begin{array}{} f_{2n+1}& f_{2n} \\ f_{2n}& f_{2n-1} \\ \end{array} \right]$ 並且可以歸納出以下方程式 (以下兩種方法都會用到！): $\left\{ \begin{array}{l} f_{2n+1} = f_{n+1}^2 + f_n^2 \\ f_{2n} = f_{n+1}f_n + f_nf_{n-1} \\ f_{2n-1} = f_{2n+1} - f_{2n} \\ \end{array} \right.$ ### Three Multiply Matrix Method #### 演算法 直接附上虛擬碼 > fib(n) $\quad$ if n = 1 return the matrix $\left[ \begin{array}{l} 1& 1 \\ 1& 0 \\ \end{array} \right]$ $\quad$ else $\qquad$ $\left[ \begin{array}{} f_{n/2+1}& f_{n/2} \\ f_{n/2}& f_{n/2-1} \\ \end{array} \right]$ &larr; fib(n/2) $\qquad$ a &larr; $(f_{n/2+1})^2$ $\qquad$ b &larr; $(f_{n/2})^2$ $\qquad$ c &larr; $(f_{n/2-1})^2$ $\qquad$ return the matrix $\left[ \begin{array}{l} a+b& a-c \\ a-c& b+c \\ \end{array} \right]$ > 參考 Figure 2.6: Three multiply matrix algorithm #### 分析效能 這邊根據上述的演算法 (Figure 2.6) 進行計算，首先觀察一共有三個一半大小的乘法，三個加法運算，以及每次取一半大小的遞迴，由這些條件我們可以開始計算，這邊論文忽略加法的 bit operations $\begin{split} T(n) &= T(n/2) + 3M(Nn/2) \\ &= 3M(Nn/2) + 3M(Nn/4) + 3M(Nn/8) + ... \\ &= \frac{3(Nn)^2}{4} + \frac{3(Nn)^2}{16} + \frac{3(Nn)^2}{64} + ... \\ &= \sum_{i=1}^\infty\frac{3(Nn)^2}{2^{2i}} \\ &= 3(Nn)^2\sum_{i=1}^\infty(\frac{1}{4})^i \\ &= 3(Nn)^2\cdot\frac{1}{3} \\ &= (Nn)^2 \end{split}$ ### Two Multiply Matrix Method #### 演算法 直接附上虛擬碼 > fib(n) $\quad$ if n = 1 return the matrix $\left[ \begin{array}{l} 1& 1 \\ 1& 0 \\ \end{array} \right]$ $\quad$ else $\qquad$ $\left[ \begin{array}{} f_{n/2+1}& f_{n/2} \\ f_{n/2}& f_{n/2-1} \\ \end{array} \right]$ &larr; fib(n/2) $\qquad$ $f_{n+2}$ &larr; $f_{n/2+1}(f_{n/2+1} + 2f_{n/2})$ $\qquad$ $f_n$ &larr; $f_{n/2}(2f_{n/2+1} - f_{n/2})$ $\qquad$ return the matrix $\left[ \begin{array}{} f_{n+2} - f_n& f_n \\ f_n& f_{n+2} - 2f_n \\ \end{array} \right]$ > 參考 Figure 2.7: Two multiply matrix algorithm #### 分析效能 這邊根據上述的演算法 (Figure 2.7) 進行計算，首先觀察一共有兩個一半大小的乘法，四個加法運算，以及每次取一半大小的遞迴。這邊論文說明這個演算法使用的 bit operation 為 $\frac{2\cdot M(Nn)}{3}$ ，由這些條件，可以得到以下等式 $\begin{split} T(n) &= T(n/2) + 2M(Nn/2) \\ &= 2M(Nn/2) + 2M(Nn/4) + 2M(Nn/8) + ... \\ &= \frac{2(Nn)^2}{4} + \frac{2(Nn)^2}{16} + \frac{2(Nn)^2}{64} + ... \\ &= \sum_{i=1}^\infty\frac{2(Nn)^2}{2^{2i}} \\ &= 2(Nn)^2\sum_{i=1}^\infty(\frac{1}{4})^i \\ &= 2(Nn)^2\cdot\frac{1}{3} \\ &= \frac{2(Nn)^2}{3} \end{split}$ ## 6. Extending N. N. Vorob'ev's methods ### 演算法 以下為 N. N. Vorob'ev method 中很重要的關係式 > 參考書籍 Vorob'ev, N.N., "Fibonacci Numbers," Pergamon press, New York; 1961. ==$f_{n+k} = f_{n-1}f_k + f_nf_{k+1}$== 而公式推導可以參考論文第 18 頁，主要是使用數學歸納法進行證明 接著實作虛擬碼如下所示 > fib(n) > $\quad$ if n = 4 return $f_2$ = 1, $f_3$ = 2, $f_4$ = 3 > $\quad$ else > $\qquad$ $f_{n/4}, f_{n/4+1}, f_{n/2}$ &larr; fib(n/2) > $\qquad$ $f_{n/2+1}$ &larr; $f_{n/4-1}f_{n/4+1} + f_{n/4}(f_{n/4+1}f_{n/4})$ > $\qquad$ $f_n$ &larr; $f_{n/2}(f_{n/2-1} + f_{n/2+1})$ > $\qquad$ return $f_{n/2}, f_{n/2+1}, f_n$ > 參考 Figure 2.8: Extended N. N. Vorob'ev algorithm to compute $f_n$ > ![](https://i.imgur.com/BWoIQ8h.png) > 參考 Figure 2.9: Call tree for $f_{16}$ ### 分析效能 這邊根據上述的演算法 (Figure 2.8) 進行計算， Figure 2.8 將一個 $\frac{n}{2}$ bit 的乘法改成兩個 $\frac{n}{4}$ bit 的乘法，且論文說明這個演算法使用的 bit operation 為 $\frac{M(Nn)}{2}$ ，由這些條件，可以得到以下等式 $\begin{split} T(n) &= T(n/2) + M(Nn/2) + 2M(Nn/4) \\ &= M(Nn/2) + 3M(Nn/4) + 3M(Nn/8) + ... \\ &= \frac{(Nn)^2}{4} + \frac{3(Nn)^2}{16} + \frac{3(Nn)^2}{64} + ... \\ &= \frac{(Nn)^2}{4} + \sum_{i=2}^\infty\frac{3(Nn)^2}{2^{2i}} \\ &= \frac{(Nn)^2}{4} + 3(Nn)^2\sum_{i=2}^\infty(\frac{1}{4})^i \\ &= \frac{(Nn)^2}{4} + 3(Nn)^2\cdot\frac{1}{12} \\ &= \frac{(Nn)^2}{2} \end{split}$ ## 7. Binomial Coefficients ### 演算法 使用二項式係數 ([Binomial Coefficients](https://en.wikipedia.org/wiki/Binomial_coefficient)) 計算 Fibonacci numbers ，以下二項式係數的定義 $\left( \begin{array}{} n \\ k \\ \end{array} \right) = \frac{n!}{k!(n-k)!}$ 接著有兩個性質，如以下所示: > Recursive formula $\left( \begin{array}{} n \\ k \\ \end{array} \right) + \left( \begin{array}{} n \\ k + 1 \\ \end{array} \right) = \left( \begin{array}{} n + 1 \\ k + 1 \\ \end{array} \right)$ > 參考論文 (2.14) > Multiplicative formula $\left( \begin{array}{} n \\ k \\ \end{array} \right) = \left( \begin{array}{} n \\ n-k \\ \end{array} \right)$ > 參考論文 (2.15) 接著附上帕斯卡三角形，其中 $0 \leq n \leq 5$ 且 $0 \leq k \le$，如下圖 > ![](https://i.imgur.com/9QikHBG.png) > 參考論文 Table 2.2: Pascal's triangle 接著有一個有趣的性質，這邊定義帕斯卡三角形第 $n^{th}$ 個對角線 ($d_n$) 為以下二項式係數的序列 $\left( \begin{array}{} n \\ 0 \\ \end{array} \right), \left( \begin{array}{} n-1 \\ 1 \\ \end{array} \right), \left( \begin{array}{} n-2 \\ 2 \\ \end{array} \right), ..., \left( \begin{array}{} 0 \\ n \\ \end{array} \right)$ 這邊假設 n = 5 ，可以得到序列 1, 4, 3 ，可以對應 Table 2.2 左下角往右上移動的位置 另外有個有趣的定理，也就是把上述第 $n^{th}$ 個對角線的值全部相加的話，可以得到 $f_{n+1}$ ，以剛剛的例子為例，總和為 1 + 4 + 3 = 8 ，剛好為費氏數列的第 6 個數 > Theorem 2.8 The sum of the $n^{th}$ diagonal, $d_n$, of Pascal's triangle is equal to $f_{n+1}$. 因此要計算 $f_n$ 的話，我們只需要計算 $d_{n-1}$ 的總和即可，那多了一個新問題，==怎麼算 $d_{n-1}$ 最快呢？== 論文提供了一種演算法 － Goetgheluck's algorithm ，用來計算 $\left( \begin{array}{} n \\ k \\ \end{array} \right)$ 的 prime power factorization ，以下為虛擬碼 (E is the power of input n,k and p) > E &larr; 0, r &larr; 0 if p > n - k then E &larr; 1; end. if p > n/2 then E &larr; 0; end. if p $\cdot$ p > n then if n mod p < k mod p then E &larr; 1; end. Repeat $\quad$ a &larr; n mod p $\quad$ n &larr; [n/p] $\quad$ b &larr; (k mod p) + r $\quad$ k &larr; [k/p] $\quad$ if a < b then E &larr; E + 1,r &larr; 1 $\quad$ else r &larr; 0 until n = 0 > 參考 Figure 2.10: Goetgheluck's algorithm ### 分析效能 :::warning ToDo: 分析 bit operations ::: ## 8. Generating function ### 數學推導 使用 [Generating function](https://en.wikipedia.org/wiki/Generating_function) 表示完整的費氏數列 $G(z) = f_0 + f_1z + f_2z^2 + ... = \displaystyle\sum_{n\geq0}^\infty f_nz^n$ 假設 $zG(z) = f_0z + f_1z^2 + f_2z^3$ $z^2G(z) = f_0z^2 + f_1z^3 + f_2z^4$ 接著計算 $G(z) - zG(z) - z^2G(z)$ 可以得到以下式子 $G(z) - zG(z) - z^2G(z) = f_0 + (f_1 - f_0)z + (f_2 - f_1 - f_0)z^2 + (f_3 - f_2 - f_1)z^3 + ...$ &rarr; $G(z)(1 - z - z^2) = 0 + z + 0z^2 + 0z^3 + ...$ &rarr; $G(z) = \frac{z}{1 - z - z^2}$ 最後估計 G(z) 位於單位根 ($\omega_i$) 上的值 ($\nu_i$)，並且為了找到每項的係數，也就是 e Fibonacci numbers ，因此使用反傅立葉轉換，可以得到最後結果如下，其中 $F$ 為 [Fourier matrix](https://en.wikipedia.org/wiki/DFT_matrix) $f_n = \displaystyle\sum_{i=0}^{n-1}F_{n-1,i}\cdot\nu_i$ ### 分析效能 ## 9. Product of Factors ### 演算法 ### 分析效能 ## 測試比較 ## 參考資料 [費氏數列分析](https://hackmd.io/@sysprog/fibonacci-number#Vorobev-%E7%AD%89%E5%BC%8F) [Algorithms for Computing Fibonacci Numbers Quickly](https://ir.library.oregonstate.edu/downloads/t435gg51w)