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.

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.


Here is my skeletal structure:

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 =; and then call #sum on a; or chain: print 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.



web developer making apps for people with appetite

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store