c++ - 在 C++ 中准确计算斐波那契数列？

Question

我真的很困惑。我正在尝试计算斐波那契数，但随着它们变得越来越大，数字开始变得错误。我不知道为什么。

如何使用 Binet 公式计算准确的斐波那契数，据我了解，这应该始终返回整数？

这是我一直在尝试使用的东西。

http://ideone.com/e6t6h

看到数字上升。变得很奇怪？

这里我用 cout.precision(15); 打印出来

http://ideone.com/XREh2

这里我用 cout << fixed << blah blah; 打印出来;

在这里，我使用程序循环通过遍历迭代来计算它。

这个比使用 Binet 公式的更准确。

无论如何。谁有任何我可以查看的代码可以计算 F(n) 而无需使用 Binet 公式迭代 (n) 的每个级别？

Answer 1

要使用比奈公式准确计算斐波那契数，您需要准确解释√5。由于√5是无理数，所以不能用double来准确表示。或 float ，因此 Binet 的公式不适用于这些类型(但是，计算中的舍入会导致一些小输入的精确结果)。由于斐波那契数是整数，您可以使用 double 从 Binet 公式中获得精确结果。或 float通过四舍五入获得更多参数，

double binet(unsigned int n)
{
    static const double phi = (1 + sqrt(5))*0.5;
    double fib = (pow(phi,n) - pow(1-phi,n))/sqrt(5);
    return round(fib);
}

这将为几乎所有 n 返回正确的结果足够小以至于结果可以精确表示为 double .然而，这些并不多。 double通常只有 53 位精度，因此只有小于 2⁵³ 的斐波那契数可以精确表示为 double (加上一些较大的可以被 2 的足够高的幂整除)。最后一个小于 2⁵³ 的斐波那契数是 F(77)，但是 F(78) 可以被 8 整除，所以也可以精确表示为 double具有 53 位精度。但是，以上仅对 n <= 70 产生正确的结果这里，从 71 开始，舍入误差太大(顺便说一句，Binet 公式使用 doubles 的结果在这里总是太大，所以使用 floor 而不是 round 也会为 F(71 ), 但没有进一步).

使用标准数据类型，没有多少斐波那契数可以精确表示，最后一个适合(无符号)64 位类型的是 F(93)；对于 128 位，最后一个是 F(186)。对于如此小的索引，通过简单的迭代算法几乎没有任何收获

unsigned long long fibonacci(unsigned int n)
{
    unsigned long long a = 0, b = 1;
    for(; n > 0; --n)
    {
        b += a;
        a = b-a;
    }
    return a;
}

除非你使用查找表

static const unsigned long long fibs[94] = { 0, 1, 1, 2, ... , 12200160415121876738ull };

为了获得准确的结果，必须将 √5(和/或 φ)视为符号常数并使用它来计算公式。这相当于评估环中的公式

ℤ[φ] = { a + b*φ : a, b ∈ ℤ }

ℚ(√5) 中的代数整数，利用 φ² = 1 + φ 的事实.等价于比奈公式是

φ^n = F(n-1) + φ*F(n)

可用于通过O(log n)步重复平方来高效计算斐波那契数(但注意F(n)有Θ(n)位，所以位运算的次数不能低于O (n)).比 Vanilla 重复平方使用稍微更有效的版本

φ^(2n) = (φ^n)² = (F(n-1) + φ*F(n))² = F(n-1)² + φ*2*F(n-1)*F(n) + φ²*F(n)²
       = (F(n-1)² + F(n)²) + φ*(2*F(n-1)*F(n) + F(n)²)

发现 F(2n) = 2*F(n)*F(n-1) + F(n)² = 2*F(n)*F(n+1) - F(n)² = F(n)*(F(n+1) + F(n-1))和 F(2n+1) = F(n)² + F(n+1)² , 使用 φ² = 1 + φ .这些公式允许从 F(n) 和 F(n+1) 计算 F(2n)、F(2n+1) 和 F(2n+2)，每个数最多有两次乘法和两次加法/减法，这给出了计算对的算法 (F(n),F(n+1))在 O(log n) 步中，只有两个数字作为状态( Vanilla 重复平方使用四个数字作为状态，需要更多的乘法)。

一个从左到右的迭代算法是

unsigned long long fib(unsigned int n){
    if (n == 0) return 0;
    unsigned int h = n/2, mask = 1;
    // find highest set bit in n, can be done better
    while(mask <= h) mask <<= 1;
    mask >>= 1;
    unsigned long long a = 1, b = 1, c; // a = F(k), b = F(k+1), k = 1 initially
    while(mask)
    {
        c = a*a+b*b;        // F(2k+1)
        if (n&mask)
        {
            b = b*(b+2*a);  // F(2k+2)
            a = c;          // F(2k+1)
        } else {
            a = a*(2*b-a);  // F(2k)
            b = c;          // F(2k+1)
        }
        mask >>= 1;
    }
    return a;
}

使用任意精度类型而不是 unsigned long long , 这允许快速计算大的斐波那契数。但当然，任意精度库通常带有自己优化的 Fibonacci 函数，因此您自己实现它有点没有实际意义。