Fibonacci function with big number (i.e. 1000 digits) in C

Question

EDIT: I replace: carry = (x-(x%10))%10; by: carry = x/10;

And I add at the end of the while loop in addition(): if(carry) f3[i] = carry;

Thanks to FalconUSA & M_Oehm ! :)

I'm working on problem 25 of Project Euler (beware spoilers), and while the fibonacci function isn't really a problem I've difficulties to implement a way to store huge number (like there a 1000 digits).

So i've tried (as i learnt on the web) to deal with it with array, but the program is running indefinitely. My problem is probably in addition() or length().

Any ideas about it ?

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

int length(int *nbr) // number of digits of my number
{
    int len = 0, c = 0;

    while(nbr[c] >= 0) {
        len++;
        c++;
    }
    return len;
}

int addition(int *f1, int *f2, int *f3, int siz) // add f1+f2 and store it in f3
{
    int carry =0, i =0;
    int x;

    memset ( f3, -1, siz*sizeof(int));

    while ( (f1[i] >= 0) || (f2[i] >= 0) ) {
        if(f1[i]<0) {
            x = f2[i] + carry;
        }
        else if(f2[i]<0) {
            x = f1[i] + carry;
        }
        else {
            x = f1[i] + f2[i] + carry;
        }
        f3[i] = x%10;
        carry = (x-(x%10))%10;
        i++;
    }

    return 0;
}

int copy_arr(int *dest, int *or, int siz) //copy array "or" into "dest"
{
    int c = 0;
    memset( dest, -1, siz*sizeof(int));

    while( c < siz ) {
        dest[c] = or[c];
        c++;
    }

    return 0;
}

int fibo(int siz) //fibonacci function
{
    int f1[siz],f2[siz],f3[siz];
    memset( f1, -1, siz*sizeof(int));
    memset( f2, -1, siz*sizeof(int));
    memset( f3, -1, siz*sizeof(int));

    int n = 2;

    f1[0] = f2[0] = 1;


    while (length(f1) <= siz) {
        n++;
        addition( f1, f2, f3, siz);
        copy_arr( f2, f1, siz);
        copy_arr( f1, f3, siz);
    }

    printf("%d\n", n);

    return 0;
}


int main() // siz's value is the number of digits I desire for my fibonacci number
{
    int siz=1000;

    fibo(siz);

    return 0;
}

Answer 1

Well, seems like your problem is in this line:

carry = (x - x%10) % 10;

it should be just

carry = x - x%10;

or

carry = x / 10;

which is equivalend in this case.

UPDATE: also, in line

 while ( (f1[i] >= 0) || (f2[i] >= 0) ) {

if the size of f1 is siz and the size of f2 is also siz, then you'll reach the element f1[siz], or even further, which is out of range. So, you should declaring

int f1[siz+1], f2[siz+1], f3[siz+1]

and you should setting siz+1 edges everywhere:

memset( fi, -1, (siz+1)*sizeof(int)); // where 1 <= i <= 3

PS: if you only want to calculate that fibonacci number without integrating into some program that requires fast calculation, it's better to use Python or Java, because these languages have built-in long numbers support and their syntax are very easy and similar to C++. And, as ghostmansd mentioned above, it's better to use GMP library if you're going to use C/C++ anyways.