计算斐波那契数

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);
}

而且，不，这不是家庭作业。对于缓慢的一天来说，这只是一个“简单”的问题。

Answer 1

我认为 C# 没有一个具有足够浮动精度和范围的数据类型来简单地处理这个问题。

如果您确实想走这条路，您可以注意到共轭 小于 1，因此 与舍入到最接近的整数相同，因此您可以简化解决方案以查找 。然后使用二项式展开，这样您只需计算 ，带有适当的 a 和 b （它们是有理数，可以计算与 BigInteger 完全相同）。如果你仍然回到 Double ，你仍然不会比 1475 更远，但你应该能够弄清楚如何仅使用精确的整数数学来完成这部分 ☺

---

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

如果你聪明的话，这可以在 O(log n) 内完成。

---

我最终在 Haskell 中实现了这些。 fib1 是矩阵求幂，fib2 是封闭式公式的精确整数转换，如上所述。它们各自的运行时如下所示，由 Criterion 测量://www.haskell.org/ghc/download_ghc_7_0_3" rel="nofollow noreferrer">GHC 7.0.3：

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

Answer 2

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;
    }
}

Answer 3

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

Answer 4

将出现“Solver Foundation”库包括一些“大”数字类型。它的 Rational 类型可能会为您提供所需的精度和范围。它将有理数表示为两个 BigInteger 值的比率。 （它带来了自己的 BigInteger - 我猜它是在 .NET 4 发布之前编写的。）

理论上，这使其能够表示非常大的数字，而且还能够表示很高的精度。 （显然你的公式不处理有理数，但浮点在这里也是一个近似值。）

它提供了一种将 Rational 提升到其他值的幂的方法：http://msdn.microsoft.com/ en-us/library/microsoft.solverfoundation.common.rational.power(v=VS.93).aspx

Answer 5

正如您正确指出的那样，没有为 BigInteger 实现 Sqrt 方法。
不过，您可以自己实现它：

计算 BigInteger 的平方根 ( System.Numerics.BigInteger)

不过，精度仍然是您的代码的问题。

Answer 6

这里的许多答案表明复杂性可以最小化到 O(log(n))。为什么不尝试 log(n) 方法的整数实现？

首先，考虑斐波那契数列中的两项：F(n) 和 F(n+1)。按照逻辑，较大的项 F(n+k) 可以写成 F(n) 和 F(n+1) 的线性函数code> 因为

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

您可以只计算这些系数（仅取决于 k），（有趣的是，它们也是斐波那契数列！）并使用它们来更快地前进，然后再次计算它们以获得更大的值k 能够进步得更快，等等。

Answer 7

最快（也是最脏）的？ ：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));
  }
}

Answer 8

问题是 (5^(1/2)^1475) 很容易溢出 int。您所要做的就是编写一个“大数学”库来处理从内存中（逐位）进行数学运算，而不是使用硬类型数据类型。这是一个痛苦，但是，我知道。查找平方和乘法。

Answer 9

1. 这不是一个精确的公式，它只能为您提供估计值。而且，由于浮点运算限制为每个数字 6-8 个字节，因此数字越大偏差就会越大。
2. 为什么不在循环中使用大整数加法，它应该可以正常工作。比浮点好得多。