Even Fibonacci numbers

July 16, 2015

Challenge 2. The Even Fibonacci numbers problem proposed by Project Euler.

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.

This challenge is again a fairly simple problem, the main challenges that I found was not making an infinite loop, I did this on my first running of the program, which I stupidly left long enough for it to crash my computer! Other than that making sure you sum the evens and get the fibonacci sequence correct are the only challenges. I decided to make the problem a little object orientated as it's something I'm really trying to get to grips with.

Lets take a look at my code.

Ruby

class Fibonacci
    
     def initialize(upTo)
        @upTo = upTo
     end

    def getFibonacci
        

        fibonacciNums = [1,2]
        index = 0
        iterations = fibonacciNums.length-1
        sumOfTwoNums = 0

        while sumOfTwoNums < @upTo
            iterations.times do 
                    sumOfTwoNums = fibonacciNums[index] + fibonacciNums[index+1]
                    

                    if sumOfTwoNums <= @upTo
                        fibonacciNums.push(sumOfTwoNums)
                    end
                index += 1
            end
        end
        getEvens(fibonacciNums)
    end

    private

    def getEvens(fibonacciNums)
        evens = []
        fibonacciNums.each do |i|
            if i.even?
                evens << i
            end
        end
    sumOfEvens(evens)
    end


    def sumOfEvens(evens)
        puts    evens.inject{|sum,x| sum + x }
    end
end

answer = Fibonacci.new(4000000)
answer.getFibonacci()
# => 4613732

As you can see I start off defining the Fibonacci class, notice the uppercase F(you define classes with uppercase letter first). This contains all the methods that solve the problem, it's overkill I'm sure but it's a learning process. The initialize method is called on every new instance of that class. So in this case my initialize method takes the argument 'upTo', this allows the user to specify the maximum value which you want to work out the sum of all the even numbers in the fibonacci sequence. For the problem the upTo value is 4,000,000 but you could work out the sum for any number.

I then set the upTo argument to the instance variable @upTo, this allows me to use the variable in other methods within the Fibonacci class. The getFibonacci method is the next method to be defined. Within this method I define the variables that I'm going to need, the fibonacciNums array has the first two numbers of the sequence in. The index will be used in order to add the two numbers in the fibonacciNums array. Iterations is the number of times the loop has to run in order to get up to the upTo variable, in this case 4,000,000. sumOfTwoNums is sum of the two number is the array, so the first sumOfTwoNums will be 3.

It obvious that to work out the solution you have to doing something until you reach 4,000,000, I found the easiest way for me was to use a simple while loop to check that the sumOfTwoNums is less than 4,000,000. I then add the two numbers in the sequence together so for the array [1,2], fibonacciNums[index] = 1 and fibonacciNums[index+1] = 2. Array indexes start at 0 so for the first iteration its fibonacciNums[0] and fibonacciNums[1]. I then need to check that sumOfTwoNums does not exceed 4,000,000 otherwise I will have one number over 4,000,000 because the while loop only stops when sumOfTwoNums is greater than 4,000,000. I could have removed the if statement and done 'while sumOfTwoNums < @upTo+1', but this only works when you know that a number in the sequence will appear. If I wanted use 4,000,001 as my upTo argument, this method wouldn't work. So if the number is below or equal to 4,000,000 I add it to the fibonacciNums array, so that on the next iteration we have [1,2,3] and so on. The index is then incremented by one, this allows the new number to be added to the previous one.

I then call the getEvens method, which unsurprisingly gets the even numbers from the fibonacciNums array. The method is simple enough, it takes an argument of the fibonacciNums array. I then define the evens array, which will contain... you guessed it, all the even numbers from fibonacciNums array. Once entire fibonacciNums array has been looped through I call the sumOfEvens method, passing in the evens array. Naming methods, classes, id's is far harder than it sounds, I often give methods terrible names, I've seen methods called 'reallyStupidMethod' at work which although funny when you come across it, doesn't help explain what it does. Generally I try to name my methods by what they do, mainly because I forget.

The sumOfEvens method just add all the numbers together, if you've never seen the syntax I've used, its the same as using 'do' & 'end' check out this stackoverflow question for more information.

For those of you who are unfamiliar, or new to Object Orientated Programming might be unfamiliar with the last couple of lines. 'answer = Fibonacci.new(4000000)' instantiates a new instance of the Fibonacci class, you can see this by doing 'puts answer.class'. I then call the class method .getFibonacci on the answer object. This allows me to do a few things, for example I could make a new object answer2 by calling answer2 = Fibonacci.new(50), then answer2.getFibonacci(). You could set these to variables eg num1 = answer.getFibonacci(), num2 = answer2.getFibonacci() and add them together. Again this is overkill but it helped me get a better understanding of OOP.

You might be wonder what the 'Private' word is all about. Well the 'Private' means that any method after it's declaration cannot be called outside of the class itself. So you can't call answer.sumOfEvens(array), go ahead and try you will see that you can't do it. For this example it's not needed, but you might need it for methods that use confidential information within the class.

If you've solved the problem in a different way I'd love to see it so feel free to leave a comment.

Subscribe for updates