Thread: Help troubleshooting

I posted this previously, but I had not included the test cases along with all other functions with it. Below is the full program. I know I am getting incorrect data or crashes with hugeAdd, and toUnsignedInt, but I am unsure how to fix. Someone had previously suggested a possible fix to hugeAdd, but I didn't understand what they were suggesting or how to implement.

I have not had a chance to test fib yet, but it impliments hugeAdd, so I wont be able to test that until I can fix hugeAdd.

Any advice on any of these functions, or anything you notice that I could improve upon would be greatly appreciated. Thank you.

Here is the prototype for all functions and structures:

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

Here is the beginning of my code:

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;

a = malloc(sizeof(HugeInteger));
trim = malloc(sizeof(HugeInteger));
//check if malloc was successful
if(a == NULL){
    printf("\n23: Malloc failed\n");
    return NULL;
}
a->digits = NULL;
//if p is bigger than q
if (p->length > q->length){
    a->digits = calloc(p->length+1, sizeof(int));
    a->length = p->length;
    //check to make sure calloc was successful
    if(a->digits == NULL){
        printf("\n34: Calloc failed\n");
        a->length = 0;
        free(a);
        return NULL;
    }
    //to find where the error occurs with the addition
    printf("\np contains the elements: \t\t\t");
    for(i=0; i<p->length; i++)
        printf("%d",p->digits[i]);
    printf("\nq contains the elements: \t\t\t");
    for(i=0; i<q->length; i++)
        printf("%d", q->digits[i]);

    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] += (p->digits[i]+q->digits[i])-10;
            a->digits[i+1] = 1;
        }
        else{
            a->digits[i] += p->digits[i]+q->digits[i];
        }
    }
}
//if q is bigger than p
else{

    a->digits = calloc(q->length+1, sizeof(int));
    a->length = q->length;
    //check to make sure calloc was successful
    if(a->digits == NULL){
        printf("\n62: Calloc Failed\n");
        a->length = 0;
        free(a);
        return NULL;
    }
    for (i=0; i<p->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] += (p->digits[i]+q->digits[i])-10;
            a->digits[i+1] += 1;
        }
        else{
            a->digits[i] += p->digits[i]+q->digits[i];
        }
    }
}
//if there is a hanging 0 at the end
    if (a->digits[a->length] == 0)
    {
        trim->digits = malloc(sizeof(a->length-1));
        if(trim->digits == NULL)
        {
            printf("\ntrim malloc failed");
            free(trim);
            return NULL;
        }
        //transfer digits over to new struct
        for (i=0; i<a->length-1; i++)
        {
            trim->digits[i] = a->digits[i];
        }
        trim->length = a->length-1;
        /*  Dont know why I have this
        for(i=0; i<trim->length; i++)
        {
            trim->digits[i]=a->digits[i];
            free(a->digits);
            free(a);
        }
        */
    printf("\nHere is the result of the Addition function (still in reverse):\t");
//to determine where the error is occurring
    for (i=0; i<trim->length; i++)
        printf("%d", trim->digits[i]);
    return trim;
    }
return a;
}
//create function for hugeDestroyer
HugeInteger *hugeDestroyer(HugeInteger *p){
//declare variables
int i;
//if fed a NULL pointer
if (p == NULL)
    return NULL;
//free all allocated space for the array & then the structure
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("\nmalloc 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, n=UINT_MAX;
    int i, mod = 1;
    
//dynamically allocate space for the unsigned integer
    a = malloc(sizeof(unsigned int)*1);
//return NULL if we were fed a NULL pointer or if malloc failed
    if (p == NULL)
        return NULL;
    if(a  == NULL)
    {
        printf("/nmalloc failed");
        return NULL;
    }
//convert the number stored in p to an unsigned integer
//(essentially undo what you did in parseInt)
    for(i=p->length; i>=0; i--)
    {
        a[0] = temp + p->digits[i] * mod;
        temp = a[0];
        mod *10;
    }
    
//return NULL if the unsigned integer we created exceeds UINT_MAX
    if (a > n)
    {
        printf("\nThere was an error with the unsigned integer. It is too big.");
        return NULL;
    }
//return a pointer to the unsigned integer
return a;
}
//create a function for fibonacci sequence
HugeInteger *fib(int n){
//Declare variables
    HugeInteger *fibarray = NULL;
    HugeInteger *a = NULL;
    HugeInteger *b = NULL;
    HugeInteger *c = NULL;
    int i;
//dynamically allocate space for each structure
    a = malloc(sizeof(HugeInteger));
    b = malloc(sizeof(HugeInteger));
    c = malloc(sizeof(HugeInteger));
//return NULL if malloc failed
    if (a == NULL)
    {
        printf("\na - malloc failed");
        return NULL;
    }
    if (b == NULL)
    {
        printf("\nb - malloc failed");
        return NULL;
    }
    if (c == NULL)
    {
        printf("\nc - malloc failed");
        return NULL;
    }
//allocate memory for the arrays
    a->digits = malloc(sizeof(int));
    b->digits = malloc(sizeof(int));
//if malloc failed
    if (a->digits == NULL)
    {
        printf("\na->digits malloc failed");
        free(a);
        return NULL;
    }
    if (b->digits == NULL)
    {
        printf("\n250 b->digits malloc failed");
        free(b);
        return NULL;
    }
//in the event that an element of size 1 is asked
    if (n >= 1)
    {
        fibarray->digits[0] = 0;
        fibarray->length = 1;
    }
//otherwise set the base case
    a->digits[0] = 0;
    b->digits[0] = 1;
//the bulk of the fibonacci function, which occurs if n>1
if (n > 1)
{
//o(n) operation
    for (i = 2; i<=n; i++)
        {
            c = hugeAdd(a,b);
            for (i=0; i<b->length; i++)
                a->digits[i] = b->digits[i];
                a->length = b->length;
            for (i=0; i<c->length; i++)
                b->digits[i] = c->digits[i];
                b->length = c->length;
        }
}
    return fibarray;
}

This function is defined in all the test cases, so to save space I'll list it here

Code:

// 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");
}

