2
\$\begingroup\$

Given:

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.

MAX_LIMIT = 4000000 # Four million inclusive
FIB_CACHE = {}

def fib(n):
    """ Calculates nth fibonacci term.
    Args:
        n: The nth term.
    Returns:
        The nth fibonacci term of the series.
    """
    if (2 >= n):
        return n
    if (n not in FIB_CACHE):
        FIB_CACHE[n] = fib(n-1) + fib(n-2) # linear recurrence
    return FIB_CACHE[n]
    
def sum_fib():
    sum = 0
    i = 1
    ith_fib = 0
    while (1):
        ith_fib = fib(i)
        if (ith_fib > MAX_LIMIT):
            return sum
        if (ith_fib % 2 == 0):
            sum += ith_fib
        i += 1
    return sum
    
print fib(1)
print fib(2)
print fib(10)
print sum_fib()

Note: Without caching, it was taking too long to complete since it's an exponential algorithm.

Few important points:

  • I read somewhere about putting fewer changing values on the left. Is this true?
  • I am always confused about when to use an if-if branch and anif-else branch. Is there any heuristic? For example, could I write cache-checking code in the else branch too?
\$\endgroup\$
3
  • \$\begingroup\$ Could you clarify what you mean by "fewer changing values on the left"? \$\endgroup\$ Sep 16, 2015 at 8:49
  • \$\begingroup\$ @JanneKarila, yes! I mean if (1 <= n), here 1 is on left side. \$\endgroup\$
    – CodeYogi
    Sep 16, 2015 at 13:50
  • \$\begingroup\$ I tackled this a long time ago using the Golden Ratio - here's a link to the blog post which details the solution. The basic principle is that the nth Fibonacci number is the closest integer to (1/Sqrt(5))*(Golden_Ratio^n); generating even a long list of Fibs from that is very fast and consequently fast to sum the even fibs directly - no caching. It's in F# but easily adaptable to Python. \$\endgroup\$ Sep 16, 2015 at 14:14

4 Answers 4

7
\$\begingroup\$

Going from top to bottom:

MAX_LIMIT = 4000000 # Four million inclusive

That sounds like a function parameter, not a global constant:

def sum_fib(max_limit=4000000):
    ...

Now, you have this function:

def fib(n):
    ...

But you don't really need it. You never need the nth Fibonacci number here, out of the blue. You're always going in order. If you're going in order, you can just keep them as local variables and update both:

cur, prev = cur+prev, cur

And then:

while (1):

Typically we'd say while True:, but in this case, we have a clearly established termination condition: our max limit. So let's use it:

def sum_fib(max_limit=4000000):
    cur, prev = 1, 0
    total = 0 
    while cur < max_limit:
        if cur % 2 == 0:
            total += cur 
        cur, prev = cur+prev, cur 

    return total

We could even generalize this more by providing a predicate:

def sum_fib(max_limit=4000000, pred = lambda x: x%2 == 0): 
    cur, prev = 1, 0
    total = 0 
    while cur < max_limit:
        if pred(cur):
            total += cur 
        cur, prev = cur+prev, cur 

    return total

Now back to optimizations. What are the Fibonacci numbers? They are:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

What are the even Fibonacci numbers? They are:

2, 8, 34, 144, 610

Notice that it's every 3rd Fibonacci number. What can we do with that? That's still a Fibonacci-like sequence. Except instead of an = an-1 + an-2, we have an = 4an-1 + an-2:

def sum_fib(max_limit=4000000):
    cur, prev = 2, 0
    total = 0 
    while cur < max_limit:
        total += cur 
        cur, prev = 4*cur+prev, cur 

    return total
\$\endgroup\$
5
  • \$\begingroup\$ Just one thing, I don't why but if you see in the description above the sequence contains only single 1 in the start i.e. 1, 2, 3, 5.... This confused me a bit. \$\endgroup\$
    – CodeYogi
    Sep 16, 2015 at 13:49
  • \$\begingroup\$ Hmm, but that's confusing. Anyways I am really surprised about jumping into the very first solution, it will be good if I can analyze other solutions as well :( \$\endgroup\$
    – CodeYogi
    Sep 16, 2015 at 14:04
  • \$\begingroup\$ Np, I got it. I think the sequence must respect the finonacci rule, it doesn't matter the starting point. \$\endgroup\$
    – CodeYogi
    Sep 16, 2015 at 15:31
  • \$\begingroup\$ Hmm, now I have one problem. Why we are doing everything in just one function. We are supposed to divide responsibility right? \$\endgroup\$
    – CodeYogi
    Sep 17, 2015 at 4:17
  • \$\begingroup\$ Yes, you are right. But how would I know if I am over engineering. How do you know when to draw the line? because I find that thinking in terms of small function helps me a lot to solve some problem. \$\endgroup\$
    – CodeYogi
    Sep 17, 2015 at 17:19
2
\$\begingroup\$

