Fibonacci数之和-速度竞赛

Question

编写一个程序，打印尽可能多的斐波纳契数字和。有一个限制，你的程序不应该在2 2GHz单核PC上运行超过10秒。(等价物是可以接受的，例如，在1 twice上的时间是原来的两倍)。内存消耗不受限制，但如果超出正常值，请提供详细信息。

您的程序必须使用不同的输入值。输出可以计算模10^i，但我必须至少是9位数。其他类型的结果也是受欢迎的，只要它们有9位数字，而不是琐碎的计算。

文章来源，语言输入值和结果。

Answer 1

Python，7个字符

结果表明，G(i)=F(i) mod 10^9的周期正好是1.5e9。因此，当将它们加起来时，我们可以将它们分组为大小为1.5e9的组，每个组都有相同的和(mod 10^9)。结果，这个总数是0。因此，如果我们取N为1.5e9的任何倍数，第一个N个斐波那契数之和为0。所以：

print 0

will，给定一个参数i，打印第一个i * 1.5e9 Fibonacci数的和。超级快，为任意大的i工作。

Answer 2

补偿我的核心是2.5GHz，允许不到8秒，

public class FiboSum
{
    public static void main(String[] args)
    {
        long now = System.currentTimeMillis();
        System.out.println("Taking F(1) = F(2) = 1, F(n) = F(n-1) + F(n-2):");
        long n = 0, x = 1, y = 1, N = 1000000000;
        // x = F_n, y = F_{n+1}
        while (System.currentTimeMillis() - now < 7800)
        {
            n++;
            long t = (x*x + y*y) % N;
            x = x * (2*y - x) % N;
            y = t;
        }
        System.out.println("\\sum_{r=1}^{2^"+n+"} F(r) = " + (N+x+y-1)%N + " mod " + N);
    }
}

输出：

Taking F(1) = F(2) = 1, F(n) = F(n-1) + F(n-2):
\sum_{r=1}^{2^94900480} F(r) = 755986263 mod 1000000000

即使有一个琐碎的公式，也没有关于比内公式的迹象，也没有任何关于和的封闭形式的计算。

作为一个密切相关的兴趣点，请注意，我们可以使用恒等式F(m+n) = F(m+1) F(n) + F(m) F(n+1) - F(m) F(n)计算O(lg n)算术运算中的nth Fibonacci数。将int和long替换为合适的BigInteger实现。我把这个尾部递归化了。

static long Fibo(int n)
{
    if (n > 92) throw new ArithmeticException("Overflow");

    long Fm = 1, Fmp = 1;
    long Fn = 0, Fnp = 1;

    while (n > 0)
    {
        if ((n & 1) == 1)
        {
            long t = Fmp * Fn + Fm * (Fnp - Fn);
            Fnp = Fmp * Fnp + Fm * Fn;
            Fn = t;
        }

        long t = Fm * (2*Fmp - Fm);
        Fmp = Fmp*Fmp + Fm*Fm;
        Fm = t;

        n >>= 1;
    }

    return Fn;
}

或者如果SML是你的一杯茶

fun fibo x =
    let fun f 0 _ _ Fn _ = Fn
          | f n Fm Fmp Fn Fnp =
            let val Fm2 = Fm * (2 * Fmp - Fm)
                val Fmp2 = Fmp * Fmp + Fm * Fm
            in if (n mod 2 = 0)
               then f (n div 2) Fm2 Fmp2 Fn Fnp
               else f (n div 2) Fm2 Fmp2 (Fmp * Fn + Fm * (Fnp - Fn)) (Fmp * Fnp + Fm * Fn)
            end
    in f x 1 1 0 1
    end;

在http://www.cheddarmonk.org/Fibonacci.html上的详细推理

Answer 3

知道了斐波纳契系列的和发散，我可以打印结果相当微不足道的16个字符在Javascript。

alert(Infinity);

好吧，好吧，够了。这可能不符合您关于琐碎计算的标准。以下是我在Javascript中的完整版本：

var old = new Date().getTime();
var fib1 = 1, fib2 = 1, sum = 0;
while(new Date().getTime() - old < 2){
    sum = fib1 + fib2;
    fib1 = fib2;
    fib2 = sum;
}
alert(sum);

它所提醒的是不可预测的，它的范围从1e+100到无穷无尽为我。

这里是金币(91千卡)：

o=new Date().getTime();f=1,g=1,s=0;while(new Date().getTime()-o< 2){s=f+g;f=g;g=s}alert(s);