c#-4.0 - フィボナッチの計算

Question

フィボナッチ数列を計算するためのこの素晴らしい非再帰関数が送られてきました。

代替テキスト

そこで、c＃を少しコーディングして、1474までのすべての数値が正しいことを確認できました。

1475以降で計算しようとすると、問題が発生します。私のc＃の数学のスキルは、別の方法を考え出すことだけではありません。それで、誰かがこの特定の数学関数をc＃で表現するより良い方法を持っていますか？再帰関数を実行する従来の方法以外に？

ちなみに、戻り型としてBigIntegerを使い始めました。しかし、（1 + Math.Sqrt（5）/ 2）を1475乗しようとすると、実際に問題が発生します。これをInfinity以外のもので戻すために必要なデータ型（またはそのためのメカニズム）がわかりません。

これが出発点です。

private Double FibSequence(Int32 input) {
    Double part1 = (1 / Math.Sqrt(5));
    Double part2 = Math.Pow(((1 + Math.Sqrt(5)) / 2), input);
    Double part3 = Math.Pow(((1 - Math.Sqrt(5)) / 2), input);

    return (part1 * part2) - (part1 * part3);
}

そして、いや、それは宿題ではありません。遅い日のための単なる「単純な」問題。

score 14 · Accepted Answer

C＃には、これを素朴に処理するのに十分な浮動精度と範囲のデータ型があるとは思いません。

本当にこのパスをたどりたい場合は、共役 $\ Phi = \ phi ^ {-1} = \ phi-1 = \ frac {-1+ \ sqrt 5} {2}$ が1未満であることに気付くことができます。これ $-\ frac {（-\ Phi）^ n} {\ sqrt 5}$ は、最も近い整数に丸めるのと同じことです。したがって、を見つけるためのソリューションを単純化できます $\ left \ lfloor \ frac {\ phi ^ n} {\ sqrt 5} + \ frac12 \ right \ rfloor$ 。次に、二項展開を使用して $\ left \ lfloor a + b \ sqrt 5 \ right \ rfloor$ 、適切なaとb（有理数であり、BigIntegerで正確に計算できる）を使用して、を計算するだけで済みます。それでもこのためにDoubleに戻ると、1475を超えることはありませんが、正確な整数演算だけでこの部分を実行する方法を理解できるはずです☺</ p>

$\ frac {\ phi ^ n} {\ sqrt 5} = \ frac {（1+ \ sqrt 5）^ n} {2 ^ n \ sqrt 5} = \ frac {\ sum_ {k = 0} ^ n {n \ choice k} \ sqrt 5 ^ k} {2 ^ n \ sqrt 5}$
$= \ left（\ sum_ {k = 0} ^ {\ left \ lfloor \ frac {n-1} 2 \ right \ rfloor} \ frac {{n \ choice 2k + 1} 5 ^ k} {2 ^ n} \ right）+ \ left（\ sum_ {k = 0} ^ {\ left \ lfloor \ frac n2 \ right \ rfloor} \ frac {{n \ choice 2k} 5 ^ {k-1}} {2 ^ n} \ right）\ sqrt 5$

行列指数を使用してフィボナッチ数を計算するためのもう1つの優れた方法があります。

$\ left（\ begin {matrix} 1＆1 \ 1＆0 \ end {matrix} \ right）^ n = \ left（\ begin {matrix} F_n＆F_ {n-1} \ F_ {n-1}＆F_ {n-2} \ end {matrix} \ right）$

あなたが賢いなら、これはO（log n）で行うことができます。

私はこれらをHaskellに実装することになりました。 fib1は行列指数でありfib2、上記のように閉形式の式の正確な整数変換です。GHC 7.0.3でコンパイルしたときにCriterionで測定すると、それぞれのランタイムは次のようになります。
行列指数関数の実行時間閉じた形式のランタイム

import Control.Arrow
import Data.List
import Data.Ratio

newtype Matrix2 a = Matrix2 (a, a, a, a) deriving (Show, Eq)
instance (Num a) => Num (Matrix2 a) where
    Matrix2 (a, b, c, d) * Matrix2 (e, f, g, h) =
        Matrix2 (a*e+b*g, a*f+b*h, c*e+d*g, c*f+d*h)
    fromInteger x = let y = fromInteger x in Matrix2 (y, 0, 0, y)
fib1 n = let Matrix2 (_, x, _, _) = Matrix2 (1, 1, 1, 0) ^ n in x

binom n =
    scanl (\a (b, c)-> a*b `div` c) 1 $
    takeWhile ((/=) 0 . fst) $ iterate (pred *** succ) (n, 1)
evens (x:_:xs) = x : evens xs
evens xs = xs
odds (_:x:xs) = x : odds xs
odds _ = []
iterate' f x = x : (iterate' f $! f x)
powers b = iterate' (b *) 1
esqrt e n = x where
    (_, x):_ = dropWhile ((<=) e . abs . uncurry (-)) $ zip trials (tail trials)
    trials = iterate (\x -> (x + n / x) / 2) n
fib' n = (a, b) where
    d = 2 ^ n
    a = sum (zipWith (*) (odds $ binom n) (powers 5)) % d
    b = sum (zipWith (*) (evens $ binom n) (powers 5)) % d
fib2 n = numerator r `div` denominator r where
    (a, b) = fib' n
    l = lcm (denominator a) (denominator a)
    r = a + esqrt (1 % max 3 l) (b * b / 5) + 1 % 2

score 4 · Accepted Answer

