# Practice Problem 2

By: | Post date: December 29, 2008 | Comments: No Comments
Posted in categories: Cocoa, Erlang
Tags:

As mentioned in my previous post, I want to keep my skills fresh by working on simple, defined problems and solving them in both Objective-C and Erlang.

Here is the second problem.

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.

Sounds simple enough. I think I’ll need:

A function to solve for the next number in the Fibonacci series,
A method of iterating through the function until the next value is greater than four million,
A function to check if the number is even or odd, and
An accumulator to sum all even values.

## Erlang First

This time I’m going to start in Erlang and then solve in Objective-C.

Here is my code for generating the Fibonacci number of a given interval:

-module(problem2).
-export([fibo/1, fibo2/1]).
-import(lists, [sum/1]).

fibo(0) -> 0;
fibo(1) -> 1;
fibo(N) when N > 0 -> fibo(N-2) + fibo(N-1).

fibo2_tr( 0, Result, _Next) -> Result;
fibo2_tr( Iter, Result, Next) when Iter > 0 -> fibo2_tr(Iter-1, Next, Result+Next).

fibo2( N)-> fibo2_tr( N, 0, 1).

Notice that I’ve got two different methods (fibo() and fibo2()). The first is trivial, but slow at larger intervals, since it calculates every value in the series to get the n-th value. The second uses tail recursion and is significantly faster for larger values of N.

To generate the series of values as a list, I would use something like:

> L2 = [problem2:fibo2(X) || X <- lists:seq(1,40)].

I could further refine it to produce only even numbers below four million by doing:

> L3 = [A || A <- L2, (A rem 2 =:=0) and (A < 4000000)].

Which results in:

[2,8,34,144,610,2584,10946,46368,196418,832040,3524578]

As with my previous example, this list can be easily summed using:

> V = lists:sum(L3).

This produces the correct answer!

## Objective-C

Objective-C (or C in general) is still easier for me to get my head around. It took a fraction of the time to code this solution:

– (void)calcSumOfEvenFibo:(NSNumber*)upperLimit;
{
long i=0;
long j=1;
long next = 1;
long localSum = 0;

while(next < [upperLimit intValue]){
next = i+j;
i = j;
j = next;
if(next % 2 == 0){
localSum += next;
}
}

NSLog(@”localSum = %d”, localSum);
}

This method returns the same result as the Erlang solution.

## So what?

Obviously these are trivial examples of coding practices, but it is interesting thinking about how to solve these sorts of problems using a functional approach. I also think we’ll start to see some differences in the next problem.