-1

For a homework assignment we were asked to create a fibonacci number generator and it was mentioned that to note behaviour as N (the number of terms) exceeds 46.

This is my code:

#include <stdio.h>

int main(void) {
  int N;
  int i;
  int fn, fi, fj;
  fj = 1;
  fi = 1;
  FILE *fp;
  fp = fopen("fibb.txt", "w");

  printf("Enter the number of terms");
  scanf("%d", &N);
  for (i = 1; i <= N; i++) {
    if (i == 1 || i == 2) {
      fprintf(fp, "%d\n", fi);
    } else {
      fn = fi + fj;
      fj = fi;
      fi = fn;
      fprintf(fp, "%d\n", fn);
    }
  }
  fclose(fp);
  return 0;
}

fibb.txt file:

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
-298632863

Why are there negative numbers? The code works fine to predict fibonacci numbers for small N. Are the numbers too large for c to store or is there some memory allocation issue? I dont think the numbers should be too large to store since they are only 10 digit numbers.

Aykhan Hagverdili
  • 28,141
  • 6
  • 41
  • 93
Vishal Jain
  • 443
  • 4
  • 17
  • "they are only 10 digit numbers": any idea of what an `int` can accomodate ? By the way, what is an `int` ? –  Feb 01 '20 at 16:27
  • 3
    They are too large. An int typically has 32 bits, which means the biggest number it can hold is 2^32 - 1. Thats roughly 4 billion, so 10 digits. You can change the datatype to `uint64_t` to hold 64 bit numbers. If that is still not big enough for you you need to look around for bigint libraries. – flowit Feb 01 '20 at 16:31
  • Try using long long type and %lld for printf and see if that changes anything – mvp Feb 01 '20 at 16:32
  • 1
    Congratulation, you just made an int overflow – Cid Feb 01 '20 at 16:35
  • 1
    An `int` can reach a positive value of just over 2 billion ( 2 ^ 31 -1 ). You could use `unsigned int` which reaches 2 ^ 32 - 1, or even better `uint64_t` which reaches 2 ^ 64 - 1. (I used "^" as power symbol) – Sir Jo Black Feb 01 '20 at 16:43

2 Answers2

2

This is what is called a "Signed Overflow". This means you try to store numbers larger than a type can store. Formally, it causes undefined behavior. Switch to larger integral types like long, or long long. Since all the numbers you're working with are positive, also consider unsigned types like unsigned long long.

Contrary to what you may have read, signed overflow is unambiguously undefined behavior:

C17 Paragraph 3.4.3/3

EXAMPLE An example of undefined behavior is the behavior on integer overflow

Community
  • 1
  • 1
Aykhan Hagverdili
  • 28,141
  • 6
  • 41
  • 93
  • 1
    The behaviour is not undefined, it's clearly defined – Cid Feb 01 '20 at 16:36
  • @Cid where does the standard define signed overflow? – Aykhan Hagverdili Feb 01 '20 at 16:37
  • In the binary representation of signed numbers. the 32 bits signed integer 2147483647, in binary `0111 1111 1111 1111 1111 1111 1111 1111` + 1 gives `1000 0000 0000 0000 0000 0000 0000 0000` which is `-2147483648`. This is the [twos's complement](https://en.wikipedia.org/wiki/Two%27s_complement) – Cid Feb 01 '20 at 16:39
  • 1
    @Cid two's complement is not mandated to be used by the standard – Aykhan Hagverdili Feb 01 '20 at 16:40
  • It's not mandated, but it's mainly used, it's the most common representation – Cid Feb 01 '20 at 16:43
  • @Cid signed overflow is UB. Unsigned overflow isn't. The fact 2's complement is not mandatory is exactly why it is UB as per the standard. – Marco Bonelli Feb 01 '20 at 16:46
  • 1
    @Cid it is undefined behavior and compilers usually optimize assuming no overflow happens. See the update to my answer and also this [Why does integer overflow on x86 with GCC cause an infinite loop?](https://stackoverflow.com/q/7682477/10147399) – Aykhan Hagverdili Feb 01 '20 at 16:47
  • any idea as to why instead of just popping up some standard error like UNDEF or some thing for all large numbers, it swaps to negative numbers and alternates between negative and positive? I get that the numbers are too big to be stored as int, but not why this behaviour is seen. – Vishal Jain Feb 01 '20 at 16:59
  • @V.Jain Undefined behavior is not required to put up warnings. – Aykhan Hagverdili Feb 01 '20 at 16:59
  • @V.Jain requiring the implementation to detect overflow would have slowed the program down. C trusts that you will not cause undefined behavior. Trades safety for speed. – Aykhan Hagverdili Feb 01 '20 at 17:05
  • 1
    There is no reason to capitalize “signed overflow” or put it in quotation marks. It is not a special term. The actual phrase used for this in the C standard appears in C 2018 6.5 5: “If an *exceptional condition* occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined” (italics in the original). – Eric Postpischil Feb 01 '20 at 18:26
0

An signed "int" data type is normally 32 bits wide. So the largest positive number you can represent is (2^32-1)/2 which works out to 2147483647. This representation is called two's complement.

Once you exceed that in your calculation, the value starts to represent a negative number. If you want to make use of the entire 32-bit range for positive numbers, you should declare them as unsigned ints.or unsigned long long.

OldProgrammer
  • 12,050
  • 4
  • 24
  • 45