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