Sum of Fibonacci numbers -- speed contest

Question

Write a program that print sum of as many Fibonacci numbers as possible. There is a limit in that your program should not run more than 10s on 2GHz single core PC. (equivalents are acceptable, for instance you have twice as many time on 1GHz PC). Memory consumption is not limited, but provide details, if you exceed normal values.

Your program has to work with different input values. Output can be calculated modulo 10^i, but i has to be at least 9 digits. Other types of results are also welcome as long as they are presented with 9 digits and are not trivially calculated.

Post source, language input value and result.

Answer 1

Python, 7 chars

It turns out that the period of G(i)=F(i) mod 10^9 is 1.5e9 exactly. So when adding them up, we can group them into groups of size 1.5e9, each of which will have the same sum (mod 10^9). Turns out, that sum is 0. So if we take N to be any multiple of 1.5e9, the sum of the first N fibonacci numbers is 0. So:

print 0

will, given an argument i, print the sum of the first i * 1.5e9 Fibonacci numbers. Super fast and works for an arbitrarily large i.

Answer 2

Compensating for my cores being 2.5GHz by allowing just under 8 seconds,

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);
    }
}

Output:

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

And no sign of Binet's formula or any closed form evaluation of the sum, even though there is a trivial one.

---

As a closely related point of interest, note that we can use the identity F(m+n) = F(m+1) F(n) + F(m) F(n+1) - F(m) F(n) to compute the nth Fibonacci number in O(lg n) arithmetic operations. Replace int and long with a suitable BigInteger implementation to taste. I've made this tail-recursive.

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;
}

Or if SML is your cup of tea then

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;

Detailed reasoning at http://www.cheddarmonk.org/Fibonacci.html

Answer 3

Knowing that the sum of the fibbonacci series diverges, I can print the result rather trivially with 16 characters in Javascript.

alert(Infinity);

Ok, ok, enough glibness. This probably doesn't meet your criterion about trivial calculation. Here is my full version in 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);

What it alerts is unpredictable, it ranges from 1e+100 to Infinity for me.

And here it is golfed (91 chars):

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);

Answer 4

Okay. I took this question as find every fib from fib(0) to fib(n) and take the sum: what's the biggest n you can deal with in 8 sec?

#!/usr/bin/env clisp

(defun sum (list)
    (setf s 0)
    (loop for foo in list do
        (setf s (+ s foo))
    )
    s
)

(defun fib-list (n)
    (loop for x from 1 to n do
        (setf *fibs* (append *fibs* (list (sum (last *fibs* 2)))))
    )
)

(defun test ()
    (progn
            ;; variable initializations
        (setf n 12000)
        (setf ti (get-universal-time))
        (setf tf (get-universal-time))

        (loop while (<= (- tf ti) 8) do ; while the end time minus the start time
                                        ; is less than 8 sec...
            (progn
                (print n)
                (setf *fibs* '(1 1))
                (setf ti (get-universal-time))  ; record the start time

                (fib-list n)
                (print (sum *fibs*))

                (setf tf (get-universal-time))  ; record the end time
                (setf n (+ n 25))
            )
        )
        (print "MAXIMUM NUMBER......")
        (print n)
    )
)

(test)

Now. this only uses one optimization: my fib calculating method, which uses a list to minimize the repetition of calculations.

The test routine reports that this code can deal with an n of 13000 in 8 seconds under win7 on a 2.35Ghz chip. I discount my dual-cores because clisp is a single-threaded process which derives no benefit therefrom.

no fancy math here, just ANSI CLISP and brute force "trivial calculation".