Problem 2 - Fibonachi Sequence

Problem 2

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.

Solution

Here's the code for Problem 2:

#!/usr/bin/env python

def nextfib(a,b): #compute the next Fibonachi term
c = a + b
return (b,c) #keep the previous term

if __name__ == '__main__' :

import sys
a = 1
b = 2
mysum = 0
val = int(sys.argv[1]) #Bad code, assumes input is an int
while(b < val):
if b%2==0: mysum += b #add it up if it's even
(a,b) = nextfib(a,b)
print(mysum) #print the answer at the end

You can run this code with the command:

python fibsum.py 4000000

The correct answer is:  4613732

Approach

The Fibonachi sequence is straight forward to compute.  You need to store the last two values in the sequence and add them up the get the next term.  If the value is even, you add it to the sum.

The only real programmatic difference between this and the previous problem was the use of a subroutine.  You can see the syntax for a subroutine here:

def nextfib(a,b): #compute the next Fibonachi term
c = a + b
return (b,c) #keep the previous term

Benchmarks

There was very little difference between the interpreters for this problem.  The Fibonachi sequence grows very quickly and it was difficult to get the compute time up enough for a benchmark.  As before, Jython was much slower and I believe we're seeing the virtual machine start-up time more than the actual compute time.  Java + Python takes longer to load than Python, which comes as no surprise.

Problem #2 Benchmarks

time python fibsum.py 400000000000000000000000000000000000000000000000000000000000000000000000000000

324236912809324524060519206539762341175704857242759930854194179672563128605028


real 0m0.025s

user 0m0.020s

sys 0m0.004s

time python -O fibsum.py 400000000000000000000000000000000000000000000000000000000000000000000000000000

324236912809324524060519206539762341175704857242759930854194179672563128605028


real 0m0.047s

user 0m0.040s

sys 0m0.004s

time python3 fibsum.py 400000000000000000000000000000000000000000000000000000000000000000000000000000

324236912809324524060519206539762341175704857242759930854194179672563128605028


real 0m0.032s

user 0m0.028s

sys 0m0.000s

time python3 -O fibsum.py 400000000000000000000000000000000000000000000000000000000000000000000000000000

324236912809324524060519206539762341175704857242759930854194179672563128605028


real 0m0.082s

user 0m0.076s

sys 0m0.004s

time pypy fibsum.py 400000000000000000000000000000000000000000000000000000000000000000000000000000

324236912809324524060519206539762341175704857242759930854194179672563128605028


real 0m0.035s

user 0m0.020s

sys 0m0.012s

time pypy -O fibsum.py 400000000000000000000000000000000000000000000000000000000000000000000000000000

324236912809324524060519206539762341175704857242759930854194179672563128605028


real 0m0.035s

user 0m0.016s

sys 0m0.016s

time jython fibsum.py 400000000000000000000000000000000000000000000000000000000000000000000000000000

324236912809324524060519206539762341175704857242759930854194179672563128605028


real 0m1.514s

user 0m3.204s

sys 0m0.164s

Conclusion

The relatively short compute time isolated the start-up time difference between Jython and the various Pythons.  At least Jython ran this time.    This was another easy problem and the code is simple.  The syntax for a subroutine was introduced for any beginners.