執行人: seasonwang0905
期末專題解說影片
依據 fibdrv 作業規範,繼續投入 Linux 核心模組和相關程式的開發。
閱讀 fibdrv 作業規範,包含「作業說明錄影」和「Code Review 錄影」,本著「誠實面對自己」的心態,在本頁紀錄所有的疑惑,並與授課教師預約討論。
過程中,彙整 Homework3 學員的成果,挑選至少三份開發紀錄,提出值得借鏡之處,並重現相關實驗。
回答「自我檢查清單」的所有問題,需要附上對應的參考資料和必要的程式碼,以第一手材料 (包含自己設計的實驗) 為佳
理解其中的技巧並導入到 fibdrv 中,並留意以下:
參考 eecheng87 的實作,他在 fast doubling 的基礎上加入了 __builtin_clz()
來加速 Fibonacci 的運算。
Fast doubling 無 __builtin_clz()
版本:
Fast doubling 有 __builtin_clz()
版本:
在加入 __builtin_clz()
前,不論欲求的 n 值為何,迴圈必定會執行 32 ,加入後,可以減少迭代的次數,避免在 n 值很小的時候執行過多的計算
再來,參考並修改了 Hsuhaoxiang 的作法,他先計算了傳入的 n 值 (這裡為 k) 在 bitwise 中有多少個 1 並紀錄,以此切換 a 及 b 的位置
這裡直接計算 k 的 1 位元個數,然後由 fast doubling 可減少一半迭代數的特性算出 count
,在效能上已和使用 __builtin_clz()
類的手法接近,改善的方式可能要從記憶體的使用或是加入大數運算
因為 c 語言沒有合適的資料型態可以存儲超過 或 的數值,故我們需要使用其他手段來作大數運算,參考 eecheng87 的作業中所述,他使用以下結構來存取一個動態長度的陣列
加法的實作為
上面省去了判斷加負數的部份,加負數可以替代成減法的形式。我們需要以字串來紀錄大數,使用時再將其一個一個輸出成大數的樣子
再來是減法的部份
減法中有很多借位的算法,目前還在嘗試理解
這邊有個疑問:加法、減法輸出 n_carry
、n_borrow
進位或是借位目的是什麼,用在哪裡?
最後是乘法
因為字串沒有所謂的相乘,所以只能把數字擷取出來再做乘法,最後把結果存到 c.->digits
有了以上大數運算,就可以運用到 Fibonacci 的數列上了
Fast doubling 演算法支援大數運算
輸入第 100 、200 項時,看看輸出結果為何
比對 The Fibonacci numbers 發現相同,大數運算成功執行。
James L. Holloway 發表於 1988 年的碩士論文 〈Algorithms for Computing Fibonacci Numbers Quickly〉針對多種 Fibonacci 數列之演算法進行模擬及分析,包括遞迴、重複相加、Binet's Formula (公式解)、Vorobev等式、二項式係數法等等逐項討論,以實際成果來展示各演算法在 Fibonacci 數列之項數 n 改變的情況下,其執行時間及效率究竟如何,最後驗證其論文結果。
在介紹函式遞迴的時,常見的例子即計算 Fibonacci 數,因重複呼叫函式的關係,演算法時間複雜度來到 ,其中 ,隨著 n 值增加,執行時間會以指數倍成長,故在 n 值較大時,幾乎不會選用此演算法。
原理與前述相同,只不過使用了 for 迴圈來取代函式遞迴的動作,效率卻有顯著的提昇,隨著 n 值增加,執行時間則呈線性增長。另外,論文中提到的 K-Fibonacci 數列也有相關的演算法,不過這裡暫不討論此部份。
透過 gnuplot 製圖:
橫軸代表 Fibonacci 數列第 n 項,即 ,縱軸則是其執行時間,不難看出僅僅是 n = 10 ,遞迴演算法的執行時間已來到最初的 6 倍了,其效率可說是驚人的低落。重複相加的演算法可以作為 gnuplot 的練習及效能的參考。
接著,列出改善計算 Fibonacci 數列的演算法
根據上述關係,著手撰寫程式碼
寫完後,馬上來測試效能如何,結果如下圖所示
藍色的線是參考上述提及的 eecheng87 的 fast doubling 無硬體加速版本的演算法,綠色則是我實作的部份,可以發現綠色的執行時間與 n 呈線性成長,效能只有比重複相加的演算法好一些
提問:在 fast doubling 演算法中,最多只需要做 次的迭代即可算完每項 ,即使我設定 n 不會超過 32 次,輸出結果是正確的,但執行時間仍就無法降低呢?是否是因為多了 f2 = f1 + temp
這一項呢?又或者應該要支援大數運算後再重新比較效能看看?
你用 perf 一類的工具去觀察執行的表現,會發現裡頭存在耗時的指令