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}$ 小于一，所以 $-\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 \选择 k}\sqrt 5^k}{2^n\sqrt 5}$
$=\left(\sum_{k=0}^{\left\lfloor\frac{n-1}2\right\rfloor}\frac{{n\选择2k+1}5^k}{2^n} \right)+\left(\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}\frac{{n\选择 2k}5^{k-1}}{2^n} \right)\sqrt 5$

还有另一种计算斐波那契数的巧妙方法，使用矩阵求幂：

$\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}\结束{矩阵}\右）$

如果你很聪明，这可以在 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.7 x 10^308

1474 的计算包括一步 ~ 1.1 x 10^308 的值。

所以，到 1475 年，你肯定超过了 Double 所能代表的。不幸的是，C# 唯一较大的原语 Decimal（一个 128 位数字）被设计为具有非常高的进动但范围相对较小（仅高达 10^28 左右）。

如果没有设计可以处理大于 10^308 且具有一定小数精度的数字的自定义数据类型，我看不到这样做的方法。也就是说，那里的某个人可能已经做了这样的课程，因为我可以想象它可以派上用场的场景。

见双： 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”库似乎包含一些“大”数字类型。它的Rational类型可能会为您提供所需的精度和范围。它将有理数表示为两个BigInteger值的比率。（它自带BigInteger- 我猜它是在 .NET 4 发布之前编写的。）

从理论上讲，这使它能够表示非常大的数字，但也能表示很大的精度。（显然你的公式不处理有理数，但浮点也是这里的近似值。）

它提供了一种将 a 提升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) 方法的整数实现呢？

首先，考虑给定斐波那契数列中的两个项：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