Algorithms – How to Develop Effective Algorithms

algorithmsproject

I picked up some Project Euler questions today and decided to find more effective ways to Answer the questions l had already answered.

So on the question about finding the sum of the even Fibonacci terms up to 4 million; I noticed that if we had a separate sequence for the even Fibonacci terms (starting with 0 & 2 as the first & second terms respectively), the progression would be [0,2,8,34,144,610,...]
If two values from two successive terms are known, then the next term could be gotten with this expression:

[ T(n) = (4 * T(n-1)) + T(n-2) ]
...
Where;
T(n) : is the nth term,
T(n-1) : is the (n-1)th term,
T(n-2) : is the (n-2)th term,
and '4' is a constant.

However, so far I've been unable to derive an adequate expression to find the value in an arbitrary position without knowing the values of the two preceding terms.

My question:

  1. Is this how equations (/algorithms) are derived?

  2. Is this an efficient algorithm?

Footnote:
The other less efficient method (in my opinion), is to:

  1. Create a function to generate all the numbers in the Fibonacci sequence under 4 million,

  2. Get the even numbers among them,

  3. Find their sum.

Best Answer

A closed-form expression (called Binet's formula) for terms of the Fibonacci sequence is well-known: Fₙ = (φⁿ-ψⁿ)/√5, where φ=(1+√5)/2 and ψ=(1-√5)/2. You might be able to prove that formula via the Master theorem for recurrences. In any case, either by inspecting Binet's formula or by numerically calculating ratios of consecutive terms of the Fibonacci sequence, you should quickly observe that Fₙ is on the order of φ times larger than Fₙ₋₁. Since φ is about 1.618, this implies that Fₙ grows rapidly enough with n that it soon exceeds 4 million.

Here is an example of some python code that computes Fibonacci values less than a limit.

def smallFib(fmax):
    a, b = 0, 1
    while b<fmax:
        print b
        a, b = b, a+b

Run the code (that is, enter the code into a python interpreter, and then say smallFib(4000000)) and you will see that in fact only about 33 terms of the Fibonacci sequence are less than 4 million. Thus, it makes sense to just do the simple thing, and add up the 11 of those terms that are even. (To test if a number is even and add it to a sum if so, you can say if not b&1: sum += b.)

Note that Binet's formula does not give any apriori information about whether a term will be even or odd. As it happens, every third Fₙ is even, so you could just compute F₃, F₆, F₉..., but to know that every third Fₙ is even you need to either inspect the numbers or prove something about Fibonacci numbers. In many cases, using a slightly-complicated closed formula is not likely to save time compared to computing values via an extremely simple recurrence.

Summary: Don't use a complicated approach when a simple approach will do. Learn an interpreted language like python so that you can run simple tests to find out if a simple approach is good enough.

Related Topic