Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com Jul 12 '13 at 21:31

This question came from our site for professional and enthusiast programmers.

    
Yes, it's a start. But deriving a formula for the n-th term of a recursive expression isn't generally easy. Here's a site with the formula for the n-th Fibonacci value: physicsforums.com/showthread.php?t=252915 –  mbratch Jul 12 '13 at 21:03
    
Specifically with the Project Euler questions, they often have a pdf that is visible (once registered and solved - it is to the right hand side of the problem list) that goes through the derivation of the optimal algorithm. –  MichaelT Jul 12 '13 at 21:35
    
Sometimes, you memorize algorithms. You see them applied somewhere, and the next time you face a similar problem, you use a variation of the algorithm you memorized. That's part of what experience brings as a developer. –  Gilbert Le Blanc Jul 15 '13 at 13:25
    
@Gilbert, thanks. Do developers need extensive math skills (other than just above average) to be able to cope well in their Software Development career? I will be starting Software Engineering/Computer Science soon in college, what's your advice as a programmer? –  Ace Takwas Jul 16 '13 at 22:49
    
@Ace Takwas: If you're going to do scientific programming, then yes, a good math background is essential. If you're going to do commercial programming, then probably not. You do need to know that floating point number math produces rounding errors. Ok for scientific calculations, not ok for currency calculations. –  Gilbert Le Blanc Jul 16 '13 at 23:13

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
1  
+1 for "it makes sense to just do the simple thing" :) This project euler question has always surprised me, given the limited depth of the recursive calls, there is little practical gain in taking the time deriving the expression F(n) = 4*F(n-1) + F(n-2). Don't get me wrong, I am all for finding a "better than obvious" solution, but this question in particular doesn't warrant it –  Nick Burns Jul 13 '13 at 4:17
    
Closed form is not great to program in since it uses floating point math, unless you happen to be using some sort of number theory library that treats square roots as integer roots instead of decimals. But then you have to think of the complexity of those operations, which are probably worse than a correctly memoized Fibonacci implementation. –  AAA Jul 13 '13 at 16:29

This should probably be closed as too broad. I mean, I'll refer to you to Polya's How To Solve It, which is something of a classic, but this list could go on too indefinitely.

A little more specifically -

  1. Sort of. Yes, by a lot of thinking and reworking, but I do happen to know the closed form for Fibonacci off the topic of my head, since I majored in math and worked on problem sets that led me in this direction enough for me to figure out big parts of it on my own - "guided self discovery," if you will. But, as a professional programmer, you spend your time not so much on this type of thinking and problem solving as you do researching, googling, and asking around until you find something.

  2. There are certainly more efficient ways to do this. It's a personal decision on your part whether you want to figure out as much as you can on your own, or look up other ways. My recommendation? First one, then the other.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.