Saturday, August 13, 2011

Learning Python with Project Euler: Problem 2

This is another short problem in Project Euler. The problem states:

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

So, we need to know what the Fibonacci sequence is. The first two numbers in the sequence are 1 and 1. After that, the next number is the sum of the previous two numbers.  Mathematically, we can define this sequence by:  F(n)=F(n-1)+F(n-2), F(0) = 1, F(1) = 1

Below is my Python implementation.  I use a tuple, bitwise and operation, Python's ability to assign multiple variables on the same line.

# only persist the last 2 values of the sequence
vsum, fib_nums = 0, (1, 1)
while fib_nums[0] < 4000000:
  # shift the 2nd value to the 1st position, add the previous 2 values and set
  # it at the 2nd position
  fib_nums = (fib_nums[1], fib_nums[0] + fib_nums[1])
 
  # only add latest fib number if it is even; using bitwise operations we can
  # tell if a number is even or odd by checking the last bit
  if fib_nums[1] & 1 == 0: vsum += fib_nums[1]

print 'sum: ' + str(vsum)

3 comments:

  1. Here's my implementation: http://pastebin.com/4tYwyf2w

    The efficiency is similar, but your solution is a lot more concise.

    ReplyDelete
  2. Thanks! That implementation is seems to be about 2.5x more efficient. The biggest factor it seems is my use of a tuple instead of just two variables (the tuple really brings nothing to the table, not sure why I used it). The other factor is that you handle 2 numbers in the sequence per iteration, where mine handles 1.

    Changing my implementation to use 2 variables instead of a tuple increased the performance twofold, making yours about 1.2x faster. I'm surprised to see that big of a difference.

    ReplyDelete
  3. Wow! There's so much you can learn with the help of statistics! When I started work on my implementation I hadn't looked at your solution so the thought of using tuples didn't occur to me.

    Anyway, I was just looking at the problem again and noticed a pattern. If you look at the terms of the Fibonacci series you'll see that two consecutive terms cannot be even!

    So, the second 'if' clause in my implementation is introducing some spurious checks, i.e., if I can confirm that 'a' is even, I don't even have to check 'b'. Hence, replacing the 'if' with an 'elif' should improve the efficiency of the solution somewhat.

    Here's a link to the updated implementation: http://pastebin.com/Gwsqr0NM.

    ReplyDelete