My Ruminations on Software

Project Euler – Problem 2

I mentioned Project Euler in my previous post. Next problem was little bit hard to do and I rewrote my code 3 times before I got it right:

/* By considering the terms in the Fibonacci sequence whose values do not exceed four million, 
 * find the sum of the even-valued terms.
 */
#include <stdio.h>
 
unsigned long fib(unsigned long num);
 
 
int main(void)
{
  const unsigned long limit = 8;
  unsigned long sum = 0;
  unsigned long i = 0;
 
  for(i = 0; i <= limit; ++i)
    {
      unsigned long j = fib(i);
 
      if(0 == (j % 2))
        {
          sum += j;
        }
    }
 
  printf("Sum of all Fibonaci even numbers upto %lu = (%lu)\n", limit, sum);
 
  return 0;
}
 
 
unsigned long fib(unsigned long num)
{
  unsigned long temp = 0;
  
  if((0 == num) || (1 == num))
    {
      temp = 1;
    }
  else
    {
      temp = fib(num - 1) + fib(num - 2);
    }
 
  return temp;
}
 
 

What can you see from above code. I got the meaning of problem statement totally wrong. Problem says “I need to add all Fibonacci numbers with values upto 4 million” whereas I took it as “add all numbers upto 4 million as input to Fibonacci”. 2nd, What else is wrong ? Can you spot it ? Stop reading right now and run this in your compiler. If you have gcc then please use -ansi -pedantic -Wall -Wextra flags. Go ahead and try and come back again. This program keeps on running for 11 minutes when limit is 400. The recirsive call eats all CPU. Even after 11 minutes I killed it. My machine is quite average in terms of hardware. Imagine at 4 million as input, how many years it will take to complete ? So what do we do ? First we get our brains right that it requires us to add all Fibonacci values less than 4 millions. 2nd, we will not use recursion and instead we will make use of the fact that F(N) = F(N-1) + F(N-2) provided F(0) = F(1) = 1, where F is fibonacci for N. We can rememeber last two fibonacci numbers in some variables instead of using recursion to find out every time. Recursion uses a lot of stack and I don’t think you should assume that you will have stack for 4 millions. Here is the correct and new iterative version.

/* By considering the terms in the Fibonacci sequence whose values do not exceed four million, 
 * find the sum of the even-valued terms.
 */
#include <stdio.h>
 
int main(void)
{
  const unsigned long limit = 4000000;
  unsigned long sum = 0;
  unsigned long i = 0;
 
  unsigned long f = 1; /* Fibonacci(0); */
  unsigned long f2 = 1; /* Fibonacci(0); */ 
  unsigned long f1 = 1; /* Fibonacci(1); */
 
  for(i = 2; f <= limit ; ++i)
    {
      /* In first iteration, Fibonacci(2) = F(1) + F(0) */
      f = f1 + f2;
      if(0 == (f % 2))
        {
          sum += f;
        }
 
      f2 = f1;
      f1 = f;
    }
 
  printf("Sum of all Fibonaci even numbers upto %lu = (%lu)\n", limit, sum);
 
  return 0;
}
 

I still see something wrong with above code. Did you notice several issues ? Don’t just read ahead, read the code and see how it fits problem statement. Its using <= instead of < . Problem statement says “upto 4 millions” and that does not include 4 millionth term (##c on freenode correct me on this as I am not a native English speaker. I thought “upto” included 4 millions). Other problem is using iteger i. We are not iterating for a specific number of times but till a certain condition is reached without caring how many times we iterated. So we need to remove that counter.

/* By considering the terms in the Fibonacci sequence whose values do not exceed four million, 
 * find the sum of the even-valued terms.
 *
 * My Method: F(n) = F(n-1) + F(n - 2) (where F(0) = F(1) = 1)
 * find the sum of all values where F(n) is even, till 4 million
 *
 */
#include <stdio.h>

int main(void)
{
  const unsigned long limit = 4000000;
  unsigned long sum = 0;

  unsigned long f = 0; /* Fibonacci(0); */
  unsigned long f2 = 0; /* Fibonacci(0); */ 
  unsigned long f1 = 1; /* Fibonacci(1); */

  while((f1 < limit) && (f2 < limit))
    {
      /* In first iteration, F(2) = F(1) + F(0) */
      f = f1 + f2;
      if(f >= limit) break;

      if(0 == (f % 2))
	{
	  sum += f;
	}

      f2 = f1;
      f1 = f;
    }

  printf("Sum of all Fibonaci even numbers upto %lu = (%lu)\n", limit, sum);

  return 0;
}

How long it takes to execute. As per ideone.com , it take 0.02 seconds. And I was waiting for 11 minutes for the first piece of code. How much good programming practice is worth of ? a few thousands extra in salary of the programmer, a millions for the bugs caused or the entire bank account multi-billioon dollor corporation if it hires all bad programmers ? What do you think ?

Copyright © 2012 Arnuld Uttre, Village – Patti, P.O – Manakpur, Tehsil – Nangal, Distt. – Ropar, Punjab (INDIA)

Verbatim copying and distribution of this entire article are permitted worldwide, without royalty, in any medium, provided this notice, and the copyright notice, are preserved.