在C ++中准确计算斐波纳契数？ [英] Calculating Fibonacci Number accurately in C++?

问题描述

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

I am really confused. I am trying to calculate Fibonacci numbers, but as they get larger and large the numbers start to become wrong. and I do not know why.

如何使用Binet的公式计算准确的斐波纳契数字，我的理解是，这应该总是返回一个整数？

How do you calculate accurate Fibonacci numbers using Binet's Formula, it is my understanding that this should always return a integer?

这是我一直在努力工作。

Here is what I have been trying to work with.

http://ideone.com/e6t6h

查看数字上升。

这里我使用cout.precision（15）打印出来;

here I print it out with a cout.precision(15);

a href =http://ideone.com/XREh2 =nofollow> http://ideone.com/XREh2

http://ideone.com/XREh2

这里I使用cout<<固定< blah blah;

here I print it out with cout << fixed << blah blah;

这里我使用了一个程序循环来计算它通过迭代。

Here I have used a procedural loop to calculate it by going though the iterations.

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

This one is more accurate, than the one using Binet's formula.

无论如何。任何人都有任何代码，我可以看看，可以计算F（n）与需要通过使用Binet的公式，每个级别的（n）迭代。

Anyway. dose anyone have any code I can look at that can compute F(n) with out the need to iterate though every level of (n) by using Binet's formula?

推荐答案

要使用Binet公式准确计算斐波那契数，需要准确解释√ 5。由于√ 5是不合理的，不能使用 double 或 float 准确表示，因此Binet的公式不起作用与这些类型（然而，计算中的舍入导致一些小输入的精确结果）。由于斐波那契数字是整数，因此您可以使用 double 或 float 从Binet的公式中获得更精确的结果

To accurately calculate Fibonacci numbers using Binet's formula, you need an accurate interpretation of √5. Since √5 is irrational, it cannot be accurately represented using double or float, hence Binet's formula doesn't work with these types (however, the rounding in the computation leads to exact results for some small inputs). Since the Fibonacci numbers are integers, you can get exact results from Binet's formula using double or float for more arguments by rounding afterwards,

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 。但是，这些不是很多。 A double 通常只有53位精度，因此只有小于2 ⁵³ 的斐波纳契数字可以精确表示为 double （加上几个较大的可以用2的足够高的幂除尽）。最后一个小于2 ⁵³ 的斐波那契数是F（77），但是F（78）可以被8整除，因此也可以表示为 double 具有53位精度。然而，上述仅在 n <= 70 中产生正确的结果，这里，从71开始，舍入误差太大（附带地，Binet的公式使用 doubles 总是太大，所以使用 floor 而不是 round

That will return the correct result for almost all n small enough that the result can be exactly represented as a double. These aren't many, however. A double typically has only 53 bits of precision, so only Fibonacci numbers smaller than 2⁵³ can be exactly represented as a double (plus a few larger ones divisible by sufficiently high powers of 2). The last Fibonacci number smaller than 2⁵³ is F(77), but F(78) is divisible by 8, so also exactly representable as a double with 53 bits of precision. However, the above produces correct results only for n <= 70 here, from 71 on, the rounding error is too large (incidentally, the result of Binet's formula using doubles is always too large here, so using floor instead of round would produce the correct result also for F(71), but no further).

对于标准数据类型，不是很多斐波那契数字是可以精确表示的，最后一个适合（无符号）64位类型是F（93）;对于128位，最后一个是F（186）。对于这样小的索引，实际上没有什么可以通过直接的迭代算法获得。

With the standard datatypes, not many Fibonacci numbers are exactly representable, the last to fit in an (unsigned) 64 bit type is F(93); for 128 bits, the last is F(186). For so small indices, there is practically nothing to be gained over the straightforward iterative algorithm

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（和/或φ）作为符号常量并使用它来计算公式。这等于评价环中的公式

For accurate results, one must treat √5 (and/or φ) as a symbolic constant and evaluate the formula using that. This amounts to evaluating the formula in the ring

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

c>，使用φ²= 1 +φ的事实。等于Binet的公式是

of algebraic integers in ℚ(√5), using the fact that φ² = 1 + φ. Equivalent to Binet's formula is

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

可用于通过在O（log n）步骤中重复平方来有效地计算斐波纳契数字（但注意F n）具有&θ（n）位，因此位操作的数量不能低于O（n））。比香草重复平方使用略高的版本

which can be used to efficiently calculate Fibonacci numbers by repeated squaring in O(log n) steps (but note that F(n) has Θ(n) bits, so the number of bit operations can't be lower than O(n)). A slightly more efficient version than the vanilla repeated squaring uses

φ^(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 = 2 * F（n）* F（n + 1）-F（n）2 = F（n）*（F（n + 1）+ F（n-1） code> F（2n + 1）= F（n）2 + F（n + 1）2 ，使用φ²= 1 +φ。这些公式允许利用至多两次乘法和每个数的两次加法/减法来从F（n）和F（n + 1）计算F（2n），F（2n + 1）和F（2n + 2）算法来计算在O（log n）步中仅具有两个数字作为状态的对（F（n），F（n + 1））（香草重复平方使用四数字作为状态，需要更多的乘法）。

finding 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)) and F(2n+1) = F(n)² + F(n+1)², using φ² = 1 + φ. These formulae allow calculating F(2n), F(2n+1) and F(2n+2) from F(n) and F(n+1) with at most two multiplications and two additions/subtractions per number, which gives an algorithm to calculate the pair (F(n),F(n+1)) in O(log n) steps with only two numbers as state (vanilla repeated squaring uses four numbers as state and needs a few more multiplications).

一个迭代左到右的算法是

An iterative left-to-right algorithm is

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函数，所以它自己实现它是一种勉强。

With an arbitrary precision type instead of unsigned long long, that allows the fast calculation of large Fibonacci numbers. But of course arbitrary precision libraries often come with their own optimised Fibonacci functions, so it's kind of moot to implement it yourself.

这篇关于在C ++中准确计算斐波纳契数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！