Week 2

This week, we got many more entries, from our extended network of friends. This combined with some local school issues contributed to two week delay in our contest. We apologize for this delay, and hope to not repeat this delay in the future.

Going forward, instead of segregating student from mentor/adult submissions, we will explore them only separated by programming environment. The order shown below is LabVIEW followed by Python, then slowest execution to fastest. The problem is the same for all submissions, and the goal here is to focus on improving algorithm development skills. This week we had far more variation in algorithms, which is a good thing!
  
Problem:
Each new term in the Fibonacci Sequence is generated by adding the previous two terms. By starting with 1 and 2, the first ten terms would be:

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

By considering the terms in the Fibonacci sequence whoses values do not exceed four million, find the sum of the even-valued terms.
 

Solutions:

LabVIEW - Joe

Joe_2.vi

Joe_2.vi

Joe_2.vi

Joe_2.vi

First up, we have a LabVIEW submission by Joe. He used a novel way to count which members to include in the sum output with a binary NOT XOR. This code computes every member of the Fibonacci sequence, but only selects the even members based on the binary “counter”, rather than calculating if a term is even with modulo division. While this entry was tersely commented, it probably could have used a little more to explain what was going on with the logic bits. One other interesting thing to note is that Joe toggled the “STOP” condition to a “CONTINUE” condition for his while loop.

Joe’s code was 1.26 times slower than the fastest. Still pretty quick!

LabVIEW - Justin

Justin_2.vi

Justin_2.vi

Justin_2.vi

Justin_2.vi

Justin came in second in speed on LabVIEW with an entry that arrived at the correct answer, but did so without testing for the termination condition of having the sequence member being less than 4,000,000. It is apparent that Justin took to heart that one way to win is by having the fastest execution, and last week’s entries with FOR loops handily outperformed the WHILE loops. WHILE loops have to test for an end condition each time the loop is executed, while FOR loops do not. This is a cheat, as it relies on knowing how many iterations of the loop is necessary, in advance. How would this code work if the limit were placed at a term being less than 173,000,000?

Justin’s code was 1.09 times slower than the fastest.  

LabVIEW - Len

Len_2.vi

Len_2.vi

Len_2.vi

Len_2.vi

Len delivered the fastest code in LabVIEW, even with the WHILE loop. He is using a simplification of the sequence to only compute even valued members and their preceding member. Since every member of the sequence is the simple addition of the two prior members, any future member of the set can be computed by knowing two successive members of the sequence, and how far ahead to jump. In this case, the sequence is odd-odd-even, repeating so every third term is even. Compared to calculating every term in the Fibonacci sequence, this method results in only 1/3 of the loop iterations, but with twice the computations per iteration.

A good practice shown here is the use of labels for individual operations. Comments can be shown this way, but you need to be careful to make each one unique, as LabVIEW treats labels like variables. If any two are the same, bad things will happen.

This chart shows the relative execution speed of the LabVIEW entries. Keep in mind that the time in seconds was to complete the task 100,000 times. As you can see, all entries were pretty quick.

Python - Wes

Moving into Python, our first entry is from Wes, a Team 585 Alum. This code is straight forward and to the point with well-named variables. He uses some great features of Python to accumulate a list of all of the terms of the Fibonacci sequence, and then list slicing to select every third term (the even ones) to sum at the end. While this is a great way to do this problem, there is a lot of overhead when you append a term to the list. Internally, the Python interpreter has to allocate more memory to the list, every time it passes through the loop, which really hurts execution speed. In the end, props for self-documenting variable names and succinct comments in the code, but execution speed was almost four times slower than the fastest entry.

/Users/len/Programming_Contests/Week_2/Entries/Wes_2.py


   1    #!/usr/bin/local/python
   2    
   3    previous = 1
   4    current  = 2
   5    
   6    values = [1, 2]
   7    
   8    # Generate all fibonnaci values below 4,000,000
   9    while current + previous < 4000000:
  10      next = current + previous
  11      previous = current
  12      current = next
  13      values.append(next)
  14    
  15    # Every 3rd item in the fibonnaci sequence is even, so just slice and sum those
  16    print sum(values[1::3])

