フィボナッチ数をC++で正確に計算するか？

Question

私は本当に混乱しています。私はフィボナッチ数を計算しようとしていますが、数値が大きくなるにつれて数値が間違ってくるようになります。そして私はなぜだか分からない。

Binet's Formulaを使って正確なフィボナッチ数を計算するには、これは常に整数を返すべきだと私は理解していますか？

ここでは私が取り組もうとしていることがあります。数が上がるよう

http://ideone.com/e6t6h

を参照してください。それはすべて奇妙になる？

ここで私はそれをcout.precision（15）で出力します。ここ

http://ideone.com/XREh2

私は< <何とか何とかを固定COUT < <でそれをプリントアウト。

ここでは、手続きループを使用して繰り返しを実行して計算しています。

これはBinetの公式を使用したものよりも正確です。

とにかく。誰もが私が見ることができる任意のコードを持っているBinetの式を使用して（n）のすべてのレベルを反復する必要性からF（n）を計算することができますか？

Answer 1

に探してみてください、あなたは√ 5の正確な解釈を必要とする√ 5は不合理である、それは正確にdoubleまたはfloatを使って表現することはできませんので、したがって、Binetの式はこれらの型では機能しません（ただし、計算の丸めによって、いくつかの小さな入力に対して正確な結果が得られます）。フィボナッチ数は整数であるので、あなたは、その後丸めることでより多くの引数にdoubleまたはfloatを使用してビネーの式から正確な結果を得ることができ、ほぼすべてのn小さな十分な結果ができることのために、正しい結果を返します

double binet(unsigned int n) 
{ 
    static const double phi = (1 + sqrt(5))*0.5; 
    double fib = (pow(phi,n) - pow(1-phi,n))/sqrt(5); 
    return round(fib); 
} 

正確には doubleと表されます。しかし、これらは多くはありません。 doubleは通常53ビットの精度しか持たないので、2 より小さいフィボナッチ数は、 doubleと正確に表すことができます（さらに、2の十分に高い累乗で割り切れるいくつかの大きなものもあります）。 2 より小さい最後のフィボナッチ数はF（77）ですが、F（78）は8で割り切れるので、53ビットの精度を持つ doubleとしても正確に表現できます。ただし、上記の結果は n <= 70ここでは71オンから丸め誤差が大きすぎます（ちなみに、 doublesを使用したBinetの式の結果は常にここでは大きすぎます）。の代わりに roundを使用すると正しい結果も得られますF（71）では、それ以上はない）。

標準のデータ型では、多くのフィボナッチ数は正確に表現できません。最後の（符号なし）64ビット型はF（93）です。 128ビットの場合、最後はF（186）である。とても小さい指標について、あなたは、1が扱う必要があり、正確な結果を得るためにルックアップテーブル

static const unsigned long long fibs[94] = { 0, 1, 1, 2, ... , 12200160415121876738ull }; 

を使用しない限り、単純な反復アルゴリズム

unsigned long long fibonacci(unsigned int n) 
{ 
    unsigned long long a = 0, b = 1; 
    for(; n > 0; --n) 
    { 
     b += a; 
     a = b-a; 
    } 
    return a; 
} 

上で獲得することが実質的には何もありません√ 5（および/またはφ）を記号定数として使用し、それを使用して式を評価します。これは、そのφ² = 1 + φ事実を使用して、ℚ(√5)における代数的整数環

ℤ[φ] = { a + b*φ : a, b ∈ ℤ } 

で式を評価になります。ビネーの式に相当する効率的に繰り返される（Nログ）手順Oに二乗しフィボナッチ数を計算するために使用される（ただし、F（n）はΘ（n）ビットであることに注意することができる

φ^n = F(n-1) + φ*F(n) 

ので、多数のビット演算はO（n）よりも小さくできません）。バニラ繰り返し二乗よりもわずかに効率的なバージョンは、φ² = 1 + φを使用して、F(2n) = 2*F(n)*F(n-1) + F(n)² = 2*F(n)*F(n+1) - F(n)² = F(n)*(F(n+1) + F(n-1))とF(2n+1) = F(n)² + F(n+1)²を見つける

φ^(2n) = (φ^n)² = (F(n-1) + φ*F(n))² = F(n-1)² + φ*2*F(n-1)*F(n) + φ²*F(n)² 
     = (F(n-1)² + F(n)²) + φ*(2*F(n-1)*F(n) + F(n)²) 

を使用します。これらの式は、F（n）とF（n + 1）からF（2n）、F（2n + 1）とF（2n + 2）を計算し、最大2回の乗算と2回の加算/アルゴリズムを使用して、O（log n）ステップのペアとして(F(n),F(n+1))を計算します。状態として2つの数値のみを使用します（バニラ繰り返し2乗は、状態として4つの数値を使用し、さらにいくつかの乗算が必要です）。

反復左から右へのアルゴリズムは、大きなフィボナッチ数の高速計算を可能にする代わりunsigned long longの任意精度のタイプと

unsigned long long fib(unsigned int n){ 
    if (n == 0) return 0; 
    unsigned int h = n/2, mask = 1; 
    // find highest set bit in n, can be done better 
    while(mask <= h) mask <<= 1; 
    mask >>= 1; 
    unsigned long long a = 1, b = 1, c; // a = F(k), b = F(k+1), k = 1 initially 
    while(mask) 
    { 
     c = a*a+b*b;  // F(2k+1) 
     if (n&mask) 
     { 
      b = b*(b+2*a); // F(2k+2) 
      a = c;   // F(2k+1) 
     } else { 
      a = a*(2*b-a); // F(2k) 
      b = c;   // F(2k+1) 
     } 
     mask >>= 1; 
    } 
    return a; 
} 

あります。もちろん、任意の高精度ライブラリには、独自のフィボナッチ関数が用意されていることが多いので、自分で実装するのは難しいです。

Answer 2

はあなたが<cmath>はなく<math.h>含むしようとしたことがあり、それは一般的にはC

Answer 3

のためであるとして、のmath.hは平方根のオーバーロードされたバージョンを持っていない可能性があり、山車とダブルスを正確に数字を表現するために設計されていません。その目的は、広い範囲の実数を表すことです。あなたは無限の精度を望むならば、あなたは正確にビネーの式を用いてフィボナッチ数を計算するにはhttp://gmplib.org/