Python - フィボナッチ数をより速く計算する(ベンチマークの参考にはならないけど。。) - ( @mattn_jp @dankogai )mattnさん、Dan Kogaiさんのツイートより

Pythonからはじめる数学入門
原著

開発環境

• macOS High Sierra - Apple
• Emacs (Text Editor)
• Python 3.7 (プログラミング言語)

フィボナッチ数列ベンチマーク。Crystal 速い。 / “GitHub - drujensen/fib: Performance Benchmark of top Github languages” https://t.co/P5NECA0sZG

— mattn (@mattn_jp) 2018年9月26日

constexpr ちょっと遅くないか?メモ化どころか実行時無計算になるはずなのに

— Dan Kogai (@dankogai) 2018年9月27日

Interpreted, dynamically typedな🐍Python3でより速くなるようなコードを書いてみた。

コード(Emacs)

Python 3

#!/usr/bin/env python3
from sympy import sqrt
import sys


def fib(n):
    return 1 / sqrt(5) * (((1 + sqrt(5)) / 2) ** n - ((1 - sqrt(5)) / 2) ** n)


phi = (1 + sqrt(5)) / 2


def fib1(n):
    return (phi ** n - (1 - phi) ** n) / sqrt(5)


def fib2(n):
    return (phi ** n - (- phi) ** -n) / sqrt(5)


fibs = [fib, fib1, fib2]
if __name__ == '__main__':
    print(fibs[int(sys.argv[1])](45).simplify())

入出力結果(Terminal, Jupyter(IPython))

$ time ./fib.py 0
1134903170

real 0m0.764s
user 0m0.712s
sys 0m0.048s
$ time ./fib.py 1
1134903170

real 0m0.767s
user 0m0.713s
sys 0m0.049s
$ time ./fib.py 2
1134903170

real 0m0.786s
user 0m0.732s
sys 0m0.047s
$

フィボナッチ数#一般項より。

もちろん、その他の言語でも再帰関数ではなく一般項を利用して計算すれば同様に速くなるけど、PythonのSymPyを使えば、無理数が出てきても気軽に正確な計算が出来るということで。(ということで、他の言語でも数式処理システムのライブラリー等があれば同様に高速化可能。)