Python - Justin

Next up is Justin’s Python submission. Where should we begin? I’ll start with the first line, as it is indicative of other problems in the rest of the comments. It is REALLY important to understand the difference between a constant and a variable. If you are going to declare in a comment that something is a constant, then it should remain constant, forever. The next four lines declare our “constants” of j, u, s, and t. The problem here is that not one of these remain constant, and other than being the first four letters of Justin’s name, what are these? No, these are all variables, and they really want a descriptive name, because none of them are generic iterators. This is really bad practice, so don’t do this.

Line 6 is a sloppy comment, but you would be forgiven for not catching its inaccuracy as 's' could stand for sum. It doesn’t. ’t’ is the sum of the even numbers, and the end condition is not based on the sum exceeding 4,000,000, but the member of the sequence having hit that limit. The test is correct, but the comment is not. Line 8 is misleading as well, as the loop does construct the next member of the Fibonacci sequence, but does not collect the members as Wes’s entry did. The rest of the code and comments are benign, and the code returns the correct answer.

Code and comments should match. It may seem that picking on comments is pedantic, but this dissection is offered in the service of improving the craft of programming. You may not be the next person to try to fix your code. You shouldn’t lead others into a major time suck of having to reverse engineer your work when it is found that the comments are unreliable (or nonexistent).

Justin’s time took about 3.1 times longer to run than the fastest code. The execution speed was slowed by the modulo math check for even-ness before adding to the total.

/Users/len/Programming_Contests/Week_2/Entries/Justin_2.py


   1    # Create constants.
   2    j = 0
   3    u = 1
   4    s = 0
   5    t = 0
   6    # Make a while loop to go on until until the sum hits 4 million.
   7    while s <= 4000000:
   8        # Make the Fibonacci Sequence.
   9         s = j + u
  10         j = u
  11         u = s
  12         # See if the number is even and add it to t.
  13         if(s%2==0):
  14            t = t + s
  15    # Print the answer.
  16    print (t)

Python - Chloe

Next is Chloe’s Python entry. The first thing that jumps out about Chloe’s code, is that she is using inline comments to document what she is doing on every single line. Unfortunately, the comments diverge from the code, starting at line 5. In this code, v1 and v2 hold the preceding and current member of the sequence, regardless of if either number is even or odd. A similar incorrect comment sits on line 13, where there is only a multiple assignment which rolls forward the sequence.

Chloe’s entry took about 2.8 times longer to run than the fastest code. Lines 4 and 13 show a nice feature of Python, multiple assignments.

/Users/len/Programming_Contests/Week_2/Entries/Chloe_2.py


   1    
   2    sum=0 #We want to find a total that is even and within range of 4000000.
   3    
   4    v1, v2 = 0, 1 #We set a value 1 and a value 2 in the code so we have a starting point.
   5                  #The v2 is in place for evens, and v1 is in place for odds.
   6    
   7    while v2 < 4000000: #Starting a loop so it will continue the sequence.
   8        
   9        if v2 % 2 == 0: #We take the evens and if it is divisible by 2 we know they are even and let them pass so they can add t
        o the sum.
  10            
  11            sum += v2  #This adds the evens we got from the previous step.
  12            
  13        v1, v2 = v2, v1 + v2 #After knowing the evens and odds, we add them and see if they are equal to an even number.
  14        
  15    print(sum)

Python - Yair

Next up is Yair, a new friend from Israel. While Yair dispenses with using comments in his code, he does use expressive names for some of his variables. He defined a function called fibonacci() that does all of the work. Instead of testing for evenness, his entry uses modulo division to test for every third member calculated in the series.

Yair’s entry took about 1.7 times longer than the fastest entry. His use of a function is actually a key to the improvement in execution speed, a common trait of the remaining entries. The Python interpreter treats defined functions differently, and statically allocates memory used by the function. Because of this, code encapsulated within the function tends to run faster.

