Problem 2 - Every other fib()

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.

Calculating the nth term of the Fibonacci sequence is a classic means of exploring recursion as a tool in function design, and can be applied here. We can also store Fibonacci results in a list and then use them after generation. We can also use a generator to calculate the nth term. To start, however, I'll present my original, and cringe-worthy implementation of the solution.

last1 = 1
last2 = 1
current = 0
runsum = 0
for x in xrange(1,200):
    if current > 4000000:
        break
    current = last1 + last2
    if current % 2 == 0:
        runsum += current
    last2 = last1
    last1 = current
print runsum

Here, the code loops until the arbitrary limit of 200 (non-inclusive) Fibonacci numbers, generating the next number on each iteration. Every time, it checks to see if the current iteration number is even, if so, it adds the new number to a running total.
Another approach is to use recursion, possibly the least effective method of solving the problem when it comes to scalability, in which a new Fibonacci term is generated with a recursive call, necessitating a new recursion path for each term.

def recur_fib(x):
    if x == 0 or x == 1:
        return 1
    return recur_fib(x - 1) + recur_fib(x - 2)

This method will return the nth Fibonacci number, however, the larger the target term, the longer it will take. One way we can improve on this is to store all of the terms that we generate. We can write the results to a file, or just keep them in a list encapsulated in a class.

class fib_list:
    terms = [1,2]
    def __getitem__(self, n):
        if len(self.terms) < n:
            return self.terms[n]
        while len(self.terms) < n:
            self.add_one_term()
        return self.terms[-1]
    def add_one_term(self):
        self.terms.append(self.terms[-2] + self.terms[-1])
    def add_until_target(self, target):
        while self[-1] < target:
            self.add_one_term()
        self.terms = self.terms[:-1]
temp = fib_list
temp.add_until_target(4000000) 
total = sum([x for x in temp.terms if x % 2 == 0]) # Answer generation

With this class, we can save the Fibonacci numbers in a list and get our answer with a single line of code that executes in trivial time. Generating the Fibonacci sequence remains the most intensive part of the problem. Is there a way to generate only the numbers we need without having to follow the sequence to its target, generating twice as many numbers as necessary?

Thankfully, there is a closed-form solution for generating the nth Fibonacci term known as Binet's formula. With this, we can generate an individual Fibonacci term, and by extension only the ones we need in the sequence (Thanks to Zeychin on StackOverflow for the Python Binet's).

def fib_at_n(n):
    return 0.4472135954999579392818347337462552470881236719223051448541 * (pow(1.6180339887498948482045868343656381177203091798057628621354,n) - pow(-0.618033988749894848204586834365638117720309179805762862135,n))
templist = []
for x in range(0,32,2):
    templist.append(fib_at_n(x))

With this method, our execution time is comparable to the time used in constructing the full Fibonacci sequence above using the list encapsulated in a class. However, this last method is by far the best scaling method. If the target term were much farther along in the sequence, this method would remain the fastest. For demonstration purposes, I'll pit each of these methods against one another in generating the 1000th Fibonacci term.

0.000510931015015 # Original Implementation
0.000808000564575 # List construction
1.90734863281e-06 # Stored list recall
4.05311584473e-06 # Binet's

As you can see, the execution time for the closed solution executes within the same time magnitude as recalling the list from a saved record, making this the best method for generating individual Fibonacci terms, but not the best for generating the whole sequence.