print fibo big numbers in c++ or c language

Question

I write this code for show fibonacci series using recursion.But It not show correctly for n>43 (ex: for n=100 show:-980107325).

#include<stdio.h>
#include<conio.h>

void fibonacciSeries(int);

void fibonacciSeries(int n)
{
static long d = 0, e = 1;
long c;
if (n>1)
{
    c = d + e;
    d = e;
    e = c;
    printf("%d \n", c);
    fibonacciSeries(n - 1);
}
}

int main()
{
long a, n;
long long i = 0, j = 1, f;
printf("How many number you want to print in the fibonnaci series :\n");
scanf("%d", &n);

printf("\nFibonacci Series: ");
printf("%d", 0);
fibonacciSeries(n);
_getch();
return 0;
}

Answer 1

The value of fib(100) is so large that it will overflow even a 64 bit number. To operate on such large values, you need to do arbitrary-precision arithmetic. Arbitrary-precision arithmetic is not provided by C nor C++ standard libraries, so you'll need to either implement it yourself or use a library written by someone else.

For smaller values that do fit your long long, your problem is that you use the wrong printf format specifier. To print a long long, you need to use %lld.

Answer 2

Code overflows the range of the integer used long.
Could use long long, but even that may not handle Fib(100) which needs at least 69 bits.

Code could use long double if 1.0/LDBL_EPSILON > 3.6e20

Various libraries exist to handle very large integers.

For this task, all that is needed is a way to add two large integers. Consider using a string. An inefficient but simply string addition follows. No contingencies for buffer overflow.

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

char *str_revese_inplace(char *s) {
  char *left = s;
  char *right = s + strlen(s);
  while (right > left) {
    right--;
    char t = *right;
    *right = *left;
    *left = t;
    left++;
  }
  return s;
}

char *str_add(char *ssum, const char *sa, const char *sb) {
  const char *pa = sa + strlen(sa);
  const char *pb = sb + strlen(sb);
  char *psum = ssum;
  int carry = 0;
  while (pa > sa || pb > sb || carry) {
    int sum = carry;
    if (pa > sa) sum += *(--pa) - '0';
    if (pb > sb) sum += *(--pb) - '0';
    *psum++ = sum % 10 + '0';
    carry = sum / 10;
  }
  *psum = '\0';
  return str_revese_inplace(ssum);
}

int main(void) {
  char fib[3][300];
  strcpy(fib[0], "0");
  strcpy(fib[1], "1");
  int i;
  for (i = 2; i <= 1000; i++) {
    printf("Fib(%3d) %s.\n", i, str_add(fib[2], fib[1], fib[0]));
    strcpy(fib[0], fib[1]);
    strcpy(fib[1], fib[2]);
  }
  return 0;
}

Output

Fib(  2) 1.
Fib(  3) 2.
Fib(  4) 3.
Fib(  5) 5.
Fib(  6) 8.
...
Fib(100) 3542248xxxxxxxxxx5075.  // Some xx left in for a bit of mystery.

Fib(1000) --> 43466...about 200 more digits...8875

Answer 3

Well, you could want to try implementing BigInt in C++ or C.

Useful Material:

• How to implement big int in C++

Answer 4

For this purporse you need implement BigInteger. There is no such build-in support in current c++. You can view few advises on stack overflow

Or you also can use some libs like GMP

Also here is some implementation:

1. E-maxx - on Russian language description.

2. Or find some open implementation on GitHub

Answer 5

Try to use a different format and printf, use unsigned to get wider range of digits.

If you use unsigned long long you should get until 18 446 744 073 709 551 615 so until the 93th number for fibonacci serie 12200160415121876738 but after this one you will get incorrect result because the 94th number 19740274219868223167 is too big for unsigned long long.

Answer 6

Keep in mind that the n-th fibonacci number is (approximately) ((1 + sqrt(5))/2)^n.

This allows you to get the value for n that allows the result to fit in 32 /64 unsigned integers. For signed remember that you lose one bit.

Answer 7

You can print some large Fibonacci numbers using only char, int and <stdio.h> in C.

There is some headers :

#include <stdio.h>
#define B_SIZE 10000 // max number of digits
typedef int positive_number;

struct buffer {
    size_t index;
    char data[B_SIZE];
};

Also some functions :

void init_buffer(struct buffer *buffer, positive_number n) {
    for (buffer->index = B_SIZE; n; buffer->data[--buffer->index] = (char) (n % 10), n /= 10);
}

void print_buffer(const struct buffer *buffer) {
    for (size_t i = buffer->index; i < B_SIZE; ++i) putchar('0' + buffer->data[i]);
}

void fly_add_buffer(struct buffer *buffer, const struct buffer *client) {
    positive_number a = 0;
    size_t i = (B_SIZE - 1);
    for (; i >= client->index; --i) {
        buffer->data[i] = (char) (buffer->data[i] + client->data[i] + a);
        buffer->data[i] = (char) (buffer->data[i] - (a = buffer->data[i] > 9) * 10);
    }
    for (; a; buffer->data[i] = (char) (buffer->data[i] + a), a = buffer->data[i] > 9, buffer->data[i] = (char) (buffer->data[i] - a * 10), --i);
    if (++i < buffer->index) buffer->index = i;
}

Example usage :

int main() {
    struct buffer number_1, number_2, number_3;
    init_buffer(&number_1, 0);
    init_buffer(&number_2, 1);
    for (int i = 0; i < 2500; ++i) {
        number_3 = number_1;
        fly_add_buffer(&number_1, &number_2);
        number_2 = number_3;
    }
    print_buffer(&number_1);
}

// print 131709051675194962952276308712 ... 935714056959634778700594751875

Best C type is still char ? The given code is printing f(2500), a 523 digits number.

Info : f(2e5) has 41,798 digits, see also Factorial(10000) and Fibonacci(1000000).