Type declaration problem in C (fibonacci numbers)

Question

I am an inexperienced C beginner. I have wrote this following to print fibbonaci numbers, which works well to some where below 50 numbers. It produces nonsense however if going beyond 50 numbers. I am almost certain this is a type decleration problem, but I can't figure out where the problem raises. Any help is appreciated.


#include <stdio.h>

void fib(int* a, int*  b)
{
    int acp = *a;
    *a = *b;
    *b += acp;
}

int nth(int n)
{
    int a = 0;
    int b = 1;
    for (int i = 0; i < n; ++i) {
        fib(&a, &b);
    }
    return a;
}

int main()
{
    for (int i = 0; i < 50; ++i) {
        printf("%ith fib: %i\n", i, nth(i));
    }
    return 0;
}

prints:

1th fib: 1
2th fib: 1
3th fib: 2
4th fib: 3
5th fib: 5
6th fib: 8
...
45th fib: 1134903170
46th fib: 1836311903
47th fib: -1323752223
48th fib: 512559680
49th fib: -811192543

This might point you in the right direction: https://stackoverflow.com/questions/1855459/maximum-value-of-int — Scott Hunter, Jun 22 '21 at 12:33
You have exceeded the range of `int`. if you use `unsigned long long` you can go to the 94th Fibonacci term before it overflows the type. And after that you either need bignum or `double` and accept that you lose precision. — Weather Vane, Jun 22 '21 at 12:34
@WeatherVane I changed the `int`s in the fib function and in the local variables `a` and `b` in nth to unsigned long long, but am still getting the same results. — Student, Jun 22 '21 at 12:53
`printf("%ith fib: %llu\n", i, nth(i));` Use `%llu` for `unsigned long long`. Aside: the code is very inefficient, as it computes every previous term to find any term. So when you compute say the 5th term, you also compute the 3rd and 4th term, which were previously computed. — Weather Vane, Jun 22 '21 at 12:54
The first chapters of any C programming book typically addresses the limits of integers. I remember that this was explained during the very first lesson of a beginner programming class I took back in high school. — Lundin, Jun 22 '21 at 13:24

score 2 · Answer 1 · answered Jun 22 '21 at 12:51

2

The problem is the "size" of int, which can store numbers in range from -2,147,483,648 to 2,147,483,647. You could use unsigned int to make the range go from 0 to 4,294,967,295, but overall, it would not be a good improvement.

It makes us go further, but at least we know that if we work with integers, we may use unsigned to make the range bigger for our case. Thus, we can use unsigned long long (or unsigned long long int), which will store way more numbers than int (up to 18,446,744,073,709,551,615).

There is also another way which you may use, but is a bit different and probably off-topic. This would be using double type and calculating values of next Fibonacci numbers using Binet's formula. The caveat is, when calculating big numbers, you will lose the precision, thus the values you may get will be approximations.

answered Jun 22 '21 at 12:51

whiskeyo

873
1
9
19

