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.