幂和斐波那契的 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 位十进制数字的精度。然而，作为 double，Math.Sqrt(5) 却不是。

使用更准确的平方根 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处又变错了。

幂和斐波那契的 C# 小数精度改进

C# Decimal Precision Improvement in Powers and Fibonacci

c#

precision

fibonacci