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\$
  • \$\begingroup\$ Could you clarify what you mean by "fewer changing values on the left"? \$\endgroup\$ – Janne Karila Sep 16 '15 at 8:49
  • \$\begingroup\$ @JanneKarila, yes! I mean if (1 <= n), here 1 is on left side. \$\endgroup\$ – CodeYogi Sep 16 '15 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\$ – Kevin Roche Sep 16 '15 at 14:14
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\$
  • \$\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 '15 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 '15 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 '15 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 '15 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 '15 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\$
  • \$\begingroup\$ Just asking, why using dictionary is not preferred? is it the hashing time that matters? \$\endgroup\$ – CodeYogi Sep 16 '15 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 '15 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\$ – SuperBiasedMan Sep 16 '15 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\$ – Janne Karila Sep 17 '15 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\$ – SuperBiasedMan Sep 18 '15 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\$
  • \$\begingroup\$ Basically you are saying to use an iterative solution. But I wanted to learn recursive algorithms :) \$\endgroup\$ – CodeYogi Sep 16 '15 at 14:08
  • 2
    \$\begingroup\$ @CodeYogi Fibonacci isn't really a good example to learn recursion. Dynamic programming for sure. \$\endgroup\$ – sam Sep 16 '15 at 14:28
  • \$\begingroup\$ @CodeYogi Tower of Hanoi for recursion \$\endgroup\$ – Caridorc Sep 16 '15 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 '15 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 '15 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\$

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.