Fibonacci Series

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

/*

1000th Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1

F2 = 1

F3 = 2

F4 = 3

F5 = 5

F6 = 8

F7 = 13

F8 = 21

F9 = 34

F10 = 55

F11 = 89

F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

*/

// The answer is 4782

int *long_addition(int *addition_dgtslist[],int addition_dgtscount[],int list_count, int *rslt_dgtcount);

int *number_to_digit(int *n, int *digit_count);

int split_lastDigit(int the_num,int *carryover);

int *add_to_list(int *the_list,int the_value,int *list_count);

void print_fibonacci(int *f,int dg_count); // works only for this project

void print_digits(int *digits,int *digit_count);

int main()

{

    // Long addition technique

    int *fibonacci_n[2];

    int fibonacci_dgcount[2];

    // Store F1 = 1 and F2 = 1

    int f1_2 = 1; // f1 & f2

    fibonacci_n[0] = number_to_digit(&f1_2,&fibonacci_dgcount[0]); // 1 is saved as list digits which is 1 in list

    fibonacci_n[1] = number_to_digit(&f1_2,&fibonacci_dgcount[1]); // 1 is saved as list digits which is 1 in list

    // Print first 50(say) Fibonacci numbers to check

//    int i=1;

//    printf("%d\t",i);

//    print_digits(fibonacci_n[0],&fibonacci_dgcount[0]);

//    i=2;

//    printf("%d\t",i);

//    print_digits(fibonacci_n[1],&fibonacci_dgcount[1]);

//

//    for(i=3;i<51;i++)

//    {

//        int result_dgcount;

//        int *result_fn =  long_addition(fibonacci_n,fibonacci_dgcount,2,&result_dgcount);

//        printf("%d\t",i);

//        print_digits(result_fn,&result_dgcount);

//

//        store fn in a temp variables

//        int *temp_dg  = fibonacci_n[1];

//        int temp1_dgcount = fibonacci_dgcount[1];

//

//         change fn from the result calculated

//        fibonacci_n[1] = result_fn;

//        fibonacci_dgcount[1] = result_dgcount;

//

//         change fn-1 from the stored temp variables

//        fibonacci_n[0] = temp_dg;

//        fibonacci_dgcount[0] = temp1_dgcount;

//

//    }

    // Print the first 1000 digit Fibonacci number

    int index = 3;

    do

    {

        int result_dgcount;

        int *result_fn =  long_addition(fibonacci_n,fibonacci_dgcount,2,&result_dgcount);

        if(result_dgcount==1000)

        {

            printf("%d\t",index);

            print_digits(result_fn,&result_dgcount);

            break;

        }

        index++;

        //store fn in a temp variables

        int *temp_dg  = fibonacci_n[1];

        int temp1_dgcount = fibonacci_dgcount[1];

        //change fn from the result calculated

        fibonacci_n[1] = result_fn;

        fibonacci_dgcount[1] = result_dgcount;

        //change fn-1 from the stored temp variables

        fibonacci_n[0] = temp_dg;

        fibonacci_dgcount[0] = temp1_dgcount;

    }while(1==1); // infinite loop until condition is met and break is triggered

    return 0;

}

void print_digits(int *digits,int *digit_count)

{

    int m;

    for(m=(*digit_count);m>0;m--)

        printf("%d",(*(digits+(m-1))));

    printf("\n");

}

int *long_addition(int *addition_dgtslist[],int addition_dgtscount[],int list_count, int *rslt_dgtcount)

{

    int i,j;

    // Find the maximum number of digits list

    // Idea is to fill zeroes for shorter numbers (numbers with less digits)

    int max_list_count = 0;

    for(i=0;i<list_count;i++)

    {

        if(max_list_count<addition_dgtscount[i])

        {

            max_list_count = addition_dgtscount[i];

        }

    }

    // Fill zeroes for shorter numbers

    for(i=0;i<list_count;i++)

    {

        for(j=addition_dgtscount[i];j<max_list_count;j++)

        {

            addition_dgtslist[i]=add_to_list(addition_dgtslist[i],0, &addition_dgtscount[i]);

        }

    }

    int *addition_result;

    (*rslt_dgtcount)=0;

    int carry_over = 0;

    int total_sum;

    for(j=0; j<max_list_count ;j++)

    {

        total_sum = carry_over;

        for(i=0;i<(list_count);i++)

        {

            total_sum = total_sum + (*(*(addition_dgtslist+i)+j)) ;

            //printf("%d",*(*(addition_dgtslist+i)+j));

        }

        addition_result=add_to_list(addition_result,split_lastDigit(total_sum,&carry_over),rslt_dgtcount);

    }

    // To add carry Over digits to the list

    int temp_carryover = carry_over;

    if(carry_over!=0)

    {

        addition_result=add_to_list(addition_result,split_lastDigit(temp_carryover,&carry_over),rslt_dgtcount);

        temp_carryover = carry_over;

    }

    return addition_result;

}

int split_lastDigit(int the_num,int *carryover)

{

    *(carryover) = (int)(the_num/10);

    return (the_num - (*(carryover)*10));

}

int *number_to_digit(int *n, int *digit_count)

{

    int numP,numC = *(n);

    int *digits = (int *)malloc(1*sizeof(int)); //Initially we allocate 1 space to digit list

    *(digit_count) = 0;// set digit_count = 0

    while(numC!=0)

    {

        numP = numC; //Set the numP value as numC then remove the last digit of numC

        //numC = numC/10

        numC=floor(numC/10);

        *(digits+(*(digit_count))) =(int)(numP - (numC*10)); //

        (*(digit_count))=(*(digit_count))+1;//Update the digit count

        int *temp=(int *)realloc(digits,(*(digit_count)+1)*sizeof(int)); // give the pointer some (+1 int) memory each time

        if (temp != NULL )

        {

            digits=temp; //Memory added here

        }

        else

        {

            printf("Error Allocating Memory");

        }

    }

    return digits;// return the digits address and the digit_count is already updated

}

int *add_to_list(int *the_list,int the_value,int *list_count)

{

    if((*list_count)==0)// There is no item in the list

    {

        the_list = (int *)malloc(1*sizeof(int)); // We initialize 1 space to the list

    }

    else

    {

        int *temp = (int *)realloc(the_list,(*(list_count)+1)*sizeof(int)); // Allocate one extra space

        if(temp != NULL)

        {

            the_list = temp;

        }

        else

        {

            printf("Error Allocating Memory");

        }

    }

    *(the_list+(*(list_count))) = the_value; // Adding the value here

    *(list_count) =(*(list_count))+1; // Increment the list count after addition

    return the_list; // return the list address

}