I am working my way through the second question on the website ProjectEuler.net. This one involves the Fibonacci Sequence:

Question 2:

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, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Prime: This one was fairly easy to optimize. My first attempt at this problem yielded the correct answer in my base 309 nanoseconds. That’s a good thing, but it also doesn’t give me a number to gauge my optimizations with. If I want to test a higher number, say 4,000,000,000, I will need to stop using integers and use doubles instead. This change causes me to not be able to use the modulus operation (%) and instead use fmod from the math.h library. As this isn’t as fast, we lose an accurate depiction of integer versus double speed. When testing 4,000,000,000 the solution is found in 3.7 microseconds. I changed the limit from 4,000,000 to a whopping 9*10^307 (yes, that’s 9 followed by 307 zeros) and it completes in 115 microseconds.

The results:

Limit             Speed
4,000,000         309 nanoseconds (base)
4,000,000,000     3.7 microseconds
9x10^307          115 microseconds

Unfortunately, you cannot get a variable to hold a number much higher than that. Of course, I should have expected results like that seeing how we are not incrementing by 1 (we are iterating by (n-1)+(n-2) where n is the current position in the sequence). By the 7th iteration we are already incrementing by 21. Without further ado, here is my first attempt:

double Run()
{
	sum = 0;
	limit = 4000000;

	//int num1 = 1, num2 = 2, temp;		//use this for small numbers
	double num1 = 1, num2 = 2, temp;	//use this for big numbers

	while(num2<= limit)
	{
		//if(num2 % 2 == 0)			//use this for small numbers
		if(fmod(num2, 2) == 0)	//use this for big numbers
			sum += num2;

		temp = num2;
		num2 += num1;
		num1 = temp;
	}

	return sum;
}

Optimization 1: There are two places I can see to make improvements on this formula. We can remove the test to see if the number is even, and we can remove the loop. Since the loop obviously isn’t impacting performance that much, I am going to skip it for now (maybe for good). So let’s focus on removing the test for even numbers. Looking at the Fibonacci Sequence, we can see a pattern emerge: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144… we can see that every 3rd number is even. Looking back at the code for Prime, we already have everything we need in place to optimize:

double Run()
{
	sum = 0;
	limit = 4000000;

	double num1 = 1, num2 = 1, num3 = 2;

	while(num3<= limit)
	{
		sum += num3;

		num1 = num2 + num3;
		num2 = num1 + num3;
		num3 = num2 + num1;
	}

	return sum;
}

We know form the above pattern that every 3rd term is even. Therefore, all we need to do is increment 3 times for every 1 iteration. I renamed the variable “temp” to “num3? to make it fit the standard of the rest of my code and perform 3 Fibonacci additions for every 1 loop. Speed is as follows:

Limit             Speed
4,000,000         309 nanoseconds (base)
4,000,000,000     309 nanoseconds (base)
9x10^307          4.9 microseconds

While I cannot find the optimization for 4 million or 4 billion, my max number yields an optimization ratio of 1:23. Not bad.

I could go on and try to remove the loop, but I think that is good enough for this problem. If anyone has any comments or improvements, please post them below.