在Powers和Fibonacci中改进C#小数精度

Question

我试图解决负数和大数的斐波那契序列，并得出以下代码和算法。我确信该算法是可行的，但我遇到的问题是，对于非常大的数字，结果的精度不正确。下面是代码。

public class Fibonacci
    {
        public static BigInteger fib(int n)
        {
            decimal p = (decimal) (1 + Math.Sqrt(5)) / 2;
            decimal q = (decimal) (1 - Math.Sqrt(5)) / 2;
            decimal r = (decimal) Math.Sqrt(5);
            Console.WriteLine("n: {0} p: {1}, q: {2}, t: {3}",
              n,
              p,
              q,
              (Pow(p, n) - Pow(q, n)) / r);

            return (BigInteger) (Decimal.Round((Pow(p, n) - Pow(q, n)) / r));
        }

        public static decimal Pow(decimal x, int y)
        {
            if(y < 0)
                return 1 / Pow(x, -1 * y);
            else if(y == 0)
                return 1;
            else if(y % 2 == 0)
            {
                decimal z = Pow(x, y / 2);
                return z * z;
            }
            else if(y % 2 == 1)
                return Pow(x, y - 1) * x;
            else
                return 1;
        }

小数 如果我们取一个大数，比如-96来求斐波那契，我得到的结果是-51680708573203484173 但实际数字是-51680708854858323072. 我检查了四舍五入的方法，但似乎在某个地方，我的结果失去了精度，没有正确保存其值。我以为使用小数就能解决这个精度问题（之前用的是双数），但是没有用。

我的代码中哪里不正确地丢失了精度，还是我的代码有其他问题被我误诊了？

Answer 1

试试这个。

public static BigInteger Fibonacci(int n)
    {
        BigInteger a = 0;
        BigInteger b = 1;
        for (int i = 31; i >= 0; i--)
        {
            BigInteger d = a * (b * 2 - a);
            BigInteger e = a * a + b * b;
            a = d;
            b = e;
            if ((((uint)n >> i) & 1) != 0)
            {
                BigInteger c = a + b;
                a = b;
                b = c;
            }
        }
        return a;
    }

好运!

Answer 2

如你所写。decimal 有大约28位小数点的精度。然而， Math.Sqrt(5)，是一个 double，不会。

使用更精确的5的平方根，可以让这个算法保持更长时间的精确性，当然最终还是会受到精度的限制，只是后来。

public static BigInteger fib(int n)
{
    decimal sqrt5 = 2.236067977499789696409173668731276235440618359611525724270m;
    decimal p = (1 + sqrt5) / 2;
    decimal q = (1 - sqrt5) / 2;
    decimal r = sqrt5;

    return (BigInteger) (Decimal.Round((Pow(p, n) - Pow(q, n)) / r));
}

这样一来 fib(96) = 51680708854858323072 这是正确的。但在128处又变成了错误。