Let's take a look at this problem: we want to produce a sum of even Fibonacci numbers within a predefined range.
Rearranged with minor edits for clarity:
#include <iostream>
using namespace std;
unsigned long fibonacci(unsigned long int *FIBO)
{
unsigned long i;
int sum=0,c=0, *EVEN = new int[2000000];
FIBO[0]=1; FIBO[1]=2;
for (i=2;i<3999999;i++){
FIBO[i]=FIBO[i-1]+FIBO[i-2];
if (FIBO[i]%2==0){
EVEN[c]=FIBO[i];
sum+=EVEN[c];
c++;
}
}
delete [] EVEN;
return sum;
}
int main(void)
{
unsigned long int fib[4000000];
cout << "SUM OF EVEN FIBONACCI NUMBERS: " << fibonacci(fib) << endl;
return 0;
}
First, let's remove unneeded code in the function fibonacci. We don't need to store even numbers, so we'll remove the EVEN array.
unsigned long fibonacci(unsigned long *FIBO)
{
unsigned long i, sum=0;
FIBO[0]=1; FIBO[1]=2;
for (i=2;i<3999999;i++){
FIBO[i]=FIBO[i-1]+FIBO[i-2];
if (FIBO[i]%2==0){
sum += FIBO[i];
}
}
return sum;
}
We can get a bit more clever though- we can prove that every third Fibonacci number will be even. Starting from Fib(0)=0, this allows us to make a new function:
unsigned long sum_even_fibonacci(unsigned long n)
{
unsigned long i, a=0, b=1, c=1, sum=0;
for (i=0;i<n/3;i++){
a = b + c; // Fib(3i)
b = a + c; // Fib(3i+1)
c = a + b; // Fib(3i+2)
sum += a; // Fib(3i) will always be even- add it to sum.
}
return sum;
}
This should produce the sum of the even Fibonacci numbers within the first n numbers of the series.
The new program, in full:
#include <iostream>
using namespace std;
unsigned long sum_even_fibonacci(unsigned long n)
{
unsigned long i, a=0, b=1, c=1, sum=0;
for (i=0;i<n/3;i++){
a = b + c; // Fib(3i)
b = a + c; // Fib(3i+1)
c = a + b; // Fib(3i+2)
sum += a; // Fib(3i) will always be even- add it to sum.
}
return sum;
}
int main(void)
{
cout << "SUM OF EVEN FIBONACCI NUMBERS: " << sum_even_fibonacci(4000000) << endl;
return 0;
}