Project Euler 2 Acceleration 2.21 Save microseconds.

The terms of the Fibonacci sequence are the sum of the previous two terms. If the first two terms are 1, 2, then the first 10 terms are:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Find the sum of even-valued terms that have less than or equal to 4 million terms in the sequence. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202

At first, I wrote the code as I came up with.

def cof():
  (v1, v2) = (1, 2)
  max = 4 * (10**6)
  s = 0
  while v2<=max:
    if not v2 % 2: s += v2
    (v1, v2) = (v2, v1+v2)
  print s

When I was looking at the problem as to whether there was something that could be speeded up, I noticed that even numbers appeared every three terms.

When n1 is the term before the even number and n2 is the even number term, the terms n3, n4, n5 following them can be expressed by the following equations.

n4 is needed to derive the next term, but n3 can probably be omitted! Moreover, if you decide on even numbers, you should be able to omit the if statement that determines whether or not it is even!

So I wrote the following code.

def cof2():
  (v1, v2) = (1, 2)
  max = 4 * (10**6)
  s = 0
  while v2 <= max:
    s += v2
    (v1, v2) = (v1+2*v2, 2*v1+3*v2)
  print s

I commented out print and measured the time with the following code.

def get_time(func,name,num):
  import time
  print "%s start." % name
  total = 0
  for i in range(0,num):
    start = time.time()
    func()
    end = time.time()
    total += end - start 
  print "%s finished." % name
  print total

if __name__ == '__main__':
  num = 10 ** 6
  #num = 1
  get_time(cof,"cof",num)
  get_time(cof2,"cof2",num)

As a result, 1 million runs saved 2.21 seconds (2.21 microseconds per run).

If you execute it 100 million times, you will save 221 seconds (about 3 minutes and 40 seconds)! Great savings!

It took me about 15 minutes to write new code because it was a code that I only run once in my life.