Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question
    
Have you solved the problem on PE? Have you looked at the attached pdf (see i.stack.imgur.com/WLwim.png ) that goes into the math for a better implementation? –  MichaelT Oct 28 '13 at 19:46
3  
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. –  DXM Oct 28 '13 at 19:52
    
@ 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 –  firephil Oct 28 '13 at 19:56
    
@firephil there's a rather elegant solution on page 5 of the PE question #2 forum. Don't know how fast they compare though. –  MichaelT Oct 28 '13 at 19:59
1  
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. –  Sean McSomething Oct 28 '13 at 23:21
show 1 more comment

migrated from programmers.stackexchange.com Oct 30 '13 at 10:46

This question came from our site for professional programmers interested in conceptual questions about software development.

1 Answer

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
share|improve this answer
    
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) –  firephil Oct 28 '13 at 20:27
1  
@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). –  kevin cline Oct 28 '13 at 23:21
    
thnx i see what you mean now –  firephil Oct 29 '13 at 17:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.