`double` has a wider range than does `long` or `long long`, but it (generally) has less precision. If one needs to compute *exact* numbers larger than `unsigned long long` can accommodate, then `double` is the wrong direction to go. An arbitrary-precision numeric library such as [GMP](https://gmplib.org/) is probably the best bet in that case. – John Bollinger Jun 22 '21 at 12:57
1

The interval of numbers that `int` can represent is flexible in the C standard and may vary between C implementations. Answers should not state there is a single interval, such as −2,147,483,648 to 2,147,483,647. This is a common interval, but students should be cautioned not to rely on this or other characteristics that may vary in C implementations. – Eric Postpischil Jun 22 '21 at 13:04
1

@EricPostpischil this is completely true, but I assumed that an inexperienced C programmer (basically students who learn C) are using their computers, which usually handle `int` as a 32-bit value. Of course it may vary on older computers, depending on their CPU architeture. – whiskeyo Jun 22 '21 at 21:30

Zilog80 · Answer 2 · 2021-06-27T02:32:43.063

To add on @whiskeyo answer, here is an implementation working for any size of integers, limited to a maximal value of 2 ^ (2 ^ 32 x 8) - 1 [ simply a 4GB integer ] and mainly by your system resources (your RAM...).

To overcome system integers sizes (see limits.h), one way is to manipulate theses integers as a bits chain, while applying adequate arithmetic.

In this basic example, we define a "number" as an array of bytes with a defined "size", it is the s_num object. The fib function here computes a = b + a by a simple carry report while adding byte by byte the "number" b to the "number" a. To display the computed number, we use printf capabilities while we can (8 bytes or less "number") and a simple hexadecimal display over 8 bytes.

An interesting work could be to build a decimal display for "number" over 8 bytes, one that could work byte by byte to output decimal digits in the same way (warning, that's not easy maths).

EDIT: Adding comments and take the point from @WeatherVane about reusing preceding computed Fibonacci in the main iteration loop. Improve readability by expanding byte arithmetic expressions in fib.

EDIT: Use of command line argument for N. Add an extract of the output.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// The s_num representing an integer as an array of bytes with a size.
// The [bytes] member stores the bytes from the least significant to the
// most significant.
struct s_number {
  unsigned char *bytes;
  unsigned int size;
};

typedef struct s_number s_num;

// This function build a s_num able to store [size] bytes.
// Returns the corresponding s_num pointer or NULL if something goes wrong.
s_num *new_num(unsigned int size) {
  s_num *num = malloc(sizeof(s_num));
  if (num != NULL) {
    num->bytes = malloc(size);
    if (num->bytes == NULL) {
      perror("Failed to allocate. ");
      free(num);
      return NULL;
    }
    if (memset(num->bytes, 0, size) == NULL) {
      perror("Failed to initialize. ");
      free(num->bytes);
      free(num);
      return NULL;
    }
    num->size = size;
  }
  return num;
}
// This function deallocate the provided s_num.
// Returns 0 or anything else if something goes wrong.
int free_num(s_num *num) {
  if (num != NULL) {
    if (num->bytes != NULL) free(num->bytes);
    free(num);
  }
  return 0;
}
// This function build a copy of the provided s_num.
// Returns the corresponding s_num pointer or NULL if something goes wrong.
s_num *dup_num(s_num *num) {
  s_num *dup;
  if (num == NULL) return NULL;
  dup = new_num(num->size);
  if (dup == NULL) {
    perror("Failed to allocate a dup. ");
    return NULL;
  }
  if (memcpy(dup->bytes, num->bytes, num->size) == NULL) {
    perror("Failed to duplicate. ");
    free_num(dup);
    return NULL;
  }
  return dup;
}
// This function extend the byte array up to [size] and fill the new extent
// with 0. 
// Returns the s_num pointer or NULL if something goes wrong.
s_num *extend_num(s_num *num, unsigned int size) {
   unsigned char *tmp;
  if (num == NULL) return NULL;
  if (size > num->size) {
    tmp = realloc(num->bytes, size);
    if (tmp == NULL) {
      perror("Failed to re allocate. ");
      return NULL;
    }
    num->bytes = tmp;
    if (memset(num->bytes + num->size, 0, size - num->size) == NULL) {
      perror("Failed to initialize. ");
      return NULL;
    }
  }
  return num;
}
// A simple method to display s_num, in decimal up to 8 bytes, in hex after.
// Returns anything other than 0 if something goes wrong.
int display_num(s_num *num) {
  if (num == NULL) return 1;
  unsigned int size = num->size;
  if (size > 8) {
    printf(" => 0x");
    while(size-- > 0) { printf("%02X", num->bytes[size]); }
    printf("\n");
  } else {
    if (size > 0) {
      unsigned long long fordisp = 0;
      while(size-- > 0) { fordisp += ((unsigned long long )num->bytes[size]<<(8*size)); }
      printf("%llu\n", fordisp);
    } else{
      printf("Empty\n");
    }
  }
  return 0;
}

// Fibonacci processor, it adds B to A and return a copy of the original A.
s_num *fib(s_num *a, s_num *b) {
   unsigned char *a_offset;
   unsigned char *b_offset;
   unsigned int b_size;
   unsigned int a_size;
   unsigned char carry;
   unsigned char next_carry;
   s_num *dup = NULL;
   if (a == NULL || b == NULL) return NULL;
   if (a->bytes != NULL && b->bytes != NULL) {
     // We keep a duplicate of A, as B should become A at the end
     dup = dup_num(a);
     if (dup == NULL) return NULL;
     if (extend_num(a, b->size) == NULL) {
       free_num(dup);
       return NULL;
     }
     // Offsets pointers for A and B, and their respective size in bytes
     a_offset = a->bytes;
     a_size = a->size;
     b_offset = b->bytes;
     b_size = b->size;
     // The carry we may have to port byte to byte, initialy 0.
     carry=0;
     // We consider at first all the bytes from A, adding from B while we can.
     while(a_size-- > 0) {
       if (b_size > 0) {
         // While we have bytes in B, we add them, carry included, to the 
         // corresponding bytes in A
         if ((unsigned int) *a_offset + *b_offset + carry > 255u) {
           next_carry=1;
         } else {
           next_carry=0;
         }
         // The following line is in fact :
         //*a_offset++ += *b_offset++ + carry;
         // We have anyway to let the C compiler know that we look voluntary to 
         // discard any overflow from the unsigned char cast, as we already have
         // the carry from the preceding code.
         *a_offset = (unsigned char) ((unsigned int)*a_offset + *b_offset + carry); a_offset++; b_offset++;
         carry = next_carry;
         b_size--;
       } else {
         // No more bytes in B, if there is no carry left, we can leave the loop
         if (carry == 0) break;
         // If there is a carry left, we add it to A. The resulting addition 
         // can also imply another carry.
         if ((unsigned int) *a_offset + carry > 255u) {
           next_carry=1;
         } else {
           next_carry=0;
         }
         // The following line is in fact :
         //*a_offset++ += carry;
         // We have anyway to let the C compiler know that we look voluntary to 
         // discard any overflow from the unsigned char cast, as we already have
         // the carry from the preceding code.
         *a_offset = (unsigned char) ((unsigned int)*a_offset + carry); a_offset++;
         carry = next_carry;
       }
     }
     // When the carry implies one more byte for the number
     if (carry > 0) {
       if (extend_num(a, a->size + 1) == NULL) {
         free_num(dup);
         return NULL;
       }
       a->bytes[a->size++] = carry;
     }
   }
   // We return the copy of the original A
   return dup;
}
// Your nth function adapted to work with s_num and able to take a start point
// from fibonacci current and previous.
// Beware that the function will free the s_num provided in previous.
s_num *nth(unsigned int n, s_num *current, s_num *previous)
{
    // We define A and B as s_num
    s_num *a = NULL;
    s_num *b = NULL;
    unsigned int start_i = 0;
    // Do we have previous fibonacci s_num provided ?
    if (previous != NULL && current != NULL && previous != current) {
      // If we have only the previous fibonacci, we need one more compute
      // to take a starting point.
      a = current;
      b = previous;
      // If a previous fibonacci is provided, we consider it as the immediatly 
      // preceding fibonacci number for n
      start_i = n - 1;
    } else {
      // If there is no start s_num provided, 
      // we define A as a s_num number 1 with 1 byte in size.
      a = new_num(1);
      if (a == NULL) return NULL;
      *(a->bytes) = 1;
      // And we define B as a s_num number 0 with 1 byte in size.
      b = new_num(1);
      if (b == NULL) {
        free_num(a);
        return NULL;
      }
    }
    s_num *tmp;
    for (; start_i < n; ++start_i) {
      // We get in tmp a copy of the original A, as it will become B
      tmp = fib(a, b);
      if (tmp == NULL) {
        free_num(a);
        free_num(b);
        return NULL;
      }
      free_num(b);
      b = tmp;
    }
    free_num(b);
    // We return a pointer to A, as it contains our corresponding result.
    // It is here the caller responsibility to free it.
    return a;
}
// We produce the 100 first fibonacci number from 0
int main(int nbargs, char *argc[]) {
    s_num *num = NULL;
    s_num *previous_num = NULL;
    s_num *previous_previous_num = NULL;
    unsigned int limit = 100u;
    if (nbargs > 1 ) {
      limit=(unsigned int)strtol(argc[1], NULL, 10u);
    }
    for (unsigned int i = 0u; i < limit; ++i) {
        printf("%uth fib: ", i);
        num = nth(i, previous_num, previous_previous_num);
        if (num != NULL) display_num(num);
        // No need to free num here, as we will reuse it for the next iteration,
        // then it will be the next nth call that will free num.
        // We have only then to free it if we leave the loop.
        previous_previous_num = previous_num ;
        previous_num = num;
    }
    if (num != NULL) free_num(num);
    // Here, as we are out of the loop, we are freeing "previous" as 
    // "previous_previous_num" received it from the last iteration.
    if (previous_previous_num != NULL  && previous_previous_num != num) free_num(previous_previous_num);
    // No more required for actual ANSI C
    // return 0;
}

Extract of the output for N = 10000 :

0th fib: 1
1th fib: 1
2th fib: 2
3th fib: 3
4th fib: 5
5th fib: 8
6th fib: 13
7th fib: 21
8th fib: 34
9th fib: 55
10th fib: 89
11th fib: 144
12th fib: 233
13th fib: 377
..
90th fib: 4660046610375530309
91th fib: 7540113804746346429
92th fib: 12200160415121876738
93th fib:  => 0x0111F38AD0840BF6BF
94th fib:  => 0x01BB433812A62B1DC1
95th fib:  => 0x02CD36C2E32A371480
96th fib:  => 0x048879FAF5D0623241
97th fib:  => 0x0755B0BDD8FA9946C1
..

9999th fib:  => 0x26455354C816C43235B9A5B9708A80EC209E5A36521B054E1F08B364AC5F9EA8A618BA6203D6598679F82A57B25E5727326C1BEC42026ED6BB5E577D20563519B1086FA78E79A13DF45829FA84BFD0AB6F0B2DBEB34CDD8BE556F2BA12DC96342BC50CD1C313479C2C83AFDFDD28C1F9FCFF8EE23EEEE443349BA0964E0AA29F35941217D12487CECACDC9CCC9B77D11D14F72BCCC265FD0FE7F831747EBE7634B9A246915F996315C79DE01E48EFA8A52CAAE6BE757783411BE20664AB19D18CC63AF13E623895D5C879D5F3B1D5768317FBF95DC91FBF8402131015E5F5154F3B14DCFDA6C3E88BABEE1BA117394C9EE4360096BDF6650209D8005BCC5E2459072F8066895C7331F271051F2830EDDCC8A0102DF15711544823B820D863EC63AB8ED88A777D4C7CFED7563DAB155C06D057C0BACB621E2D50B7A655E647EA443C8555005BB5D7066096A2E811D53571E24181DFE37FF0979AF3B063B133BDC511FE7FC3E71C74D2529F1E6C218F213EECF09A09194857B1130A3E8DFD9CF3B38E6A18A68103C4698D3E014DC8D6D59EC1C6D2478BD16E42A20FBCB81B03C86470AFE986FE20AD2C54706CD01D198BCC78BF5A0B0C6FA15C2585647635F965925246AF87C8D05CC0F072355F3D31867944AEF1C0AD65B32DA8121EBBC36AC1A3554BEE17AB8E680DB4C6F305AE9836CA2B8BEEB64D2B1BD5F6B801139AEB8298BF53AE4EEA0B4237965F95C6CBC92F5BE3427CBD0B2E8771C54B578032F865CD74E66CB093D51B51F808308B71FCAFE88250528A3F5D1E308A1A9CE9872547FA5ACC2CF434B9503B368066143606EA5458B0B9ED1538A465EAA4638A340B8AB274AAAC060A56F2D2FA639B7A8CBF00ADAD2286AB2B299C9ADF471647736E8B97B5A6F8781CF0707617BE5570BB649C47E122F6D4781BF97BC02BFBDF59D558820DF190348081A3028FA2F3EFBF486D2F69AEB5C8FB963F27BF01300F047E4989C9CAD353A1EE19AA20752F5789EA65AAEFC62DD5F836456C17B08B5194C682118570AEBDFECD446A1F63AE261A299C23C6AB19E7B2758E4FE91D35D8FE1D5DFF7359FB73A5DEDB172765B205628AC2DCF0DE6865874CCC0CB5369623FB3E96F09A07D07F4753F50034CCACE3542ED83D69BBD346E43A1D4BF5C229A116B35F9F98E4C8752CA26035035F30F7DB929B9C06FA898222219DEE5079FAAD824476D4A0819DB

@SteveSummit You're right. Sometime i fall to old habits. Edit done, thanks. — Zilog80, Jun 23 '21 at 14:05

Type declaration problem in C (fibonacci numbers)

2 Answers2

Linked