# Sum of Fibonacci numbers — speed contest

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.

-
Define "trivially calculated". Are you saying that we can apply mathematical identities to optimise it up to some cutoff point? If so, what precisely is the cutoff point? – Peter Taylor Apr 14 '11 at 18:44
@ralu Instead of giving a PC specification, you can also say print the maximum sum of fibonacci numbers before it times out on ideone.com . That way everyone will have a common ground. The time limit there is 5 secs. – fR0DDY Apr 15 '11 at 3:23
did not knew. That looks fair – ralu Apr 15 '11 at 7:27
What kind of input values are you talking about? – user unknown Apr 16 '11 at 1:40
The question is still unclear to me. For arbitrary input, each machine will reach a limit in 10s, so does 'as many as possible' mean, that the program shall interrupt, and print the sum so far? If you have a timelimit, the program could be interrupted from outside, and show, what it reached. – user unknown Apr 18 '11 at 12:09
show 5 more comments

## 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.

-
A very nice illustration of the point behind my question about what "trivially calculated" means. You could, of course, extend it to take any i and calculate the sum. – Peter Taylor Apr 14 '11 at 22:11
Indeed, the sum of the first i is the same as the sum of the first i % 1.5e9. – Keith Randall Apr 14 '11 at 22:24
Your program has to work whit different input values – ralu Apr 15 '11 at 0:08
I didn't get any of it. Care to explain to those without a degree in CS as of now? – the_drow Apr 15 '11 at 12:00
– Peter Taylor Apr 15 '11 at 21:46
show 6 more comments

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

-

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

-
I know that the question says just "print a sum of as many Fibonacci numbers as possible" without saying anything about them being unique, consecutive, or starting at 1, but I think it's implicit that it should be a sum of consecutive Fibonacci numbers starting 1, 1, 2. If you put an alert inside your loop you'll see that the values you output start 2, 5, 12, 29, 70. They should be 2, 4, 7, 12, 20. – Peter Taylor Apr 16 '11 at 7:16
@Peter Taylor That can be easily fixed just by changing the initial value of fib2 to 0. – Peter Olson Apr 16 '11 at 16:36
That gives 1, 2, 5, 12, 29, 70. Still broken. – Peter Taylor Apr 16 '11 at 18:28
+1 for the first code example - :) – Nate Koppenhaver Apr 26 '11 at 17:24
@Peter Taylor I fixed it, I think. I changed sum += fib1 + fib2 to sum = fib1 + fib2. – Peter Olson Apr 27 '11 at 20:12
show 1 more comment

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".

-