{"id":133,"date":"2009-07-06T20:51:42","date_gmt":"2009-07-07T04:51:42","guid":{"rendered":"http:\/\/www.madpickles.org\/rokjoo\/?p=133"},"modified":"2009-07-08T14:37:57","modified_gmt":"2009-07-08T22:37:57","slug":"project-euler-problem-2","status":"publish","type":"post","link":"https:\/\/www.madpickles.org\/rokjoo\/2009\/07\/06\/project-euler-problem-2\/","title":{"rendered":"Project Euler Problem #2"},"content":{"rendered":"<p>Problem 2 from <a href=\"http:\/\/www.projecteuler.net\">projecteuler<\/a> requested the sum of all the even <a href=\"http:\/\/en.wikipedia.org\/wiki\/Fibonacci_number\">Fibonacci numbers<\/a> below 4 million. I had seen references to &#8220;generators&#8221; in some of the Python howtos and after further reading, this seemed like a reasonable place to try them out.<\/p>\n<pre>\r\ndef fibGenerator():\r\n fib0 = 0\r\n fib1 = 1\r\n while True:\r\n  yield fib1\r\n  fibNext = fib0 + fib1\r\n  fib0 = fib1\r\n  fib1 = fibNext\r\n<\/pre>\n<p>Then all I had to do was keep track of a running total of the even numbers which lead to:<\/p>\n<pre>\r\ndef sumEvenFibs():\r\n fib = fibGenerator()\r\n sum = 0\r\n nextFib = fib.next()\r\n while nextFib < 4000000:\r\n  if nextFib &#038; 1 == 0:\r\n   sum += nextFib\r\n  nextFib = fib.next()\r\n return sum\r\n<\/pre>\n<p><code><br \/>\niterations = 1000<br \/>\nt = timeit.Timer(\"sumEvenFibs()\",\"from __main__ import sumEvenFibs\")<br \/>\nprint \"Answer: %d. %d iterations took %.3f seconds\" % (sumEvenFibs(), iterations, t.repeat(1,iterations)[0])<br \/>\n<\/code><\/p>\n<p>Answer: 4613732. 1000 iterations took 0.109 seconds<\/p>\n<p>The while loop in sumEvenFibs didn't seem very Pythonic so I thought about how I could go about removing it. I could change fibGenerator to take a parameter for the maximum Fibonacci number to generate. In addition, the condition that a number be even was conceptually a filter that could easily be captured in a lambda function. I ended up with this:<\/p>\n<pre>\r\ndef fibGenerator(maxFib):\r\n fib0 = 0\r\n fib1 = 1\r\n while fib1 < maxFib:\r\n  yield fib1\r\n  fibNext = fib0 + fib1\r\n  fib0 = fib1\r\n  fib1 = fibNext\r\n\r\ndef sumEvenFibs():\r\n fib = fibGenerator(4000000)\r\n return sum(filter((lambda x: x &#038; 1 == 0),fib))\r\n<\/pre>\n<p>Which performed about as well, and is much cleaner. Looking through the forums it turns out there is a pattern to the Fibonacci numbers (odd, odd, even...) so it's pretty easy to get rid of the even check as well:<\/p>\n<pre>\r\ndef evenFibGenerator(maxFib):\r\n fib0 = 1\r\n fib1 = 2\r\n while fib1 < maxFib:\r\n  yield fib1\r\n  temp = fib0 + (2 * fib1)\r\n  fib1 = (2 * fib0) + (3 * fib1)\r\n  fib0 = temp\r\n\r\ndef sumFibs():\r\n fib = evenFibGenerator()\r\n return sum([f for f in fib])\r\n<\/pre>\n<p>Not suprisingly this cuts the runtime by about 50%: Answer: 4613732. 1000 iterations took 0.043 seconds. On to the next problem...<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 2 from projecteuler requested the sum of all the even Fibonacci numbers below 4 million. I had seen references to &#8220;generators&#8221; in some of the Python howtos and after further reading, this seemed like a reasonable place to try them out. def fibGenerator(): fib0 = 0 fib1 = 1 while True: yield fib1 fibNext [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[18,11,19,17],"_links":{"self":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/133"}],"collection":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/comments?post=133"}],"version-history":[{"count":3,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/133\/revisions"}],"predecessor-version":[{"id":137,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/133\/revisions\/137"}],"wp:attachment":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/media?parent=133"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/categories?post=133"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/tags?post=133"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}