## Project Euler – Problem 2

June 11, 2012 at 10:14 am | Posted in Programming | Leave a commentTags: Project Euler, project euler solutions

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.
*

## Leave a Comment »

Blog at WordPress.com.

Entries and comments feeds.

## Leave a Reply