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.
Don’t get too lost in the Fib spiral! Thanks for the photo Wikicommons.
Analyze the Problem
This prompt opens with critical information. They tell us how to structure the Fibonacci algorithm. Any value in the Fibonacci series will be the sum of the two previous Fibonacci values. This can easily be represented with
f = (f-1) + (f-2). These ‘f’ variables refer not to the value, but the term in the Fibonacci series.
Next they give us an upper limit on values that we need to concern ourselves with (4,000,000). Finally, we are asked to find the sum of even-termed values.
At first reading I thought they were simply asking for all of the even values, but they try to abstract it a little further and asked for the sum of the even-valued terms.
Pseudocode the Problem
We need to…
- Calculate Fibonacci values
- Use only Fibonacci values less than or equal to 4,000,000
- Determine if the Fibonacci term for each value is even or odd
- Add up all the values that belong to even terms
total = 0 n = 1 def fibonacci(n) if n <= 2 return 1 else fibonacci(n-1) + fibonacci(n-2) end end while fibonacci(n) <= 4_000_000 if fibonacci(n) % 2 == 0 total += fibonacci(n) end n += 1 end p total #=> 4613732
Let’s look at this code in more detail. We have a method
fibonacci(n) that has a term-value parameter.
If you run
fibonacci(10), you get
#=>55 (this doesn’t line up with the series in the prompt because it assumes a 0-index start…the Euler solution is still correct).
We then have a
while loop that keeps our input values under or equal to 4,000,000. While this condition is true, we check if each value’s term has a remainder equal to 0 when it is divided by 2 (which would make it even). If it is even, it gets added to our variable
All said and done, the sum of the even-valued terms is
I don’t know if you noticed, but the algorithm above wasn’t very fast. In fact, I used the
Benchmark module and got the following times back:
2.420000 0.000000 2.420000 ( 2.430614)
This is really slow for a relatively simple calculation. Let’s make sure we understand why this algorithm performs so slowly.
Basically, we have a recursive method finding our Fibonacci values. This means every time
fibonacci(n) runs, every single value used in the calculation relies on
fibonacci(n-...). This creates exponential complexity in our algorithm, and leaves it with an unfavorable Big O of O(n^2), which let’s us describe it as 'running in n^2 time.’ You can see why they capped the values at 4,000,000! I bet with a little more head-knocking we can refactor our algorithm to linear complexity.
Let’s see if we can…
- Avoid calculating Fibonacci recursively
I think if we accomplish the above we can definitely speed up our algorithm! Try it yourself before looking at the refactored solution.
i = [1, 1] c = 0 sum = 0 while c <= 4_000_000 c = i + i i = i i = c if c % 2 == 0 sum += c end end p sum
To memoize, we needed to initialize an array that will store all of our computed Fibonacci values. We start it at [1,1] to line it up with the Fibonacci series presented in the problem.
while loop, we play around with
c, our current Fib value, and
i, our Fib value array. Though it looks wildly simpler (and different?) than the Fibonacci calculator in our just-works solution, that is exactly what the three lines between
if are doing.
If you plug in the first two values of our array
i, you will see that our first c-value is 2, and then the next two lines busy themselves with shifting the values around so that every time the loop starts over our code always refers to (c-1) and (c-2). We use the same conditional as in our just-works to evaluate evenness, and store the even values the same way as well.
Before we look at the Benchmark performance, what can we expect from the Big O notation? Well, we definitely got rid of recursion. Every time we calculate
c we do so with immediately retrievable values from our
So, we can say that our algorithm runs in N time ( “O(N)” ).
Benchmark gives us…
0.000000 0.000000 0.000000 ( 0.000058)