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.