What is Sum of Even Terms In Fibonacci (<4million)? [Large Value Datatype Confusion]

Question

By starting with 1 and 2, the first 10 terms of Fibonacci Series 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 4 million.

SOLVED: Actually, I managed to get the solution myself. Here's my program. It works.

#include <stdio.h>
int main() {
    int x=1,y=2,sum,limit;     //Here value of first 2 terms have been initialized as 1 and 2
    int evensum=2;             //Since in calculation, we omit 2 which is an even number
    printf("Enter Limit: ");   //Enter limit as 4000000 (4million) to get desired result
    scanf("%d",&limit);
    while( (x+y)<limit ) {
        sum=x+y;
        x=y;
        y=sum;
        if (sum%2==0)
            evensum+=sum;
    }
    printf("%d \n",evensum);
    return 0;
}

Answer 1

Use BigInt.

Then again, unsigned int stores values up to over 4 billion, so you shouldn't be having any problems even with "sum of all fibonacci numbers up to 4 million" (which, obviously, has to be less than 8 mil)?

Answer 2

int is big enough for values in the millions on almost every modern system, but you can use long if you are worried about it. If that still gives you weird results, then the problem is with your algorithm.

Answer 3

Since you only want up to four million, it's likely that int is not your problem.

It's quite possible that your program is buggy and that the data storage is just fine, so you should test your program on smaller values. For example, it's clear that the sum of the first three even terms is 44 (hint: every third term is even) so if you run your program with a cap of 50, then you should instantly get 44 back. Keep running small test cases to get confidence in the larger ones.

Answer 4

For security, use the 'long' data type; the C standard requires that to hold at least 4 billion. On most machines, 'int' will also hold 4 billion.

enum { MAX_VALUE = 4000000 };
int sum  = 0;
int cnt  = 0;
int f_n0 = 0;
int f_n1 = 1;
int f_n2;

while ((f_n2 = f_n0 + f_n1) < MAX_VALUE)
{
    if (++cnt % 2 == 0)
        sum += f_n2;
    f_n0 = f_n1;
    f_n1 = f_n2;
}
printf("%d\n", sum);

It might be better to unwrap this loop to avoid the 'cnt' counter; simply evaluate two steps of the Fibonacci series in each iteration - but beware of overstepping the end condition.

Answer 5

Try changing this:

while (i<limit-2)

to this:

while (y<limit)

As written, your program is cycling until it gets to the 4 millionth Fibonacci number (i.e. when i gets to 4 million, though overflow obviously happens first). The loop should check to see when y (the larger Fibonacci number) becomes greater than 4 million.

Answer 6

One bug that you're probably seeing is the bad formatting of your printf() statements. With a printf("%d %d") followed by a printf(" %d"), numbers of 3, 5, 8, 13, 21, 34, 55 will print as: 3 5 813 21 3455 which certainly looks like funky output with wildly inappropriate numbers. You need a few more spaces or linefeeds: printf("%d %d\n"), printf(" %d\n").

I also don't see where you're actually checking only for the even terms to contribute to the sum.

Answer 7

Your program prints F_1 + ..+ F_limit and not F_1 + ... F_n with F_n < limit as you described.

Check the Wikipedia article on Fibonacci Numbers and Sloane A000045: Fibonacci numbers grows exponentially. Checking this table F_48 = 4807526976 which exceeds int. F_100 is 354224848179261915075 which surely overflows even int64_t (your stack doesn't, though).

Answer 8

Guys, I got the answer. I confirmed the result and int can handle it. Here's my program:

#include <stdio.h>
int main() {
    int x=1,y=2,sum,limit;     //Here value of first 2 terms have been initialized as 1 and 2
    int evensum=2;             //Since in calculation, we omit 2 which is an even number
    printf("Enter Limit: ");   //Enter limit as 4000000 (4million) to get desired result
    scanf("%d",&limit);
    while( (x+y)<limit ) {
        sum=x+y;
        x=y;
        y=sum;
        if (sum%2==0)
            evensum+=sum;
    }
    printf("%d \n",evensum);
    return 0;
}

Thx for all the replies and help. "Thinking on my feet" to the rescue :)