サブリニア時間でのフィボナッチ数n番目

質問

n番目のフィボナッチ数をサブ線形時間で計算するアルゴリズムはありますか？

どのように解決するのですか？

この n 番目のフィボナッチ数は次のように与えられます。

f(n) = Floor(phi^n / sqrt(5) + 1/2) 

ここで

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

仮に、原始的な数学演算( + , - , * と / ) は O(1) を計算すると、この結果を使って n でのフィボナッチ数 O(log n) 時間 ( O(log n) というのは、式中の指数関数があるからです)。

C#の場合。

static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use 
   const double inverseSqrt5 = 0.44721359549995793928183473374626
   const double phi = 1.6180339887498948482045868343656
*/

static int Fibonacci(int n) {
    return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}