using System;
using Nat = System.Numerics.BigInteger; // needs a reference to System.Numerics

class Program
{
    static void Main()
    {
        Console.WriteLine(Fibonacci(1000));
    }

    static Nat Fibonacci(Nat n)
    {
        if (n == 0) return 0;
        Nat _, fibonacci = MatrixPower(1, 1, 1, 0, Nat.Abs(n) - 1, out _, out _, out _);
        return n < 0 && n.IsEven ? -fibonacci : fibonacci;
    }

    /// <summary>Calculates matrix power B = A^n of a 2x2 matrix.</summary>
    /// <returns>b11</returns>
    static Nat MatrixPower(
        Nat a11, Nat a12, Nat a21, Nat a22, Nat n,
        out Nat b12, out Nat b21, out Nat b22)
    {
        if (n == 0)
        {
            b12 = b21 = 0; return b22 = 1;
        }

        Nat c12, c21, c22, c11 = MatrixPower(
            a11, a12, a21, a22,
            n.IsEven ? n / 2 : n - 1,
            out c12, out c21, out c22);

        if (n.IsEven)
        {
            a11 = c11; a12 = c12; a21 = c21; a22 = c22;
        }

        b12 = c11 * a12 + c12 * a22;
        b21 = c21 * a11 + c22 * a21;
        b22 = c21 * a12 + c22 * a22;
        return c11 * a11 + c12 * a21;
    }
}

score 3 · Accepted Answer

Doubleデータ型の上限値は1.7x10^308です。

1474の計算には、1つのステップで約1.1 x 10^308の値が含まれます。

したがって、1475年までに、Doubleが表すことができるものを確実に超えています。残念ながら、C＃の唯一のより大きなプリミティブであるDecimal（128ビット数）は、歳差運動が非常に高くなるように設計されていますが、範囲は比較的狭くなっています（最大で約10 ^ 28）。

10 ^ 308より大きい数値をある程度の小数精度で処理できるカスタムデータ型を設計しないと、これを行う方法がわかりません。そうは言っても、それが役立つシナリオを想像できるので、誰かがすでにそのようなクラスを作っているかもしれません。

doubleを参照してください：http：//msdn.microsoft.com/en-us/library/678hzkk9 （v = VS.80）.aspx

および小数： http： //msdn.microsoft.com/en-us/library/364x0z75 （v = VS.80）.aspx

score 2 · Accepted Answer

'Solver Foundation'ライブラリには、いくつかの'big'数値タイプが含まれているようです。そのRationalタイプが必要な精度と範囲を提供する可能性があります。これは、2つの値の比率として有理数を表しBigIntegerます。（それはそれ自身をもたらしますBigInteger-私はそれが.NET 4が出荷される前に書かれたと思います。）

理論的には、これにより非常に大きな数を表すことができますが、非常に正確に表すこともできます。（明らかに、あなたの公式は有理数を扱いませんが、浮動小数点もここでの近似です。）

Rationalこれは、を他の何かの力に引き上げるための方法を提供します：http: //msdn.microsoft.com/en-us/library/microsoft.solverfoundation.common.rational.power (v=VS.93).aspx

score 1 · Accepted Answer

最も速い（そして最も汚い）？：D

private Double dirty_math_function(Int32 input){
       Double part1 = (1 / Math.Sqrt(5));
       Double part2 = Math.Pow(((1 + Math.Sqrt(5)) / 2), input);
       Double part3 = Math.Pow(((1 - Math.Sqrt(5)) / 2), input);
       return (part1 * part2) - (part1 * part3);
 }

private Double FibSequence(Int32 input) {
  if(input < 1475)
       return dirty_math_function(input);
  else{
       return (FibSequence(input -1) + FibSequence(intput -2));
  }
}

score 1 · Accepted Answer

ご指摘のとおり、BigIntegerにはSqrtメソッドは実装されていません。ただし、自分で実装できます。

BigIntegerの平方根を計算する（System.Numerics.BigInteger）

ただし、精度はコードの問題です。

score 1 · Accepted Answer

ここでの多くの回答は、複雑さをO（log（n））に最小化できることを示唆しています。log（n）アプローチの整数実装を試してみませんか？

まず、Fibonacchiのシーケンスから2つの用語が与えられていると考えてください：F(n)とF(n+1)。より大きな項は、およびの線形関数としてF(n+k)記述できるという論理です。F(n)F(n+1)

 F(n+k) = Ck1*F(n) + Ck2*F(n+1)

これらの係数（これはにのみ依存しますk）を計算し（興味深いことに、これらもフィボナッチ数列です！）、それらを使用してより速く前進し、次にそれらを再度計算して、より大きな値でkさらに速く前進できるようにすることができます。の上。

score 0 · Accepted Answer

これは正確な式ではなく、推定値のみを示します。また、浮動小数点演算は数値ごとに6〜8バイトに制限されているため、数値が大きくなると偏差が大きくなります。
サイクルで大きな整数の加算を使用しないのはなぜですか、それは問題なく動作するはずです。浮動小数点よりもはるかに優れています。

score 0 · Accepted Answer

問題は、（5 ^（1/2）^ 1475）がintを簡単にオーバーフローすることです。あなたがしなければならないことは、ハードタイプのデータ型を使用するのではなく、メモリから（ビットごとに）数学を行うことを処理するための「大きな数学」ライブラリを書くことです。それは痛みですが、私は知っています。二乗と乗算の方法を調べてください。

c#-4.0 - フィボナッチの計算

9 に答える 9

Related

Reference