Algorithms in Ruby: Fibonacci sequence

If you’re coming from my last blog, you’ve probably picked up on the fact I started doing the classic Euler project. So here’s the next challenge…

## Problem: Even Fibonacci

- 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.

You can skip this next section if you are familiar with the Fibonacci sequence(referred to as fib_seq from here on out) pretty well. For me, I had to write it out in plain english.

Being a poor mathematician, spelling things out on the first few routines of the sequence may reveal the secrets.

What’s given: each new term is equal to the sum of the previous two terms.

new_term = term1 + term2

So at what real number does the fib_seq actually start at? If googled, that question has quite a few response and many of the same answer. Turns out that’s very important to consider. The problem statement is misleading, because how does the sequence initialize? In reality, people witness it initialized all around, like a seashell of some kind. Out of nothing, comes something, and from that something, many more.

If we say in our code “the fib_seq begins with one” we are making many parallel assumptions about the seq that can be modified, but at what cost? If we consider what the mathematicians say, the fib_seq starts 0,1,2,3,5,8,13, 21…I’m going to use this assumption for my working algorithm.

Thus, simply put, if we start at zero, our first number is zero, our second is then one. If we can loop over a routine of setting those italicized words, we could be capable of finding all the numbers in the fib_seq to our limit; or, ultimately, filtering out and giving back the the ones that do pass a condition. For this scenario, that condition being an even number within the fib_seq; it could easily be the odds; or create a function that will fire either. Let’s keep it simple:

Let’s say the limit is 21. So first time, start = 0, first = 0, second = 1. Enter the loop. First plus second is done; 1 + 0 . This is now assigned to the start variable. 1 is not even. First is set to second; first = 1. Second is assigned to the start; start = 1.

Run sequence again: start + first ; 1 + 1 = 2, thus 2 is the start, 1 is first. Interjection: the start is even! Again: start + first; 2+1 = 3, thus 3 is start. 3 + 2 = 5; now it goes 5 + 3 = 8(another even); 8+5=13; 13 + 8 = 21…all the way up to the limit. All the evens here are: 2 and 8; sum is 10. Interesting.

Now I write that idea as a psuedocode and in so doing, I will also be making sure to note when to evaluate which of those numbers in the sequence are even, and write code to store those numbers somewhere in order to be used at the end to do more math and return the ultimate sum of evens from the fib seq.

Psuedocode:

declare procedure to take in a limiting number and return the sum of all the even numbers in the fib sequence up to that limit
  starting from zero
  our first number is also zero
  our second number is one
  so long as the starting point is less than the limit, let's run some math and evaluate those returns against some conditions
  do math: first plus second, and assign this sum as the new starting point
  is this sum even? if so, let's store it somewhere, otherwise its not something we're going to be using (we could store it, but its useless)
  now let's make some reassignments for the next run of the sequence: our new_first is our former_second, and our starting point will be the sum we've already determined.
  keep running this until the sum of first and second are greater than limit, at which point break and do no go forwards into reassignment or (most importantly) storing evens.
lastly, take all those evens, add em up and return!
end
tests
10
20
100
1000

Here is my skeletal structure:

def even_fibonacci_sum(limit)
  # variable declarations
  array_of_evens = []
  i = 0
  first = 0
  second = 1
  # lets use a while loop
  while i < limit
   # add first and second, then assign it to i
    i = first + second
   # if this i is greater than our limit, break the loop
    break if i > limit
   # what to do now? evaluate if i is even, and store in array
    array_of_evens << i if i.even?
   # reassign our variables for the next loop
   # new first is former second
    first = second
  # new second is reassigned i
    second = i
  end 
# take the array and do the maths sum = | x, y, x | x + y + z to infinity and keep going potentially
  array_of_evens.reduce(:+)
end

If this style of reduce is foreign to you, look into this article here. Reduce is an essential ruby method, and it can be a little tricky to understand what it does and how it works. But once you get the hang of it, it will save you time in coding, and the time for your code to execute, too, potentially.

Here’s another gist of this in object oriented ruby:

There are many obvious ways to refractor this. First, there’s the glaring one that I’ve taken my beautiful singular procedural ruby method, and instead created two methods I can call on our instances. This is done for two reasons. I want to be able to, first, in my console create and save a new instance of the class to variable, ie: a = EvenFibonacci.new(100); and then call #sum on a; or chain: print EvenFibonacci.new(100).sum to get to the heart of the matter, and show it in my console. Second, is to call #find_evens. Why? Because what’s cool is that upon object initialization, #find_evens is called, and its return value is stored to an instance variable, which we can read by calling, for example, a.evens. Doing this will reveal a fun but important difference. Since #find_evens has been called and executed until the breaking point, it means also that our instance variables of first and second have been reassigned to the last loop on which it broke, ie when our x is greater than limit, thus the array returned is empty if we call it after it has already been initialized and created. Seeing that kind of call stack in action is integral to debugging. Also, having methods available to access instance variables allows me to see the results of the data attempting to be or having been transferred. Immediately invoked functions are cool.

Also, why inject? Because its fun to replace reduce with it because, I mean, inject just sounds cool; check out earlier articles, where I discuss this in details.

So lastly, here’s my slimmed down way of implementing this as fast as possible in (N) time; and please note for debugging I had the gem ‘pry’ added to a gemfile, and created a config folder with environment.rb to load in app-wide dependancies:

I hope reading along to this recap on how someone with little math skills can use programming to overcome math tricky equations gives you some idea of how to break down a problem yourself, and start solving things that are a grade more difficult than your capabilities each time.