私は、Binetの公式をGNU MPライブラリで使ってフィボナッチ数を計算しています。私はアルゴリズムの漸近的なランタイムを解明しようとしています。Binetの数式のランタイム
Fib(n)の場合、変数をnビット精度に設定しています。したがって、2つの数を掛けることはn Log(n)と考える。累乗は、Log(n)乗算と考える。私はLog(n)Log(n Log(n))を持っていると思います。結論として、浮動小数点数と累乗のべき乗のべき乗を整数指数で掛け合わせるという仮定の両方で、正しいのでしょうか?
私の精度が高く、私は精度g(n)を使用します。私はこれがg(n)Log(g(n))に減少すると思う。しかし、私はg(n)はg(n)= n Log(φ)+1でなければならないと思います。それは漸近線に実際の影響を与えてはならないはずです。
計算には単に乗算と累乗が必要ですか? exp(x * log(\ phi))(事前計算ログ(\ phi)を保持する)。 – ElKamina
数字とそのビット数を表すのに 'n'を使用しています: –