find the sum of even number not exceed four million

Hai all

i try to solve the this problem:
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

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


and here is my code:

Code Java:

---

public class Fibonacci {
 
	public static void main(String[] args) {
		int firstNum = 1;
		int seqNum = 0;
		int secNum = 1;
		long length = 1000 * 4000;
		int sumEvenNum = 0;
		System.out.println("length " + length);
 
		while (seqNum < length) {
			seqNum += firstNum;
 
			if (seqNum % 2 == 0) {
				//System.out.println("seqNum: " + seqNum);
				//System.out.println("sumEvenNum: " + sumEvenNum);
				sumEvenNum += seqNum;
				//System.out.println("even number: " + sumEvenNum);
			}
 
			firstNum = secNum;
			secNum = seqNum;
		}
 
		System.out.println("sumEvenNum: " + sumEvenNum);
	}
}

---

But the result is: 4613732, exceed four million, while the question require the value not exceed four million. can you help me to solve this problem??.

You're condition is testing for until your computed result is greater than or equal to 4000000. So naturally the result you have will be the very first fibonacci number larger than 4 million.

The easiest way to fix this is to keep a second variable which will keep track of the fibonacci number after the current one and stop when that number first gets larger than 4 million.

also, if I'm reading the original problem statement right, you're adding up fibonacci numbers less than 4 million. There are quite a few and it's possible that their sum (even with only ever other one) could add up to be over 4 million.

i guess the answer is :

Code Java:

---

public class Fibonacci {
 
    public static void main(String[] args) {
        int firstNum = 1;
        int seqNum = 0;
        int secNum = 1;
        long length = 1000 * 4000;
        int sumEvenNum = 0;
        System.out.println("length " + length);
 
        while (seqNum < length) {
            seqNum += firstNum;
 
            if (seqNum % 2 == 0) {
                //System.out.println("seqNum: " + seqNum);
                //System.out.println("sumEvenNum: " + sumEvenNum);
                sumEvenNum += seqNum;
                //System.out.println("even number: " + sumEvenNum);
            }
 
            if(sumEvenNum > length)
                break;
 
            firstNum = secNum;
            secNum = seqNum;
        }
 
        System.out.println("sumEvenNum: " + seqNum);
    }
}

---

This is the second Project Euler Challenge. Well I can tell you that the answer is indeed 4613732. You are asked to find the SUM of all the even valued numbers in the Fibonacci sequence below 4 million. That doesn't mean that the answer has to be below 4mil.

Your first answer looks correct to me. Here is my answer which was also correct:

Code Java:

---

int total = 0;
int max = 4000000;
int next = 1;
int last = 1;
 
while (next < max) {
	int temp = next;
	next = next + last;
	last = temp;
 
        if (next % 2 == 0) {
		total += next;
	}
}
 
return total;

---

Quote:

---

Originally Posted by ChristopherLowe

Code Java:

---

int total = 0;
int max = 4000000;
int next = 1;
int last = 1;
 
while (next < max) {
	int temp = next;
	next = next + last;
	last = temp;
 
        if (next % 2 == 0) {
		total += next;
	}
}
 
return total;

---

---

That piece of code would certainly do the job, but it can be made more efficient by implementing recursion also you can fix the swap part to a 2 variable one. A little bit of threading should make it even more efficient.

Thanks Mrc0d3r,

It takes about 0.0004 seconds to execute this code and it's a one of solution to a one of problem so I am not really interested in making it more efficient. But now that you mention it .. how would I 'fix the swap part to a 2 variable one'.

Quote:

---

Originally Posted by Mrc0d3r

That piece of code would certainly do the job, but it can be made more efficient by implementing recursion also you can fix the swap part to a 2 variable one. A little bit of threading should make it even more efficient.

---

Recursion definitely looks more elegant, but it is by no means more efficient. Fibonacci number computation is highly repetitive, so a dynamic programming solution (implemented iteratively) is the best way to compute Fibonacci numbers. Because computing Fibonacci numbers is very sequential (even with an iterative solution), I don't see any benefit of using a multi-threaded solution. If anything, the overhead from creating new threads, managing synchronization and data safety will far out-weigh any small, if any, benefit of a multi-threaded solution.

Honestly, I don't see how an iterative method can perform a swap without at least 3 variables.

Quote:

---

Originally Posted by helloworld922

Recursion definitely looks more elegant, but it is by no means more efficient. Fibonacci number computation is highly repetitive, so a dynamic programming solution (implemented iteratively) is the best way to compute Fibonacci numbers. Because computing Fibonacci numbers is very sequential (even with an iterative solution), I don't see any benefit of using a multi-threaded solution. If anything, the overhead from creating new threads, managing synchronization and data safety will far out-weigh any small, if any, benefit of a multi-threaded solution.

---

Completely agree ! And regarding the multi-threading part, I thought we could split up the work to threads :S

Quote:

---

Originally Posted by ChristopherLowe

how would I 'fix the swap part to a 2 variable one'.

---

Quote:

---

Originally Posted by helloworld922

Honestly, I don't see how an iterative method can perform a swap without at least 3 variables.

---

This can do the job I suppose..

Code Java:

---

next = next + last;
last = next - last;

---

Quote:

---

Originally Posted by Mrc0d3r

This can do the job I suppose..

Code Java:

---

next = next + last;
last = next - last;

---

---

Ahh, that's a very interesting solution. There's not any significant performance boost (or ding), but it does look cool.

Quote:

---

Originally Posted by Mrc0d3r

This can do the job I suppose..

Code Java:

---

next = next + last;
last = next - last;

---

---

Haha! That's brilliant! Great logic my friend.

Quote:

---

Originally Posted by helloworld922

Ahh, that's a very interesting solution. There's not any significant performance boost (or ding), but it does look cool.

---

Yeah right, a few micro-seconds difference.(and space isn't quite a big problem these days though !)

Quote:

---

Originally Posted by ChristopherLowe

Haha! That's brilliant! Great logic my friend.

---

Thanks !