Algorithm

Python 費氏數列解法(五):不同解法的執行時間比較

終於來到最後一篇了,前面幾篇依序寫了各種不同費氏數列的寫法,包含:遞迴、迭代矩陣、從矩陣衍生的Fast doubling、以及最後公式解和補充的精確版公式解

從時間複雜度來看,從矩陣開始都是 $O(\lg n)$(如果我們把公式解內指數運算當作 $O(\lg n)$ 的話),那這三個哪個比較快呢?

這篇文章裡面用 c 比較了 fast doubling 和公式解,發現號稱常數時間複雜度的公式解,反而慢上很多,而且還需要考慮精確度問題。

使用 Decimal 提高浮點運算精確度

第四篇提到費氏數列的公式解會遇到浮點數問題,只能精準算到 122 位。因為浮點數是利用二進位的小數來做儲存,對於非二進位的數字會有誤差。而且其儲存位數有上限,對於無理數的運算,超過一定的大小就會出現精確度問題。

所以這篇就要來簡單使用 Python 內建的 Decimal module 來拉高浮點數運算的精確度。