CODEWITHSUNDEEP
c
Rosie Red
Rosie Red

Reputation: 73

Why doesn't this code work for a[100] and above? (project euler 2 in C)

Here is my code:

I don't understand why it gives me the wrong answer above 50.

#include<stdio.h>

int main()
{
    long long int i, sum=0;
    long long int a[50];
    a[0] = 1;
    a[1] = 1;
   for(i=2;i<50;i++)
   {
        a[i] = a[i-1] + a[i-2];
        if(a[i]%2==0 && a[i]<4000000) 
        sum = sum + a[i];
   }
printf("%lld", sum);
return 0;
}

Upvotes: 0

Views: 63

Answers (2)

Tom Zych
Tom Zych

Reputation: 13576

Your first mistake was not breaking out of the loop when a term exceeded 4,000,000. You don’t need to consider terms beyond that for the stated problem; you don’t need to deal with integer overflow if you stop there; and you don’t need anywhere near 50 terms to get that far.

Nor, for that matter, do you need to store all of the terms, unless you want to look at them to check correctness (and simply printing them would work just as well for that).

Upvotes: 2

Tamas Hegedus
Tamas Hegedus

Reputation: 29926

You have an integer overflow. Fibonacci numbers get really big. Around F(94) things get out of the range of 64 bit integers (like long long).

F(90) = 2880067194370816120   >= 2^61
F(91) = 4660046610375530309   >= 2^62
F(92) = 7540113804746346429   >= 2^62
F(93) = 12200160415121876738  >= 2^63
F(94) = 19740274219868223167  >= 2^64
F(95) = 31940434634990099905  >= 2^64
F(96) = 51680708854858323072  >= 2^65

When the overflow happens, you will get smaller, or even negative numbers in a instead of the real fibonacci numbers. You need to workaround this overflow.

Upvotes: 2

Related Questions