Problem
It is desirable to have integers that are unlimited in length. But many programming languages have a limited size integer. C language also has the same limitation. The 'int' type has a size of 4 or 8 bytes nowadays. A 4 byte int can store maximum upto 2^32 that is 4294967296. To store higher values, we can create our own datatype called MyInteger.
Suppose we have to store the number 8589934592 (that is 2^33). Then we can store this number by cutting it in multiple parts. For example one way of storing it will be as follows: We store '8' as one digit, '5' as another in 'int's. Then we link up all these ints using a linked list. So in this case, our data type will be
typedef struct node {
int digit;// can be char digit also, but will be more tricky
struct node *next;
}node;
Now using this a list can be created, which can be accessed from the first node. So we can define
typedef struct node *MyInteger;
On this structure we can also define functinos like
MyInteger add(MyInteger p, MyInteger q);
void Read(Myinteger *a);
void print(MyInteger a);
Which can be called by the user as:
main() {
MyInteger a, b, c;
......
read(&a);
read(&b);
c = add(a, b);
print(a);
}
Here a and b are two variables of MyInteger type and they represent two unlimited size integers to the user. The user treats the c = add(a, b) as c = a + b where c, a, b are unlimited size. While implementing the functions, we basically do some linked list manipulation.
one can do the 'split' more carefully for performance. the number 8589934592 can also be split 2 parts only because an 'int' can store upto 2^32 (or 2^31) data. the logic of 'add()' and other functions will also change accordingly. hint: any number can be represented using any base. for example: 123 = 1*10^2 + 2 * 10^1 + 3 * 10^0 spo 123 was represented using base 10. 123 = 1111011 = 1*2^7 + 1*2^6 + 1*2^5 + 1*2^4+ 1 *2^3 + 1 * 2^1 + 1 * 2^0
Assignment
implement an efficient MyInteger type. the type should have following functions:
Myinteger add(Myinteger p, Myinteger q); // adds p and q and returns the addition (as a new list)
Myinteger mult(Myinteger p, Myinteger q); //multiplies integer p and q and returns the result as a new myinteger
Myinteger readmyint();// reads an unlimited size integer from keyboard and returns it.
void print(Myinteger a); // prints a myinteger
Myinteger readfromfile(char *filename); // reads the integer string stored in a file, given as filename, and returns the myinteger created.
for this submit a myinteger.h and myinteger.c files.
write some big integer data in two files (call them one.int and two.int)
write a user program that can be called as follows: (filename: useint.c)
./useint one.int two.int
the program will call the MyInteger functions, add them and print the result of addition and multiplication as a third MyInteger. While printing just print the number, don't print additional stuff like "Myinteger:123412541223".