Starting from 1 and 2, compute the sum of all even fibonacci numbers (while these numbers are smaller or equal to 4 million)
I am trying to sum all even fibonacci numbers up to 4e6
, but it doesn't give me anywhere the right result, and I don't understand where I've messed up. In my mind, the conditions for the if
are correct.
My fibonacci()
function, and my function to sum the even numbers up, is below.
int fibonacci(int k) //compute the k-th fibonacci number (with EulerProject formula)
{
if (k == 1 || k == 2)
{
return k;
}
{
return (fibonacci(k-1) fibonacci(k-2));
}
}
int evenfibonacci()
{
int result = 0;
for (int k = 1; fibonacci(k)<=4e6;) {
if (fibonacci(k)%2 == 0 ) {
result = fibonacci(k);
k ;
} else {
k ;
}
}
}
CodePudding user response:
evenfibonacci()
is declared as returning an int
value, but does not actually return
anything, which is undefined behavior. Thus, the return value is always indeterminate, it ends up returning random garbage, which is why you never get a good result.
You need to add a return
statement, eg:
int evenfibonacci()
{
int result = 0;
for (int k = 1; fibonacci(k) <= 4e6; k) {
if (fibonacci(k) % 2 == 0) {
result = fibonacci(k);
}
}
return result; // <-- ADD THIS
}
That being said, calling fibonacci(k)
3 times per loop iteration is very inefficient, calculating the same values over and over, especially for higher values of k
. You should call it only 1 time per loop, eg:
int evenfibonacci()
{
int result = 0;
for (int k = 1; k <= 33; k) {
int value = fibonacci(k);
if (value % 2 == 0) {
result = value;
}
}
return result;
}
Of course, a better solution would be to get rid of fibonacci()
altogether, and instead use an iterative approach to calculating only new values per iteration, eg:
int evenfibonacci()
{
int result = 2;
int last[2] = {1, 2};
for (int k = 3; k <= 33; k) {
int value = last[0] last[1];
if (value % 2 == 0) {
result = value;
}
last[0] = last[1];
last[1] = value;
}
return result;
}