相关疑难解决方法(0)

所以,我们看到了很多斐波纳契问题.我个人非常讨厌他们.很多.不止一切.我认为如果我们可以让任何人都不可能再次将其用作面试问题,那就太好了.让我们看看有多接近O(1)我们可以得到斐波那契.

这是我的开始,几乎来自维基百科,当然还有足够的空间.重要的是,这个解决方案将引爆任何特别大的fib,它包含一个相对天真的power函数使用,如果你的库不好,它会把它放在最坏的O(log(n)).我怀疑我们可以摆脱电源功能,或至少专攻它.有人帮忙吗？除了使用查找表的有限*解决方案之外,是否存在真正的O(1)解决方案？

http://ideone.com/FDt3P

#include <iostream>
#include <math.h>
using namespace std; // would never normally do this.

int main()
{
int target = 10;
cin >> target;
// should be close enough for anything that won't make us explode anyway.
float mangle = 2.23607610; 

float manglemore = mangle;
++manglemore; manglemore = manglemore / 2;
manglemore = pow(manglemore, target);
manglemore = manglemore/mangle;
manglemore += .5;
cout << floor(manglemore);

}

*我知道,我知道,这足以满足斐波纳契的任何零实际用途.

背景:

我被"拖累"看到这个问题: 当作者最初用许多其他语言标记但后来专注于Haskell问题时,Fibonacci在Haskell中的Closed-form表达式
.不幸的是,我对Haskell没有任何经验,所以我无法真正参与这个问题.然而,其中一个答案引起了我的注意,应答者把它变成了纯整数学问题.这对我来说听起来很棒,所以我必须弄清楚它是如何工作的,并将其与递归的Fibonacci实现进行比较,以了解它的准确性.我有一种感觉,如果我只记得涉及非理性数字的相关数学,我可能能够自己解决所有问题(但我没有).因此,对我而言,第一步是将其移植到我熟悉的语言中.在这种情况下,我正在做C#.

幸运的是,我并没有完全处于黑暗中.我有很多其他功能语言(OCaml)的经验,所以我看起来有点熟悉.从转换开始,一切看起来都很简单,因为它基本上定义了一个新的数字类型来帮助计算.然而,我在翻译中遇到了几个障碍,但我在完成翻译时遇到了麻烦.我的结果完全错了.

分析:

这是我正在翻译的代码:

data Ext = Ext !Integer !Integer
    deriving (Eq, Show)

instance Num Ext where
    fromInteger a = Ext a 0
    negate (Ext a b) = Ext (-a) (-b)
    (Ext a b) + (Ext c d) = Ext (a+c) (b+d)
    (Ext a b) * (Ext c d) = Ext (a*c + 5*b*d) (a*d + b*c) -- easy to work out on paper
    -- remaining instance methods are not needed

fib …

我发送了这个非常好的非递归函数来计算斐波纳契数列.

所以我编写了一些c#并且能够验证所有高达1474的数字是否正确.

尝试计算1475及以上时会出现问题.我的c#数学技能不能达到找出不同方法的任务.那么,有人有更好的方法在c#中表达这个特定的数学函数吗？除了传统的递归函数方式？

顺便说一句,我开始使用BigInteger作为返回类型.但是当试图将(1 + Math.Sqrt(5)/ 2)提升到1475次幂时,问题确实存在.我只是没有看到我需要什么样的数据类型(也没有这个问题的机制)来让它回归到Infinity以外的东西.

这是一个起点.

private Double FibSequence(Int32 input) {
    Double part1 = (1 / Math.Sqrt(5));
    Double part2 = Math.Pow(((1 + Math.Sqrt(5)) / 2), input);
    Double part3 = Math.Pow(((1 - Math.Sqrt(5)) / 2), input);

    return (part1 * part2) - (part1 * part3);
}

而且,不,这不是功课.对于缓慢的一天来说只是一个"简单"的问题.

几周前我在Google+上看到了一条评论,其中有人展示了斐波那契数字的直接计算,这些数字并非基于递归而且没有使用记忆.他实际上只记得最后两个数字并不断添加它们.这是一个O(n)算法,但他非常干净地实现了它.所以我很快指出,更快的方法是利用它们可以被计算为[[0,1],[1,1]]矩阵的幂的事实,它只需要一个O(log(N))计算.

问题当然是,这远远超过某一点.只要数字不是太大就有效,但它们以N*log(phi)/ log(10)的速率增长,其中N是第N个斐波那契数,phi是黄金比((1) + sqrt(5))/ 2~1.6).事实证明,log(phi)/ log(10)非常接近1/5.因此,预计Nth Fibonacci数字大约为N/5位数.

当数字开始有数百万或数十亿的数字时,矩阵乘法,即使偶数乘法,也会非常慢.因此,F(100,000)计算大约0.03秒(在Python中),而F(1000,000)大约需要5秒钟.这几乎不是O(log(N))增长.我的估计是这种方法没有改进,只是将计算优化为O((log(N))^(2.5))左右.

以这个速率计算第十亿个Fibonacci数将会非常慢(即使它只有〜1,000,000,000/5位数,因此它很容易适合32位内存).

有谁知道一个允许更快计算的实现或算法？也许某些东西可以计算出万亿的斐波纳契数.

而且要清楚,我不是在寻找近似值.我正在寻找精确的计算(到最后一位数).

编辑1: 我正在添加Python代码以显示我认为的O((log N)^ 2.5))算法.

from operator import mul as mul
from time import clock

class TwoByTwoMatrix:
    __slots__ = "rows"

    def __init__(self, m):
        self.rows = m

    def __imul__(self, other):
        self.rows = [[sum(map(mul, my_row, oth_col)) for oth_col in zip(*other.rows)] for my_row in self.rows]
        return self

    def intpow(self, i):
        i = int(i)
        result = TwoByTwoMatrix([[long(1),long(0)],[long(0),long(1)]])
        if i <= 0:
            return result
        k = 0
        while i % 2 == …