Here are the test cases:

case 1:

Code:

int main(void)
{
 unsigned int *temp;
 HugeInteger *p;
 hugePrint(p = parseString("12345"));
 printf("%u\n", *(temp = toUnsignedInt(p)));
 free(temp);
 hugeDestroyer(p);
 hugePrint(p = parseString("354913546879519843519843548943513179"));
 temp = toUnsignedInt(p);
 if (temp == NULL)
  printf("Good work.\n");
 else
  printf("Uh oh...\n");
 free(temp);
 hugeDestroyer(p);
 hugePrint(p = parseString(NULL));
 temp = toUnsignedInt(p);
 if (temp == NULL)
  printf("Good work.\n");
 else
  printf("Uh oh...\n");
 free(temp);
 hugeDestroyer(p);
 hugePrint(p = parseInt(246810));
 printf("%u\n", *(temp = toUnsignedInt(p)));
 free(temp);
 hugeDestroyer(p);
 hugePrint(p = parseInt(0));
 printf("%u\n", *(temp = toUnsignedInt(p)));
 free(temp);
 hugeDestroyer(p);
 hugePrint(p = parseInt(INT_MAX));
 printf("%u\n", *(temp = toUnsignedInt(p)));
 free(temp);
 hugeDestroyer(p);
 hugePrint(p = parseInt(UINT_MAX));
 printf("%u\n", *(temp = toUnsignedInt(p)));
 free(temp);
 hugeDestroyer(p);
 return 0;
}

case 2:

Code:

int main(void)
{
 int i;
 HugeInteger *p, *q, *r;
 // calculate INT_MAX + 1
 p = parseInt(INT_MAX);
 q = parseInt(1);
 r = hugeAdd(p, q);
 // demonstrate overflow
 printf("Overflow style:\n%d + %d = %d\n\n", INT_MAX, 1, INT_MAX + 1);
 // print result of INT_MAX + 1 with HugeIntegers
 printf("HugeInteger style:\n");
 hugePrint(p);
 printf(" + ");
 hugePrint(q);
 printf(" = ");
 hugePrint(r);
 printf("\n\n");
printf("\nmade it here!\n");
 // free memory
 hugeDestroyer(p);
 hugeDestroyer(q);
 printf("\nmade it here!\n");
 hugeDestroyer(r);

 // now calculate UINT_MAX + 1
 p = parseInt(UINT_MAX);
 q = parseInt(1);
 r = hugeAdd(p, q);
 // demonstrate overflow
 printf("Overflow style:\n%u + %u = %u\n\n", UINT_MAX, 1, UINT_MAX + 1);
 // print result of UINT_MAX + 1 with HugeIntegers
 printf("HugeInteger style:\n");
 hugePrint(p);
 printf(" + ");
 hugePrint(q);
 printf(" = ");
 hugePrint(r);
 printf("\n");
 // free memory
 hugeDestroyer(p);
 hugeDestroyer(q);
 hugeDestroyer(r);

 return 0;
}

case 3:

Code:

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;
}

Just some kind advice. The more code you dump, the more unlikely it is anybody will help. Narrow down your problem first. If possible, write a minimal and complete (i.e. probably just main() and at most a short function or 2) test case that demonstrates the problem you're having. Describe what you expect should happen and what is actually happening.

Good luck