Binet の式、つまりフィボナッチ数を計算するための閉解式を使用して、通常計算可能なフィボナッチ数 (結果が大きくなりすぎない限り) を一定時間で計算できます。これが私のコードです：
fibonnaci の非再帰的実装の場合:
gr = (1 + 5**0.5) / 2
def gfib(n):
return int(((gr**n - (1-gr)**n) / 5**0.5))
a^n は指数関数的な実行時の複雑さを示していることは理解していますが、これはコードが Python で実行されている場合には当てはまりません。これは、n 番目のフィボナッチ数を即座に計算するためです。指数がPythonでどのように実装されているか（おそらく二乗による累乗？）についていくつかの調査を行って、得られる一定時間の解を求めましたが、決定的な答えは見つかりませんでした。何か案は？
float.__pow__()メソッドは、C のlibmを使用します。これは、2 進浮動小数点演算のハードウェア サポートを最大限に活用します。後者は、対数を使用して数値を表します。対数表現により、累乗を 1 回の乗算だけで実装できます。
エグゼクティブ サマリー:浮動小数点指数はハードウェアに実装されており、対数の魔法によりほぼ一定の速度で実行されます。
整数の指数は、思ったよりずっと効率的に計算できます。ウィキペディアがそれについて言わなければならないことは次のとおりです。
bⁿ を計算する最も単純な方法は、n-1 回の乗算操作を必要としますが、次の例に示すように、それよりも効率的に計算できます。2¹⁰⁰を計算するには、100 = 64 + 32 + 4 であることに注意してください。以下を順番に計算します。
2² = 4
(2²)² = 2⁴ = 16
(2⁴)² = 2⁸ = 256
(2⁸)² = 2¹⁶ = 65,536
(2¹⁶)² = 2³² = 4,294,967,296
(2³²)² = 2⁶⁴ = 18,446,744,073,709,551,616
2⁶⁴ × 2³² × 2⁴ = 2¹⁰⁰ = 1,267,650,600,228,229,401,496,703,205,376
この一連の手順では、99 回ではなく 8 回の乗算操作しか必要ありません (上記の最後の積では 2 回の乗算が必要になるため)。
一般に、bⁿ を計算するために必要な乗算演算の数は、2 乗による累乗または (より一般的には)加算チェーン累乗を使用することで、Θ(log n) に減らすことができます。bⁿ の乗算の最小シーケンス (指数の最小長の加算チェーン) を見つけることは、効率的なアルゴリズムが現在知られていない難しい問題ですが (部分和問題を参照)、多くの合理的に効率的なヒューリスティック アルゴリズムが利用可能です.[29]
二乗によるべき乗のページはまとめにくいですが、基本的には 2⁸ == (2⁴)² == (2²)²)² という考え方なので、 を計算する代わりに を計算2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 256できます2 × 2 = 4; 4 × 4 = 16; 16 × 16 = 256。
log_pow 関数の CPython のソース コードで実装を見つけることができます。