Better way of calculating Project Euler #2 (Fibonacci sequence)

Question

Even Fibonacci numbers

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

object Problem_2 extends App {
 def fibLoop():Long =
 {
 var x = 1L
 var y = 2L
 var sum = 0L
 var swap = 0L
 while (x < 4000000)
 {
 if (x % 2 ==0) sum += x
 swap = x
 x = y
 y = swap + x
 }
 sum
 }
 def fib:Int = {
 lazy val fs: Stream[Int] = 0 #:: 1 #:: fs.zip(fs.tail).map(p => p._1 + p._2)
 fs.view.takeWhile(_ <= 4000000).filter(_ % 2 == 0).sum
 }
 val t1 = System.nanoTime()
 val res = fibLoop
 val t2 = (System.nanoTime() - t1 )/1000 
 println(s"The result is: $res time taken $t2 ms ")
}

Is there a more functional way of calculating the Fibonacci sequence and taking the sum of the even values below 4 million?

Is the imperative method 1000x faster?

• user22048: Have you solved the problem on PE? Have you looked at the attached pdf (see i.sstatic.net/WLwim.png ) that goes into the math for a better implementation?
• DXM: Project Euler has its own forum. Once you solve the problem using ANY way that gives you a solution, you get access to the forum for that problem where plenty of other people post their solutions.
• firephil: @ MichaelT the fibLoop function implements the algorithm that is recommended by the site, i was looking for a functional solution which would be as fast as the imperative method, maybe a tail recursive solution
• user22048: @firephil there's a rather elegant solution on page 5 of the PE question #2 forum. Don't know how fast they compare though.
• Sean McSomething: From a programming point of view, the loops is the best you can do. Any better solutions rely on mathematical principles, not programming efficiency. If you're learning to program (or learning a new language), PE is a poor tool, since many of the problems come down to having mathematical knowledge or already knowing a particular algorithm for a solution.

Answer 1

No iteration is required to calculate this result.

Every third Fibonacci number is even. The Fibonacci numbers can be expressed in closed form as:

Fib(n) = 1/sqrt(5) * (phi^n - psi'^n)

where

phi = (1 + sqrt(5) / 2)

and

psi = (1 - sqrt(5) / 2)

F(n) is even when n is a multiple of 3.

Therefore the sum of even fibonacci numbers is equal to the sum of two geometric series, and can be calculated directly and exactly.

P.S. A little experimentation shows that

sum(i=0..n) Fib(3*i) = (Fib(3*n + 2) - 1) / 2

e.g.

2 + 8 + 34 = 44 = (89 - 1) / 2

• firephil: still you have to iterate on the collected values and add them though.And i think adding is more efficient than calculating the values directly if you had started for an initial value say fib(5000) would have more efficient to jump there but with this given problem you have to start from 1 so its faster to start calculating from fib(1)
• kevin cline: @firephil: no, you don't have to iterate. The sum of even fibonacci numbers is equal to the sum of two geometric series. There is a closed form expression for the sum of a geometric series: sum(0..n) x^n = (x^(n+1)-1)/(x-1).
• firephil: thnx i see what you mean now
• firephil: @kevin cline it is more expensive to compute the closed form than a simple iteration or tail recursive algorithm. It may seem the closed form is faster but its not. I have performed measurements. Also you run into accuracy problems because you need to calculate the sqrt(5) which in most languages it is calculated with "double" precision