关于Binet公式的秘诀 [英] Smth about Binet formula
问题描述
为什么Binet公式(O(LogN)，但不完全正确)在时间上比迭代方法(O(n))效果差?
Why does the Binet formula( O(LogN), but it is not exactly ) work worse in time than the iteration method( O(n) )?
static double SQRT5 = Math.Sqrt(5);
static double PHI = (SQRT5 + 1) / 2;
public static int Bine(int n)
{
return (int)(Math.Pow(PHI, n) / SQRT5 + 0.5);
}
static long[] NumbersFibonacci = new long[35];
public static void Iteracii(int n)
{
NumbersFibonacci[0] = 0;
NumbersFibonacci[1] = 1;
for (int i = 1; i < n - 1; i++)
{
NumbersFibonacci[i + 1] = NumbersFibonacci[i] + NumbersFibonacci[i - 1];
}
}
推荐答案
如果假定算术运算为O(1)，则使用Binet的公式为O(1)，典型的迭代实现为O(n).
If arithmetic operations are assumed to be O(1) then using Binet's formula is O(1) and the typical iterative implementation is O(n).
但是，如果我们假设算术运算为O(1)，那么即使 fibo(n)是常见的访谈和电话屏幕主题，实际上它也没什么用以一种典型的方式来实现它是有道理的-除非被告知我们要忽略标准编程语言整数和浮点数的有限性.斐波那契数呈指数增长.只要没有选择朴素的递归实现，它们就会在选择特定算法之前很早就溢出标准编程语言类型.
However, if we assume arithmetic operations are O(1) then, even though fibo(n) is a common interview and phone screen topic, it actually makes little sense to implement it in the typical way -- barring being told we are to ignore the finiteness of standard programming language integers and floating point numbers. The Fibonacci numbers grow exponentially. They overflow standard programming language types long before the particular algorithm chosen matters, as long as that is one did not choose the naive recursive implementation.
具体来说，这是在C#中返回第n个斐波那契数的两种实现.顶级的实现了Binet的双精度封闭形式解决方案，并将其强制转换为长整数，在C#中将为64位宽.第二个是迭代版本:
To get specific, here are two implementations of returning the nth Fibonacci numbers in C#. The top one implements Binet’s closed form solution on doubles and casts to a long, which in C# will be 64 bits wide. The second one is the iterative version:
static long constant_time_fibo(long n)
{
double sqrt_of_five = Math.Sqrt(5.0);
return (long) (
(Math.Pow(1.0 + sqrt_of_five, n) - Math.Pow(1.0 - sqrt_of_five, n)) /
(sqrt_of_five * Math.Pow(2.0, n))
);
}
static long linear_time_fibo(long n)
{
long previous = 0;
long current = 1;
for (int i = 1; i < n; i++)
{
long temp = current;
current = previous + current;
previous = temp;
}
return current;
}
static void Main(string[] args)
{
for (int i = 1; i < 100; i++)
Console.WriteLine("{0} => {1} {2}", i,
constant_time_fibo(i), linear_time_fibo(i) );
}
当我运行这段代码时，由于浮点错误，我得到的恒定时间算法未能在n = 72左右匹配迭代实现，而由于溢出，迭代方法在n = 92失败.如果我使用的是32位类型而不是64位，那么这种情况会更早发生.
when I run this code I get the constant time algorithm failing to match the iterative implementation at around n = 72 due to floating point error and the iterative approach failing at n = 92 due to overflow. If I had used 32 bit types instead of 64 bits this would have happened even sooner.
九十二个项目什么都不是.如果您实际上需要第n个斐波那契数，并且只关心适合64位的斐波那契数，那么在非人为情况下-而不是用于作业或白板问题-它应该花O(1)的时间因为存在Binet公式，但是您应该使用其中包含92个项目的查找表.在C ++中，您甚至可以使用 constexpr 函数在编译时生成92个项目.
Ninety-two items is nothing. If you need the nth fibonacci number in practice and only care about fibonacci numbers that fit in 64 bits, in a non-contrived situation -- not for a homework assignment or for a whiteboard question -- it should take O(1) time not because of the existence of Binet's formula but because you should use a lookup table with 92 items in it. In C++ you could even generate the 92 items at compile time with a constexpr function.
另一方面，如果我们要谈论任意大数的算术，那么这个问题会更有趣.Binet公式中的指数都是整数.您可以仅使用任意大的整数算法来实现Binet的公式-您无需计算任何5的平方根，只需跟踪"5的平方根在哪里"，因为它们最终将被抵消.您以(a +b√5)/c之类的二项式形式进行计算，但是由于ϕ的怪异代数性质，所有非理性和所有非整数数学都被魔术抵消了.查找finding ^ n时，您无需实际计算任何√5.如果您使用"通过平方求幂"，这将导致O(log n)实现--反正O(log n)算术运算；整个过程的时间复杂度取决于您使用的任意大型算术库的时间复杂度.
If on the other hand if we are talking about arbitrarily large number arithmetic then the question is somewhat more interesting. The exponents in Binet’s formula are all integers. You can implement Binet’s formula using only arbitrarily large integer arithmetic — you do not need to compute any square roots of 5, just need to keep track of "where the square roots of five are" because they are going to cancel out in the end. You calculate in terms of a binomial form like (a+b√5)/c but because of the weird algebraic properties of ϕ all of the irrationality and all of the non-integer math cancels out by magic. You do not need to actually calculate any √5's while finding ϕ^n. If you use "exponentiation by squaring" this will lead to an O(log n) implementation -- O(log n) arithmetic operations anyway; the time complexity of the whole thing would depend on the time complexity of the arbitrary large arithmetic library you are using.
这篇关于关于Binet公式的秘诀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
