When I go to run the Fibonacci function ( fib ), it begins to return incorrect calculations towards the higher numbers, but then seems to correct itself for a little bit, but then does it again and ultimately crashes. And the program seems to be crashing at random numbers. Sometimes the it will make it up to F(55), other times it will only get to F(20). Could someone please tell me why this is happening and/or how I could possibly fix this problem?
Also, when I go to run the program on a Linux server, it segfaults, but it doesn't when I just run it on my IDE. Could you please tell me what could be causing this problem as well? Any help would be greatly appreciated.
Note: the function adds two arrays with individual digits together. It does this to allow the program to add numbers that would exceed the boundaries of INT_MAX.
Here is the header file "Fibonacci.h":
Code:#ifndef __FIBONACCI_H #define __FIBONACCI_H typedef struct HugeInteger { // a dynamically allocated array to hold the digits of a huge integer int *digits; // the number of digits in the huge integer (approx. equal to array length) int length; } HugeInteger; // Functional Prototypes HugeInteger *hugeAdd(HugeInteger *p, HugeInteger *q); HugeInteger *hugeDestroyer(HugeInteger *p); HugeInteger *parseString(char *str); HugeInteger *parseInt(unsigned int n); unsigned int *toUnsignedInt(HugeInteger *p); HugeInteger *fib(int n); #endif
And here is the function definitions w/ the main function attached
Code:#include <stdio.h> #include <stdlib.h> #include <limits.h> #include <string.h> #include "Fibonacci.h" //create function for hugeAdd HugeInteger *hugeAdd(HugeInteger *p, HugeInteger *q){ int i; //return NULL if either pointer is NULL if(p == NULL || q == NULL) return NULL; //create a new HugeInteger to store the result in HugeInteger *a = NULL; HugeInteger *trim = NULL; //dynamically allocate the structure a = malloc(sizeof(HugeInteger)); trim = malloc(sizeof(HugeInteger)); //check if malloc was successful if(a == NULL || trim == NULL){ printf("\n23: Malloc failed\n"); return NULL; } //set the arrays to NULL to confirm malloc worked a->digits = NULL; trim->digits = NULL; //if p is bigger than q if (p->length > q->length){ //dynamically allocate the array a->digits = calloc(p->length+1, sizeof(int)); a->length = p->length+1; //check to make sure calloc was successful if(a->digits == NULL){ printf("\nCalloc failed\n"); a->length = 0; free(a); return NULL; } //copy contents of the bigger array into the newly calloc'd array for (i=0; i<p->length; i++) a->digits[i] = p->digits[i]; //add two arrays together for (i=0; i<q->length; i++){ //if sum is >10 do this, since each cell should only hold 0-9 if (p->digits[i]+q->digits[i]>=10){ a->digits[i] += q->digits[i]-10; a->digits[i+1] += 1; } else{ a->digits[i] += q->digits[i]; } } } //if q is bigger than p else{ a->digits = calloc(q->length+1, sizeof(int)); a->length = q->length+1; //check to make sure calloc was successful if(a->digits == NULL){ printf("\nCalloc Failed\n"); a->length = 0; free(a); return NULL; } //copy contents of the bigger array into the newly calloc'd array for (i=0; i<q->length; i++) a->digits[i] = q->digits[i]; //add two arrays together for (i=0; i<p->length; i++){ //if sum is >10 do this, since each cell should only hold 0-9 if (q->digits[i]+p->digits[i]>=10){ a->digits[i] += p->digits[i]-10; a->digits[i+1] += 1; } else{ a->digits[i] += p->digits[i]; } } } //if there is a hanging 0 at the end if (a->digits[a->length-1] == 1) return a; else { trim->digits = malloc(sizeof(int)* (a->length-1)); if(trim->digits == NULL) { printf("\ntrim malloc failed"); free(trim); return NULL; } trim->length = a->length-1; //transfer digits over to new struct for (i=0; i<trim->length; i++) { trim->digits[i] = a->digits[i]; } //clean up after yourself free(a->digits); a->length = 0; free(a); return trim; } } //create function for hugeDestroyer HugeInteger *hugeDestroyer(HugeInteger *p){ int i; if (p == NULL) return NULL; free(p->digits); free(p); //set p to NULL and return NULL p = NULL; return NULL; } //create function for parseString HugeInteger *parseString(char *str){ int i,j, k=0, temp=0; HugeInteger *a = NULL; HugeInteger *tempint = NULL; //check if we were passed a NULL string if (str == NULL) return NULL; //dynamically allocate the HugeIntegers a = malloc(sizeof(HugeInteger)); a->digits = NULL; tempint = malloc(sizeof(HugeInteger)); tempint->digits = NULL; //check if malloc worked if (a == NULL || tempint == NULL){ printf("\nmalloc failed\n"); return NULL; } //dynamically allocate a->digits, and set the length a->digits = malloc(sizeof(int)*(strlen(str))); a->length = strlen(str); //since tempint will store the same numbers as a in reverse later on, dynamically //allocate it the same way tempint->digits = malloc(sizeof(int)*(strlen(str))); tempint->length = strlen(str); //check if malloc worked if(a->digits == NULL){ printf("\nMalloc failed\n"); a->length = 0; free(a); return NULL; } //if "" is passed to function if(str == '\0'){ a->digits[0] = 0; a->length = 1; return a; } //copy the numbers stored in str into the array in a for(i=0; i<strlen(str); i++) a->digits[i] = str[i] - '0'; for(i=strlen(str)-1, j=0; i>=0; i--, j++) { tempint->digits[j] = a->digits[i]; } for(i=0; i<strlen(str); i++) a->digits[i] = tempint->digits[i]; //return a pointer to a return a; } //create function for parseInt HugeInteger *parseInt(unsigned int n){ //declare variables HugeInteger *a = NULL; int mod = 10, counter=0, secondmod=1, i; unsigned int temp = n; a = malloc(sizeof(HugeInteger)); //check to see if mallco failed if (a == NULL) { printf("\n174 malloc failed\n"); return NULL; } //in the case of n being 0 if (n == 0) { a->digits = NULL; a->digits = calloc(1, sizeof(int)); //check if malloc succeeded if (a->digits == NULL) return NULL; a->digits[0] = 0; a->length = 1; return a; } //determine how much digits make up the unsigned number while(temp>0) { temp/=10; counter++; } //check to see if malloc failed a->digits = NULL; a->digits = malloc(sizeof(int)*counter); if (a->digits == NULL) { printf("\nmalloc failed"); free(a); return NULL; } //set the a->length originally to 0 a->length = counter; //store every individual digit of the large number into a slot in the array for (i=0; i<a->length; i++) { a->digits[i] = (n % mod)/secondmod; mod*=10; secondmod*=10; } if (n == INT_MAX) a->digits[a->length-1] = 2; if (n == UINT_MAX) a->digits[a->length-1] = 4; return a; } //create function for toUnsignedInt unsigned int *toUnsignedInt(HugeInteger *p){ //declare variables unsigned int *a=NULL, temp=0, currentuint=0, prevuint=0, n=UINT_MAX; int i, mod = 1; //return NULL if we were fed a NULL pointer or if malloc failed if (p == NULL) return NULL; if(a == NULL) { printf("/ncalloc failed"); return NULL; } temp = 0; //convert the number stored in p to an unsigned integer //(essentially undo what you did in parseInt) for(i=0; i<p->length; i++) { temp = temp + p->digits[i] * mod; mod *= 10; if (temp < prevuint) return NULL; prevuint = temp; } a = &temp; //return NULL if the unsigned integer we created exceeds UINT_MAX //return a pointer to the unsigned integer return a; } //create a function for fibonacci sequence HugeInteger *fib(int n){ //Declare variables HugeInteger *a = NULL; HugeInteger *b = NULL; HugeInteger *c = NULL; int i,j,k; //allocate memory for the structure a = malloc(sizeof(HugeInteger)); b = malloc(sizeof(HugeInteger)); c = malloc(sizeof(HugeInteger)); //check if malloc worked if (a == NULL || b == NULL) { printf("\nmalloc failed\n"); return NULL; } //initialize the array pointer to NULL a->digits = NULL; b->digits = NULL; c->digits = NULL; //dynamically allocate memory for the arrays a->digits = malloc(sizeof(int)); b->digits = malloc(sizeof(int)); c->digits = malloc(sizeof(int)); //if a's malloc failed if (a->digits == NULL) { printf("\nmalloc failed"); free(a); return NULL; } //if b's malloc failed if (b->digits == NULL) { printf("\nmalloc failed"); free(b); //since it passed the first if statement, we have to free a too free(a->digits); free(a); return NULL; } //if c's malloc failed if (c->digits == NULL) { printf("\nmalloc failed"); free(c); free(b->digits); free(b); free(a->digits); free(a); return NULL; } //set length a->length = 1; b->length = 1; //set the base case a->digits[0] = 1; b->digits[0] = 0; //the bulk of the fibonacci function, which occurs if n>0 if (n > 0) { //order n operation for (i = 1; i<=n; i++) { //add the two previous (or base cases) together. c = a+b c = hugeAdd(a,b); //a = b for (j=0; j<b->length; j++) a->digits[j] = b->digits[j]; a->length = b->length; //b = c for (j=0; j<c->length; j++) b->digits[j] = c->digits[j]; b->length = c->length; } } return b; } // print a HugeInteger (followed by a newline character) void hugePrint(HugeInteger *p) { int i; if (p == NULL || p->digits == NULL) { printf("(null pointer)\n"); return; } for (i = p->length - 1; i >= 0; i--) printf("%d", p->digits[i]); printf("\n"); } int main(void) { int i; HugeInteger *p; for (i = 0; i <= 1000; i++) { printf("F(%d) = ", i); hugePrint(p = fib(i)); hugeDestroyer(p); } return 0; }
Originally Posted by Elkvis
