12

我收到了这个用于计算斐波那契数列的非递归函数。

替代文字

因此,我编写了一些 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);
}

而且,不,这不是家庭作业。只是一个缓慢的一天的“简单”问题。

4

9 回答 9

14

我不认为 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用适当的 ab计算(它们是有理的,可以用 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
于 2010-12-01T19:22:53.963 回答
4
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;
    }
}
于 2013-04-18T20:46:34.787 回答
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

于 2010-12-01T18:58:30.790 回答
2

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

于 2010-12-02T10:21:02.747 回答
1

最快的(也是最脏的)?: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));
  }
}
于 2010-12-27T14:08:03.747 回答
1

正如您正确指出的那样,没有为 BigInteger 实现 Sqrt 方法。你可以自己实现它:

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

不过,精度应该仍然是您的代码的问题。

于 2010-12-01T19:30:21.587 回答
1

这里的许多答案表明复杂性可以最小化到 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以便能够更快地前进,等等上。

于 2010-12-01T19:45:31.387 回答
0
  1. 这不是一个精确的公式,它只会给你估计值。而且,由于浮点运算被限制为每个数字 6-8 个字节,因此偏差会随着数字的增加而增加。
  2. 为什么不在循环中使用大整数加法,它应该可以工作。远胜于浮点数。
于 2010-12-28T13:23:00.873 回答
0

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

于 2010-12-01T19:00:45.187 回答