CODEWITHSUNDEEP
c
Varun Srivastava
Varun Srivastava

Reputation: 45

I get incorrect values when printing Fibonacci numbers from the 93rd value upwards

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int fibonacciSum(int n);

int main(void) {
    int n = 0;
    scanf("%d", &n);
    printf("%d", fibonacciSum(n));
}

int fibonacciSum(int n) {
    if (n <= 1)
        return n;
    uintmax_t previous = 0;
    uintmax_t current  = 1;
    for (int i = 0; i < n - 1; i++) {
         printf("%ju and i %d\n", current, i);    
         uintmax_t tmp_previous = previous;
         previous = current;
         current = tmp_previous + current;
    }
    return current % 10;
}

This program calculates nth Fibonacci number and also the last digit of nth Fibonacci number. In my case, as I'm getting wrong values after the 92nd element, so the last digit is also coming out wrong. I'm using the jdoodle online application to compile my C program. What's going wrong?

Upvotes: 0

Views: 176

Answers (2)

chqrlie
chqrlie

Reputation: 144740

If you are only interested in the last digit of the Fibonacci numbers, do the computations modulo 10:

#include <stdio.h>

int fibonacciSum(int n);

int main(void) {
    int n = 0;
    if (scanf("%d", &n) == 1) {
        printf("%d\n", fibonacciSum(n));
    }
    return 0;
}

int fibonacciSum(int n) {
    if (n <= 1)
        return n;
    int previous = 0;
    int current  = 1;
    for (int i = 1; i < n; i++) {
         printf("fib(%d) % 10 = %d\n", i, current);
         int tmp_previous = previous;
         previous = current;
         current = (tmp_previous + current) % 10;
    }
    return current;
}

If you also want the complete numbers, you should use a multiprecision package (also called bignum) as Fibonacci numbers exceed 64 bits from the 93rd on.

You could write a simplistic one to handle addition of positive numbers only, stored as allocated strings of decimal digits. An interesting challenge for the next 24 hours, I shall post a simple program here then.

Upvotes: 2

iBug
iBug

Reputation: 37227

It looks like there's an integer overflow in the case.

As Steve Summit suggested in comments,

fib[93] = 12,200,160,415,121,876,738 = 64 bits
max_uint64 = 18,446,744,073,709,551,615

So it's sure that fib[94] will cause an int overflow because it's larger than 264.

You can use arbitrary-precision arithmetics if you want a super big number.

Upvotes: 0

Related Questions