CODEWITHSUNDEEP
c
ch15
ch15

Reputation: 81

General Fibonacci, why is it overflowing?

I am trying to create a general fibonacci series where the starting values can be variable, depending on what the user wants. For example, instead of starting with values 0, 1, or 1, 1, as it usually does, it can start with 3, 6, or 10, 21, or whatever the user wants. We then want to get the nth value of that series.

I tried my code for a = 10 and b = 21, and I wanted a big value, however it didn't work. So I started checking where the problem was. With those starting values: for n = 37, 38, 39, the output should be 405812042, 656617677, 1062429719 respectively. When I run my code for values n = 37 and n = 38, both answers are correct. However when I try 39, this is the value I get: 62429712.

This is my code:

#include <stdio.h>

int main(void)
{
  unsigned long long a, b, hn, value;
  int scenarios;

  scanf("%d", &scenarios);

  for (int i = 0; i < scenarios; i++){
    scanf("%lld%lld%lld", &a, &b, &hn);
    if (hn == 1)
      value = a;
    else if (hn == 2)
      value = b;
    else{
      for (int j = 3; j <= hn; j++){
        value = a + b;
        a = b;
        b = value;
      }
    //value %= 1000000007;
    }
    printf("%lld\n", value);
  }


}

EDIT: According to the problem specification, the answer should be module 1000000007. The output I get if I get the 514th value is 2903631044495864380, and to be honest I don't know how to verify this value. If I do 2903631044495864380 mod 1000000007, my answer is 170447212, but according to the problem this answer should be 859861000. Any idea how to verify this?

Upvotes: 1

Views: 90

Answers (2)

gsamaras
gsamaras

Reputation: 73366

Change this:

scanf("%lld%lld%lld", &a, &b, &hn);

to this:

scanf("%llu%llu%llu", &a, &b, &hn);

Change this:

printf("%lld\n", value);

to this:

printf("%llu\n", value);

since these variables are of type unsigned long long.

EDIT

It seems like (from your edit) you need to change this:

value = a + b;

to this:

value = (a + b) % 1000000007;

Upvotes: 4

grek40
grek40

Reputation: 13438

You misinterpreted the point where you should calculate the modulo according to your exercise.

You don't compute the end sum before doing modulo, but you apply modulo to the intermediate results:

for (int j = 3; j <= hn; j++)
{
    value = (a + b) % 1000000007; // there
    a = b;
    b = value;
}

Also, change your scan/print format to '%llu', as @gsamaras suggested.

Upvotes: 2

Related Questions