Thursday, May 12, 2011

02 Kata [reason] - sum of even fibonacci numbers

In this second kata, we are going to explore another problem from Project Euler.

Let's check it out:
"By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms"

I have been working on two possible solutions. In the first solution, I use a little bit of brute force, meaning that, I have to calculate every fibonacci number until tje result exceeds four million. For every generetade fibonacci number, I will test whether it's even or not and then, if it's even I sum it up. And, then, after all that, I will return the sum.

This first solution is the easiest way to solve the problem, meaning that we don't have to think hard to come up with it. And I see two positive outcomes when using this solution. We can use it to learn a language that we don't master yet and we can also use it as a start point to think about more fancy solutions.

In the second solution, I made use of a little math to optimize the algorithm.

We first find the index of the last fibonacci number that we need to compute in order to get the correct solution.
To find the index we use the following formula:

  • round ((log limit * (sqrt 5)) * 2) + 1.618)

1.618 is the golden ratio.

So, no we have the fib(n) that will generate a fibonnaci number that is less than the limit.

But we can use a little more math to make things a little bit faster.

Since every third fibonacci number is even, we don't need to compute the fibonacci number for all indexes in the sequence.
We can use de following formula and calculate only the ones that we know are even.

(4 * fib(i - 3)) + fib(i - 6)

In this version, we don't compute the fib(3), so we have to add 2 to the final result in order to get the correct answer.

So, let's take a look at the solutions

No comments:

Post a Comment