Big Integer Multiplication assignment #1 (cop3502)

// Chris Orem
// 5/29/12
// Solution to COP 3502 (Computer Science I)
// Assignment #1: BigInteger multiplication

// Edited by Arup Guha on 1/21/09 to read from a file.
// Edited by Arup Guha on 5/17/2012 to conform to Summer 2012 Assignment Scaffold 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define MAX 10001

struct integer {
 int* digits;
 int size;
};

struct integer* add(struct integer* one, struct integer *two);
void print(struct integer* number);
void print_op(struct integer* op1, struct integer* op2,struct integer* answer,char op);
struct integer* convert_integer(char* word);
void free_struct(struct integer* thisint);
struct integer* multiply(struct integer *p, struct integer *q);


int main() {

    FILE* ifp = fopen("bigint.txt", "r");

    int loop, numcases;
    fscanf(ifp, "%d", &numcases);

    // Go through each case.
    for (loop=1; loop<=numcases; loop++) {

        // Read in both operands.
        char op1[MAX];
        char op2[MAX];
        fscanf(ifp, "%s%s", op1, op2);

        // Convert and compute.
        struct integer* first = convert_integer(op1);
        struct integer* second = convert_integer(op2);
        struct integer* ans = multiply(first, second);

        // Print the output.
        printf("Problem #%d: ", loop);
        print_op(first, second, ans, '*');
        printf("\n");

        // After we output, we don't need these any more.
        free_struct(first);
        free_struct(second);
        free_struct(ans);
    }

    return 0;
}

//Preconditions: p and q are pointers to struct integers.
//Postconditions: A new struct integer is created that
//                stores the product of the integers
//                pointed to by p and q and a pointer to it
//                is returned.
struct integer* multiply(struct integer *p, struct integer *q){

    //create and allocate space for our answer
    struct integer *ans = (struct integer *)malloc(sizeof(struct integer));
    ans->size = 1;
    ans->digits = (int*)(calloc(ans->size,sizeof(int)));

    //if either integer is 0 return integer 0
    if((p->size==1 && p->digits[0]==0)||(q->size==1 && q->digits[0]==0))
        return ans;
    //create and allocate initial space for first line of multiplication
    struct integer *one = (struct integer *)malloc(sizeof(struct integer));
    one->size=1;
    one->digits = (int*)(calloc(one->size,sizeof(int)));


    int i,j;
    //loop through each digit of p and q
    for(i=0;isize;i++){

        int k;
        //copy ans to a new struct and free it; add(one,ans) will create memory leak
        struct integer *two = ans;

        one->size = p->size+i;
        one->digits = (int *)realloc(one->digits, sizeof(int)*one->size);

        for(k=0;k<=i;k++)
            one->digits[k]=0; //set i spaces to 0

        for(j=0;jsize;j++){
            one->digits[i+j]=p->digits[j]*q->digits[i]; //start i spaces over
        }

        ans = add(one,two);
        free_struct(two);
    }
    free_struct(one);
    return ans;
}


// Pre-conditions: Both one and two are not NULL pointers that point to
//                 linked lists structures that store non-negative digits
//                 at each node.
// Post-conditions: A pointer to a linked list will be returned. The
//                  linked list will store the value of the sum of the
//                  two integers represented by the linked lists passed
//                  into the function.
struct integer* add(struct integer* one, struct integer *two) {

    struct integer *ans;
    int digit1 = 0, digit2 = 0, carry = 0, result, i;


    ans = (struct integer *)malloc(sizeof(struct integer));

    //allocate space for the larger of the 2 arrays
    if(one->size>two->size)
        ans->size=one->size;
    else
        ans->size=two->size;

    ans->digits=(int*)(malloc(sizeof(int)*ans->size));

    for(i=0;isize;i++){
        // Determine digit to add from first operand.
        if (i size)
            digit1 = one -> digits[i];
        else
            digit1 = 0;

        // Determine digit to add from second operand.
        if (i size)
            digit2 = two -> digits[i];
        else
            digit2 = 0;

        // Compute correct addition digit and carry.
        result = (digit1 + digit2 + carry)%10;
        carry = (digit1 + digit2 + carry)/10;

        // Store result in the appropriate linked list.
        ans -> digits[i] = result;

    }//for

    // Take care of the most significant digit if there is a carry.
    if (carry != 0) {

        //copy off the whole array into a new one
        //of size+1 and free the old one in case of carry
        ans->size+=1;
        ans->digits = (int *)realloc(ans->digits, sizeof(int)*ans->size);
        ans->digits[ans->size-1] = carry;
    }

    // Return the ptr. to the added result.
    return ans;
}

// Precondition: number points to a not NULL linked list that contains
//               only single digits stored at each node.
// Postcondition: The integer represented by the linked list pointed to by
//                number will be printed out.
void print(struct integer* number) {

    int i;
    if (number != NULL) {

        // Loop through in backwards order, since number is stored reversed.
        for(i=number->size-1;i>=0;i--){
            printf("%d",number->digits[i]);
        }
    }
}

// Precondition: op1 and op2 point to valid linked lists storing integers,
//               operator is a valid integer operator, and answer is the
//               value of applying the first operation to the second.
// Postcondition: The arithmetic operation desired (op1 operator op2) will
//                be printed to the screen in a reasonable manner.
void print_op(struct integer* op1, struct integer* op2,struct integer* answer,char op) {

    print(op1);
    printf(" %c ", op);
    print(op2);
    printf(" = ");
    print(answer);
    printf("\n");
}

//Preconditions: the first parameter is a pointer to a
// pointer variable that points to
// struct integer. The function skips leading
// blanks and assumes that no leading zeros are
// entered at the input.
//Postconditions: The function will read the digits of the
// large integer character by character,
// convert them into integers and place them in
// nodes of a linked list. The pointer to the
// head of the list is returned as the value of
// the input parameter.
struct integer* convert_integer(char* word) {

 int i;

 struct integer *p=(struct integer *)(malloc(sizeof(struct integer)));
 p->size=0;
    if(word==NULL) p->digits=NULL;

 else {

        // Allocate space for each of the digits.
        p->size = strlen(word);
        p->digits=(int *)(malloc(sizeof(int)*p->size));

        // Store them in reverse order.
        for(i=0;i< p->size;i++)
            p->digits[p->size-i-1]=word[i] - '0';

    }//if word not NULL

 return p;
}

// Frees the memory for the struct pointed to by thisint.
void free_struct(struct integer* thisint) {
    free(thisint->digits);
    free(thisint);
}