I think your docstring for fib could be shortened to one line. You don't need to separate out Args and Returns as headings (unless this is to follow a specific parsing format)

""" Returns the nth fibonacci term."""

A few notes about your cache. It should just be a list, every nth number calculated will need all preceding numbers anyway, so a list fits this use perfectly. You might have wanted to avoid the fact that lists start indexing from 0, but you save space by sticking with a list and you can just pass n-1 when accessing the list. Also caps in the name suggest that it's a constant, but it's obviously not as it's a cache. If you wanted to signal that it shouldn't be used, add an underscore before it _fib_cache because that's the Python style to indicate it's a 'private' variable.

Also you could make the cache part of the function itself using a mutable default value. If you added cache=[] to your fib definition then you'll create an empty list when you create the function. This list will always be passed to the function as cache unless you manually override it by passing your own list value. This way you're not reliant on an external dictionary to store your values.

Even better though, start with cache=[1,2] since the brief said to begin with those values. Now you don't need to validate special values with 2 >= n. Though it could be good to ensure that a value less than 1 hasn't been passed.

Also, when using a list, instead of testing whether an index exists first, it's actually more Pythonic and faster to try access an index and then catch if that fails and calculate the previous fibonacci values. You can do this using try except IndexError.

def fib(n, cache=[1,2]):
    if (n < 1):
        raise ValueError("n must be greater than 1")
    try:
        return cache[n-1]
    except IndexError:
        cache.append(fib(n-2) + fib(n-1))
        return cache[-1]

Also using 2 <= n is a confusing order, generally variables are on the left and constants are on the right. Another convention is using while True instead of while (1), in addition those parentheses aren't needed.

ith_fib is a confusing name, I think it's meant to be ith like 4th, but that's not clear. Just use num or current_fib.

\$\endgroup\$
5
  • \$\begingroup\$ Just asking, why using dictionary is not preferred? is it the hashing time that matters? \$\endgroup\$
    – CodeYogi
    Sep 16, 2015 at 14:06
  • \$\begingroup\$ Also, ith_fib seems perfectly fine name. The first thing that comes to your mind is that its some ith term of the sequence which is good. \$\endgroup\$
    – CodeYogi
    Sep 16, 2015 at 14:07
  • \$\begingroup\$ Dictionaries are optimised for keywords, but lists are optimised for a sequence of integers. You have the latter so it makes sense to use the type optimised for it. ith confused me because I read it as a word rather than separating i and th. \$\endgroup\$ Sep 16, 2015 at 14:31
  • \$\begingroup\$ If one is using a list to store the Fibonacci numbers, it would be clearer to populate it from bottom up (with a loop instead of recursion). \$\endgroup\$ Sep 17, 2015 at 5:38
  • \$\begingroup\$ @JanneKarila That's definitely true, I actually got that feedback on something I posted, I was mostly just improving upon what the OP had. You're right that I should have noted the better approach though, I'll remember to do that in future even if I'm not going into detail on it. \$\endgroup\$ Sep 18, 2015 at 9:07
2
\$\begingroup\$

Question only requires finding the sum of all even fibonacci numbers not exceeding 4million.

Another way would be to not use a array to hold previous fib numbers at all.

Something like:

n, sum = 2, 0
previous, current = 1, 1
fib = 2
while fib < 4000000:
    fib = current + previous   #equivalent to n-1 + n-2

    #check for even fibs
    if fib%2 == 0:
        sum += fib

    previous = current      #n-2
    current = fib           #n-1
\$\endgroup\$
6
  • \$\begingroup\$ Basically you are saying to use an iterative solution. But I wanted to learn recursive algorithms :) \$\endgroup\$
    – CodeYogi
    Sep 16, 2015 at 14:08
  • 2
    \$\begingroup\$ @CodeYogi Fibonacci isn't really a good example to learn recursion. Dynamic programming for sure. \$\endgroup\$
    – sam
    Sep 16, 2015 at 14:28
  • \$\begingroup\$ @CodeYogi Tower of Hanoi for recursion \$\endgroup\$
    – Caridorc
    Sep 16, 2015 at 18:29
  • \$\begingroup\$ @Caridorc ya that's a well known example. But! what about thinking of our own, solving new problems? can just Tower of Hanoi enable us to solve any problem including recursion? I doubt. \$\endgroup\$
    – CodeYogi
    Sep 17, 2015 at 4:12
  • \$\begingroup\$ Also, if I see you are mixing concerns, ideally one function should calculate nth Fib term and second should sum the terms, \$\endgroup\$
    – CodeYogi
    Sep 17, 2015 at 4:16
1
\$\begingroup\$

Using a while loop with a counter is highly unidiomatic, you should use itertools.count for conciseness.

Some code, as my answer could be considered ambiguous:

def sum_fib():
    sum = 0
    for i in itertools.count():
        ith_fib = fib(i)
        if (ith_fib > MAX_LIMIT):
            return sum
        if (ith_fib % 2 == 0):
            sum += ith_fib
    return sum
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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