1
\$\begingroup\$

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?

\$\endgroup\$

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

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • \$\begingroup\$ 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? \$\endgroup\$ – user22048 Oct 28 '13 at 19:46
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – DXM Oct 28 '13 at 19:52
  • \$\begingroup\$ @ 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 \$\endgroup\$ – firephil Oct 28 '13 at 19:56
  • \$\begingroup\$ @firephil there's a rather elegant solution on page 5 of the PE question #2 forum. Don't know how fast they compare though. \$\endgroup\$ – user22048 Oct 28 '13 at 19:59
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Sean McSomething Oct 28 '13 at 23:21
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – firephil Oct 28 '13 at 20:27
  • 1
    \$\begingroup\$ @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). \$\endgroup\$ – kevin cline Oct 28 '13 at 23:21
  • \$\begingroup\$ thnx i see what you mean now \$\endgroup\$ – firephil Oct 29 '13 at 17:58
  • \$\begingroup\$ @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 \$\endgroup\$ – firephil Aug 8 '14 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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