Thread: Need help troubleshooting functions

My program uses a huge integer structure, that saves all the elements of a integer too big to be expressed in 32-bit integers, and stores each digit in a spot in an array.

Here is the HugeInteger Prototype:

Code:

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;

I have been writing 2 functions that implement this, that have caused me quite a bit of trouble.

First, I have a function that adds two very large integers together, by putting them into reverse order and adding them together. An example of this would be

12345+1

[5][4][3][2][1]
+[1]
_____________
[6][4][3][2][1]

so that when it is flipped back to normal again, it is 12346.

In my program however, when I run this function, it returns a completely incorrect answer and I cannot figure out how to fix it. Here is my code:

Code:

//create function for hugeAdd
HugeInteger *hugeAdd(HugeInteger *p, HugeInteger *q){
//declare variables
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;
//dynamically allocate structure
a = malloc(sizeof(HugeInteger));
//check if malloc was successful
if(a == NULL){
    printf("\n23: Malloc failed\n");
    return NULL;
}
//set array to NULL
a->digits = NULL;
   
//if p is bigger than q
if (p->length > q->length){
    //dynamically allocate array & set 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;
    }
//store the result of the addition of the 2 huge integers in the new array
    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;
            //carry a one over to the next space in the array
            a->digits[i+1] = 1;
        }
        //if the result of the two being added, is less than 10, store the result in a
            a->digits[i] += (p->digits[i]+q->digits[i]);
    }
}
//if q is bigger than p
else{
 
    //dynamically allocate the array & set length
    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;
    }
  
  //store result of the addition of the two huge integers in the new array
    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;
            //carry the one over 
            a->digits[i+1] += 1;
        }
        else{
            //if the sum is less than 10
            a->digits[i] += p->digits[i]+q->digits[i];
        }
    }
}
return a;
}

The only other function that is causing me problems is a function that takes a string of numbers and stores them into an array of integers, with one digit per cell, stored in reverse order (this is one of thw ways I can get the two HugeInts listed above, with the other being directly declaring everything, which I did to test).
This is another function I keep on receiving garbage values on, and I cant seem to find the problem.

Code:

//create function for parseString
HugeInteger *parseString(char *str){
int i, k=0, temp=0;
HugeInteger *a = NULL;
//let user know what step we are on
    printf("\nstarted parseString\n");
    printf("\nthe string should be %s", str);
    
//check if we were passed a NULL string
if (str == NULL)
    return NULL;
//dynamically allocate the HugeInteger a
a = malloc(sizeof(HugeInteger));
a->digits = NULL;
//check if malloc worked
if (a == 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);
//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;
    printf("\nThe parsed string was empty and just contains \t\t%d", a->digits[0]);
    return a;
}
//let user know whats happening in the function
printf("\nthe string made it past the empty checkpoint");
//copy the numbers stored in str into the array in a
for(i=0; i<strlen(str); i++)
{
    a->digits[i] = str[i];
}
//return a pointer to a
return a;
}

Any help would be greatly appreciated. I've been at this for a while now, and I feel like I might be missing something incredibly simple that's causing these errors. Please let me know if you found where I went wrong. Thank you

Note: in the parsestring function, the end result hadn't been switched yet, but I saw that it was giving an incorrect solution, so I wanted to take care of that before I moved on.

It would make our task of helping you much easier if you could post a complete, compileable program, along with sample input that demonstrates the problem.

Also, you should not have written hugeAdd until parseString was finished and bug-free. If you can't parse in input correctly, then you have no guarantee that you can add two number correctly. Garbage in, garbage out as they say. Use a debugger, or a printHuge function to verify that you correctly parse it. Start with a plan -- data structures, algorithms, flow charts, etc, all with paper and pencil. Then translate to pseudo code first, then code. Work in smaller chunks, and test very thoroughly, before you move onto the next function.

In parse:

Code:

a = malloc(sizeof(HugeInteger));
a->digits = NULL;
//check if malloc worked
if (a == NULL){
    printf("\nmalloc failed\n");
    return NULL;
}

You do a good job of checking for NULL everywhere, but you're doing some things out of order. What happens if malloc returns NULL? The very next line of code tries to access a->digits, which would dereference a null pointer.

Also, in parse:

Code:

a->digits[i] = str[i];

str contains characters like '1', '4', '7'. Those do not have numeric values of 1, 4 and 7 respectively (look at, e.g. an ASCII chart). You need to do something like

Code:

a->digits[i] = str[i] - '0';

which will turn the character into it's corresponding number.

In hugeAdd, the "p bigger than q" and "q bigger than p" sections are virtually identical. Repeated code means twice as many opportunities to make bugs and twice as much code to debug/maintain. You should have one bit to allocate the right size stuff for a (hint, it may be longer than either addend if the sum of the most significant digits has a carry out), and one loop to add the digits (you can use if statements to decide whether you're actually adding a digit from p or q, or ignoring/adding in a 0 from that operand).