Programming Challenge no. 2: Fibonacci Sequence (Understanding Pseudocodes)

We are finally solving another programming challenge from Project Euler (after a long, long, long time).

 Our challenge for today:

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.

Before we open our compilers to start programming, we need to understand what the problem requires and the conditions we need to consider.

For this challenge, we'll use Java. (Actually, as long as you understand how the code works, you can use any language you feel comfortable to use.)

Analyzing the Problem

What we need to get: 
sum of the even-valued terms in the Fibonacci sequence.

Conditions:
1.) The numbers we need to add are in Fibonacci sequence.
2.) The numbers we need are less than four million (That's a big number!)
3.) The numbers we need are even.

Now that we have established our objective and requirements, let's create a pseudocode for this challenge.

Creating the Pseudocode

A psuedo-wha?

I've mentioned the meaning of this word in the previous puzzle but let me explain it better here. Let's break down the word. When you Google the word "pseudo", the results will tell you that it means "fake" or "mock". So when you say someone is a pseudoscientist, that person is a "fake scientist".

So we're making a "fake code"?

Err.. Well, to be precise, we are writing a code that resembles a programming language. It is not a real code since if you run it in a compiler, it would create errors. This makes sense because pseudocodes are written not for computers but for humans. With pseudocodes, you need not worry about programming language syntax.

Below is an example of pseudocode:

Declare fibonacciFormer, fibonacciLatter, currentFibonacci, limit and sumOfEvenFibonacci to Long
Initialize limit to 4000000
Initialize sumOfEvenFibonacci to 0
Initialize fibonacciFormer to 1
Initialize fibonacciLatter to 1
Initalize currentFibonacci to fibonacciFormer + fibonacciLatter 

While currentFibonacci is lesser than limit
     Check if currentFibonacci is even
         if True
             sumOfEvenFibonacci = sumOfEvenFibonacci + currentFibonacci
      fibonacciFormer = fibonacciLatter
      fibonacciLatter = currentFibonacci
      currentFibonacci = fibonacciFormer + fibonacciLatter

      return sumOfEvenFibonacci


Pause and try to understand what is happening. If your brain is refusing to process the "fake code" above, you'll have a hard time understanding the real one so let me enlighten you. However, if you figured out what the pseudo code does, you can move on to the coding section.

Let's start with what a Fibonacci sequence looks like. The figure below shows the Fibonacci sequence below 100.

So the next number is the number of the two preceding numbers in the sequence. Can you guess what's the next number after 89? Just add 55 and 89!

Now that we understand the Fibonacci sequence, let's go back to our pseudocode. You'll see that we have variables called fibonacciFormer and fibonacciLatter. These contain the preceding numbers while currentFibonacci is the sum of these numbers. Basically, currentFibonacci is the next number in the sequence. We initialized fibonacciFormer and fibonacciLatter to 1 because the Fibonacci sequence always starts with 1. We also initialized sumOfEvenFibonacci to zero.

Now the conditions! We are given the limitation of getting the numbers not greater than 4 million. We can hard code the condition to the number but it is wise to use a variable (in this case, our variable is called limit) so we can easily modify the code in the future when the requirements change.

1.) We will check if the currentFibonacci is lesser than our limit.
      If it is, then we will go inside the loop and arrive in our next condition.
2.) Since the problem set specifically wants even numbers, we need to check if the currentFibonacci is even.
3.) If it is, we add it to our current sumOfEvenFibonacci.
     If it is not, we skip it.
4.) We will then re-assign the values of our fibonacciFormer to get the value of fibonacciLatter.
5.) The variable fibonacciLatter gets the value of our currentFibonacci.
6.) Then we get the next number of our sequence by adding fibonacciFormer and fibonacciLatter and assign it to currentFibonacci.
7.) Then back we go to our loop until finally, we reach the limit.
8.) We exit the loop and we return the sumOfEvenFibonacci, which should contain the sum of our even fibonacci numbers.

And that's what our pseudocode is trying to do.

Coding

So here is our pseudocode written in Java:

public long getSumOfEvenFibonacci(long limit)
    {
      long fibonacciFormer, fibonacciLatter, currentFibonacci, sumOfEvenFibonacci;
      sumOfEvenFibonacci = 0;
      fibonacciFormer = 1;
      fibonacciLatter = 1;
      currentFibonacci = fibonacciFormer + fibonacciLatter;
   
      while(currentFibonacci < limit)
      {
        if(currentFibonacci % 2 == 0)
          sumOfEvenFibonacci = sumOfEvenFibonacci + currentFibonacci;
     
        fibonacciFormer = fibonacciLatter;
        fibonacciLatter = currentFibonacci;
        currentFibonacci = fibonacciFormer + fibonacciLatter;
      }
   
      return sumOfEvenFibonacci;
    }

It looks like our pseudocode, right? Except this one has brackets and semi-colons. Also, notice that to check if the number is even, we used the expression currentFibonacci % 2 == 0. The percentage symbol represents the modulo operation. We'll get to that in another post sometime.

Recommendation

If you run this Java code, it will give you the answer to the second puzzle in Project Euler. But this is not an efficient algorithm.

Algo-what now? Rhythm? We talking about music now?

Let's deal with algorithms in the next puzzle, aight? For now, give yourself a pat for taking the time to understand the Fibonacci sequence and how to get the sum of its even numbers.