Problem : Euler Task 2

Let's continue the effort of answering euler project challenge. Here, we answer the challenge no. 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, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

First, let's investigate the implementation of fibonacci. A simple recursive program is the following

1 def fib(x: Int) : Long = {
2    if (x >= 2) {
3       fib(x -1) + fib(x -2)
4    } else {
5       1
6    }
7 }

The problem with the code above is the performance. fib(45) in my computer took 77 s. Fortunately, Scala can optimise tail recursion and indeed fibonacci can be implemented using tail recursive algorithms. The implementation is shown in the following code:

1 def fibiter(index: Int) : Long = {
2  def fibiter(x: Long, acc: Long, count: Int) : Long = {
3      if (count == index) 
4          acc
5      else fibiter(x + acc,x, count + 1)
6   }
7   fibiter(1, 0, 0)
8 }

To implement the algorithms, we need to define an auxiliary method, fibiter/3 that receives the "next" fibonacci number, the "current" fibonacci number, and the index of the count that needed to be compared against the requested index.
Scala optimises the code above so that it is treated just like a loop instead of a recursive call. Executing fibiter(45) does not take even 1ms. 
Having defined fibiter method, we're now ready to attack the problem, that is to sum of all even-valued terms.

First, just sum everything, not necessarily the even ones. The code is implemented as follow:

 1 def fibSum(max: Long) : Long = {
 2   def fibSum(x: Long, acc: Long, sum: Long) : Long = {
 3      if (x > max) {
 4          sum
 5      }
 6      else { 
 7        fibSum(x + acc, x, sum + x) 
 8      }
 9  }
10   fibSum(1, 0, 0)
11 }
12 
Like fibiter, we use here an auxilary method, fibSum with 3 parameters. acc is used as the accumulator of fibonacci number, just like in fibiter. In addition, sum is used as the accumulator of the sum of fibonacci number computed so far. The condition at line 3-5 is used to see if the next fibonacci number exceeds the max. If it is the case, the sum so far is returned, otherwise it recursively computes the next fibonacci number.
With the above algorithms in hand, we're now ready to attack the problem, that is, to sum only even fibonacci number:


 1 def fibSum(max: Long) : Long = {
 2   def fibSum(x: Long, acc: Long, sum: Long) : Long = {
 3     if (x > max) {
 4          sum
 5      }
 6      else if (x % 2 == 0) {
 7          fibSum(x + acc, x, sum + x) 
 8      } else {
 9          fibSum(x + acc, x, sum) 
10      }
11   }
12   fibSum(1, 0, 0)
13 }

The lines 6-10 are the key of the solution. The sum is updated only when the current fibonacci number is even. 


Finally, to further generalise the method, the fibSum is modified to accept a function Long => Boolean as follow:
 1 def fibSum(max: Long, filter: Long => Boolean) : Long = {
 2   def fibSum(x: Long, acc: Long, sum: Long) : Long = {
 3     if (x > max) {
 4          sum
 5      }
 6      else if (filter(x)) {
 7          fibSum(x + acc, x, sum + x) 
 8      } else {
 9          fibSum(x + acc, x, sum) 
10      }
11   }
12   fibSum(1, 0, 0)
13 }
To sum all even fibonacci numbers under 4000000, fibSum is called as follow: fibSum(4000000, x => x % 2 ==0).