Assignment 1

Due Date : Aug 9, 2013

Implementation of Big Integer Multiplication



The unsigned int type in C requires 4 bytes of memory storage. With 4 bytes we can store integers as large as 2 to the power 32. What if we need bigger integers, for example ones having hundreds of digits? If we want to do arithmetic with such very large numbers we cannot simply use the unsigned int data type. One way of dealing with this is to use a different storage structure for integers, such as an array of digits. We can represent an integer as an array of digits, where each digit is stored in a different array index. Since the integers are allowed to be as large as we like, a dynamically-sized array will prevent the possibility of overflows in representation. However we need new functions to operate on these integers. In this assignment, you will develop a function to ADD and multiply arbitrarily large integers stored in this manner.

Here are the prototypes of the functions you must write:

//Preconditions: the first parameter is string that only
// contains digits and is 10000 digits or
// fewer. No leading 0s will be included
// unless the number represented is 0.
//Postconditions: The function will read the digits of the
// large integer character by character,
// convert them into integers and return a
// pointer to the appropriate struct integer.
struct integer* convert_integer(char* stringInt);

//Preconditions: p is a pointer to a big integer.
//Postconditions: The big integer pointed to by p is
// printed out.
void print(struct integer *p);
//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);

You may write other functions to help you with this task. In fact, you are encouraged to do so. You are free to design the prototypes of these other functions. Full credit will be given only if you properly document the code. Extra credit will be given to students who can implement a scheme which uses memory proportional to the size of the numbers in the input.

Submission Instructions will be posted soon.