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.
我真的很困惑。我正在尝试计算斐波纳契数,但随着它们越来越大,数字开始变得错误。同时我不知道为什么。
How do you calculate accurate Fibonacci numbers using Binet's Formula, it is my understanding that this should always return a integer?
你如何使用Binet的公式计算准确的斐波纳契数,我的理解是这应该总是返回一个整数?
Here is what I have been trying to work with.
这是我一直在努力的方法。
See as the number goes up. it gets all weird?
看到数字上升。这有点奇怪吗?
here I print it out with a cout.precision(15);
在这里,我用cout.precision打印出来(15);
here I print it out with cout << fixed << blah blah;
在这里,我用cout << fixed << blah blah;
Here I have used a procedural loop to calculate it by going though the iterations.
在这里,我使用了一个程序循环来通过迭代来计算它。
This one is more accurate, than the one using Binet's formula.
这个比使用Binet的公式更准确。
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?
无论如何。剂量任何人都有任何我可以看到的代码可以计算F(n)而不需要通过使用Binet的公式迭代每个级别的(n)?
3 个解决方案
#1
15
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,
要使用Binet公式精确计算斐波那契数,您需要准确解释√5。由于√5是不合理的,因此无法使用double或float精确表示,因此Binet的公式不适用于这些类型(但是,计算中的舍入会导致某些小输入的精确结果)。由于Fibonacci数是整数,你可以通过使用double或float获得更多参数的Binet公式的精确结果,然后通过舍入,
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);
}
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 253 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 253 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).
这将返回几乎所有n足够小的正确结果,结果可以精确地表示为double。然而,这些并不多。双精度通常只有53位精度,因此只有小于253的斐波那契数可以精确地表示为双精度(加上一些较大的精度可被2的足够高的幂整除)。最后一个小于253的斐波纳契数是F(77),但是F(78)可以被8整除,因此也可以精确地表示为具有53位精度的双精度。但是,上面只为n <= 70产生了正确的结果,从71开始,舍入误差太大(顺便说一句,Binet的公式使用双精度的结果总是太大,所以使用floor而不是round会产生对于F(71)也是正确的结果,但没有进一步的结果。
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
对于标准数据类型,没有多少斐波纳契数可以准确表示,最后一个适合(无符号)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;
}
unless you use a lookup table
除非你使用查找表
static const unsigned long long fibs[94] = { 0, 1, 1, 2, ... , 12200160415121876738ull };
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
为了获得准确的结果,必须将√5(和/或φ)视为符号常数,并使用它来评估公式。这相当于评估环中的公式
ℤ[φ] = { a + b*φ : a, b ∈ ℤ }
of algebraic integers in ℚ(√5), using the fact that φ² = 1 + φ. Equivalent to Binet's formula is
使用φ2= 1 +φ的事实,在ℚ(√5)中使用代数整数。相当于比奈的公式是
φ^n = F(n-1) + φ*F(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
这可以用来通过O(log n)步骤中的重复平方来有效地计算Fibonacci数(但是注意F(n)具有Θ(n)位,因此位操作的数量不能低于O(n) )。比香草重复平方使用的版本略高一些
φ^(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)²)
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).
求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)²,使用φ2= 1 +φ。这些公式允许从F(n)和F(n + 1)计算F(2n),F(2n + 1)和F(2n + 2),每个数最多两次乘法和两次加法/减法,这给出了在O(log n)步骤中计算对(F(n),F(n + 1))的算法只有两个数作为状态(香草重复平方使用四个数作为状态并需要更多的乘法)。
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;
}
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.
使用任意精度类型而不是无符号long long,可以快速计算大的Fibonacci数。但是当然任意精度库通常都带有自己优化的Fibonacci函数,因此自己实现它是没有意义的。
#2
2
In general, floats and doubles are not designed to represent numbers accurately. Their purpose is to represent real numbers in a wide range. If you do want infinite precision, you could try looking into http://gmplib.org/
通常,浮动和双打不是为了准确地表示数字而设计的。它们的目的是在很大范围内表示实数。如果您确实需要无限精度,可以尝试查看http://gmplib.org/
#3
1
Have you tried including <cmath> rather than <math.h>, math.h might not have an overloaded version of sqrt as it is for C
您是否尝试过包含
#1
15
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,
要使用Binet公式精确计算斐波那契数,您需要准确解释√5。由于√5是不合理的,因此无法使用double或float精确表示,因此Binet的公式不适用于这些类型(但是,计算中的舍入会导致某些小输入的精确结果)。由于Fibonacci数是整数,你可以通过使用double或float获得更多参数的Binet公式的精确结果,然后通过舍入,
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);
}
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 253 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 253 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).
这将返回几乎所有n足够小的正确结果,结果可以精确地表示为double。然而,这些并不多。双精度通常只有53位精度,因此只有小于253的斐波那契数可以精确地表示为双精度(加上一些较大的精度可被2的足够高的幂整除)。最后一个小于253的斐波纳契数是F(77),但是F(78)可以被8整除,因此也可以精确地表示为具有53位精度的双精度。但是,上面只为n <= 70产生了正确的结果,从71开始,舍入误差太大(顺便说一句,Binet的公式使用双精度的结果总是太大,所以使用floor而不是round会产生对于F(71)也是正确的结果,但没有进一步的结果。
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
对于标准数据类型,没有多少斐波纳契数可以准确表示,最后一个适合(无符号)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;
}
unless you use a lookup table
除非你使用查找表
static const unsigned long long fibs[94] = { 0, 1, 1, 2, ... , 12200160415121876738ull };
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
为了获得准确的结果,必须将√5(和/或φ)视为符号常数,并使用它来评估公式。这相当于评估环中的公式
ℤ[φ] = { a + b*φ : a, b ∈ ℤ }
of algebraic integers in ℚ(√5), using the fact that φ² = 1 + φ. Equivalent to Binet's formula is
使用φ2= 1 +φ的事实,在ℚ(√5)中使用代数整数。相当于比奈的公式是
φ^n = F(n-1) + φ*F(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
这可以用来通过O(log n)步骤中的重复平方来有效地计算Fibonacci数(但是注意F(n)具有Θ(n)位,因此位操作的数量不能低于O(n) )。比香草重复平方使用的版本略高一些
φ^(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)²)
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).
求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)²,使用φ2= 1 +φ。这些公式允许从F(n)和F(n + 1)计算F(2n),F(2n + 1)和F(2n + 2),每个数最多两次乘法和两次加法/减法,这给出了在O(log n)步骤中计算对(F(n),F(n + 1))的算法只有两个数作为状态(香草重复平方使用四个数作为状态并需要更多的乘法)。
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;
}
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.
使用任意精度类型而不是无符号long long,可以快速计算大的Fibonacci数。但是当然任意精度库通常都带有自己优化的Fibonacci函数,因此自己实现它是没有意义的。
#2
2
In general, floats and doubles are not designed to represent numbers accurately. Their purpose is to represent real numbers in a wide range. If you do want infinite precision, you could try looking into http://gmplib.org/
通常,浮动和双打不是为了准确地表示数字而设计的。它们的目的是在很大范围内表示实数。如果您确实需要无限精度,可以尝试查看http://gmplib.org/
#3
1
Have you tried including <cmath> rather than <math.h>, math.h might not have an overloaded version of sqrt as it is for C
您是否尝试过包含