/Users/len/Programming_Contests/Week_2/Entries/Yair_2.py


   1    def fibonacci():
   2        x1 = 1;
   3        x2 = 1;
   4        sum = 0;
   5        evenSums = 0;
   6        counter = 0;
   7        while x1 < 4000000:
   8            if counter % 3 == 2:
   9                evenSums += x1
  10            sum = x1 + x2;
  11            x1 = x2;
  12            x2 = sum;
  13            counter += 1;
  14            
  15        return evenSums;
  16            
  17            
  18            
  19    
  20    print fibonacci();

Python - Jacob

Next is from Jacob, another Team 585 alumni. Jacob’s code is compact, well commented, and takes advantage of multiple assignments (like Chloe’s). One other distinctive trait of Jacob’s code is the use of a non-constant end condition. If the desired end condition were to be changed, it only needs to be modified within the calling of the function.

Jacob’s code took about 1.5 times longer than the fastest entry, and is probably as fast as you can get in Python when constructing the Fibonacci sequence. Why wasn’t it the fastest code? Read on.

/Users/len/Programming_Contests/Week_2/Entries/Jacob_2.py


   1    def fib(n):
   2        #1, 2 as initial terms.
   3        a, b, result = 1, 2, 0
   4        #Iterate over terms while less than input.
   5        while a < n:
   6            #Add first term if even.
   7            if a % 2 == 0:
   8                result += a
   9            #Continue to next terms.
  10            a, b = b, a+b
  11        #Finished iterating, print result.
  12        print(result)
  13    #Calculate sum of even Fibonacci numbers less than 4,000,000.
  14    fib(4000000)

Python - Len

The last entry is from Len. Similar to Yair’s and Jacob’s, it uses a function to calculate the sum of the even members of the sequence. This code is essentially a Python version of Len’s LabVIEW entry. It generates a new sum with every iteration of the loop, because it only is interested in minimal calculation required to get the even terms. This essentially means that this solution will twice the work, but one third as often as all of the other entries. It is algorithmically optimized for this particular problem, and does not compute the members of the sequence that it does not need.

/Users/len/Programming_Contests/Week_2/Entries/Len_2.py


   1    # Team 585 Programming Contest - Week 2
   2    #
   3    #==============================================================================
   4    #
   5    # Problem:
   6    # Each new term in the Fibonacci Sequence is generated by adding the previous
   7    # two terms. By starting with 1 and 2, the first ten terms would be:  
   8    
   9    #      1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 
  10    
  11    # By considering the terms in the Fibonacci sequence whoses values do not
  12    # exceed four million, find the sum of the even-valued terms. 
  13    #
  14    #==============================================================================
  15    
  16    # The problem statement incorrectly starts the sequence at 1, 2, 3, when it
  17    # should start with 1, 1, 2.  This doesn't really matter for this program, as
  18    # we are only interested in the even terms.  The Fibonacci sequence inherrently
  19    # has a set pattern of odd - odd - even, where every number is the sum of the
  20    # two previous terms.
  21    
  22    # A simplification to compute the even valued terms based on the previous even
  23    # valued term and it's predecessor can reduce the overhead of computation by a
  24    # factor of 3.
  25    #
  26    
  27    # Initialize seed values for computation loop.
  28    
  29    def sumEvenFibs(limit):
  30        predecessor = 1
  31        evenValued = 2
  32        total = evenValued
  33        
  34        while True:
  35            # Compute next even valued term and its predecessor from the previous
  36            # even valued term and its predecessor.  Both are required to compute
  37            # the next even valued term.
  38            
  39            newPredecessor = predecessor + (2 * evenValued)
  40            evenValued = (2 * predecessor) + (3 * evenValued)
  41            predecessor = newPredecessor
  42            
  43            # Check to see if new even valued term exceeds the limit.
  44            if evenValued < limit:
  45                # We're still good.  Add to sum.
  46                total += evenValued
  47            else:
  48                # We're done!
  49                break
  50            
  51        print(total)
  52    
  53    # Get sum of even Fibonacci numbers up to 4,000,000
  54    sumEvenFibs(4000000)

This bar graph shows the relative times of all of the Python entries. As with the LabVIEW code, each solution was executed 100,000 times to get the durations shown.