CS1101C Practical Exam

Session 2 (1200 - 1345 hours)

Big Integer Number

The name of your C program file must be called bignum.c, files with any other name will not be marked.

The deadline for this lab is Wednesday 11 April 2007, 13:45:59 hours. Strictly no submissions will be accepted after the deadline.

Background

As you know, integers (int type) in C has limited range (no more than 2,147,483,647). However, if we choose to represent integer using char array where each element represents one digit, we can have a much larger range (limited by the size of array only). For example, using a character array of size 20 allows us to represent an integer up to 20 digits. Since we can now represent some really big numbers, we will name this representation bignum.

The Task

To make bignum useful, we will need to provide some common functions, like comparison, addition etc. You are required to write a program to test out these functions on bignums with 20 digits or less. Your program will read from a text file (input.txt) which has the following format. (This file has been copied into your directory by the pesetup command.)

command
one or two lines of bignum(s) depends on the command
another command
one or two lines of bignum(s) depends on the command
....
....

The following table summarize the commands and the required functionality:

Command	Number of bignum(s)	Functionality
1	1	Checks whether the bignum supplied is valid. The bignum should contains only digits and no other characters.
2	2	Compares the two bignums, assuming that they are valid bignums. Checking of the bignums should be done before this function is called and indicate INVALID if at least one of the bignums is invalid. If both bignums are valid, this function is called. Then the possible results are: EQUAL : the two bignums are equal. LARGER : the first bignum is larger than the second. SMALLER : the first bignum is smaller than the second.
3	2	Adds the two bignums assuming that they are valid bignums. Checking of the bignums should be done before this function is called and indicate INVALID if at least one of the bignums is invalid. If both bignums are valid, this function is called. Then show the sum and indicate OVERFLOW if the sum is larger than 20 digits.
4	0	Stops the program.

For example, given the following input file:

1
12345678901234567890
1
12345abc000000012345
1
12345
1
12345+4567
2
98765432109876543210
98765432109876543210
2
98765432109876543210
8765432109876543210
2
8765432109876543210
98765432109876543210
2
12345abc000000012345
8765432109876543210
3
11111111111111111111
22222222222222222222
3
9999999999999999999
1
3
99999999999999999999
1
3
99999999999999999999
11111111111111111111
3
12345xxx12345
99999999999999999999
4

The sample output is given below (with added comments to aid your understanding):

12345678901234567890:VALID                              //a 20-digit bignum
12345abc000000012345:INVALID                            //"abc" are not valid digits
12345:VALID                                             //a 5-digit bignum
12345+4567:INVALID                                      //"+" is not a valid digit
98765432109876543210vs98765432109876543210:EQUAL        //same bignum
98765432109876543210vs8765432109876543210:LARGER        //first > second
8765432109876543210vs98765432109876543210:SMALLER       //first < second
12345abc000000012345vs8765432109876543210:INVALID       //first is invalid
11111111111111111111+22222222222222222222=33333333333333333333
9999999999999999999+1=10000000000000000000
99999999999999999999+1=00000000000000000000:OVERFLOW    //answer more than 20 digits
99999999999999999999+11111111111111111111=11111111111111111110:OVERFLOW //sum more than 20 digits
12345xxx12345+99999999999999999999=INVALID              //the first bignum is not a valid bignum

Assumptions

The following can be assumed when designing your program.

The bignums (even invalid ones) contains no spaces in between.
The bignums (even invalid ones) contains no more than 20 characters.
Even when there is an overflow for addition, the result of the addition is still correct for the least significant (rightmost) 20 digits.
You are not required to handle file I/O errors.

Program Specifications

You must use character array to represent bignum. However, whether to use them as string or plain array is up to you to decide. Make sure your array is of the correct size regardless of your decision. No credit will be given if you use any other representation for the bignums. You must define the following functions in your program:

int isBigNum(char bn[]): Function isBigNum checks whether bn is a valid bignum. Returns 1 if true, 0 otherwise.
int compareBigNum(char bn1[], char bn2[]): Function compareBigNum compares bignums bn1 and bn2. Return 1 if bn1 is larger than bn2. Return -1 if bn2 is larger than bn1. Return 0 if bn1 is equal to bn2.
int addBigNum(char bn1[], char bn2[], char bnSum[]): Function addBigNum adds bn1 to bn2 and places the result in bnSum. Additionally, returns 0 to indicate normal operation. Return 1 to indicate an overflow has occurred.

You are allowed to write other functions if needed. Remember to follow the sample output exactly; else marks will be deducted.

Submit your program using the submit bignum.c command, and check your submission using the check command.

All the best!

Hints and Tips

Remember that '1' is not equivalent to the number 1. It is a character with ASCII value of 49. Similarly for other digits.

We will test your programs with other (more complicated) text input files.

Do not use any structures or any form of dynamic memory allocation (using malloc or calloc) in your program, else no credit will be given.

Remember to submit your program frequently using the submit bignum.c command, and check your submission using the check command.

All the best!

UNIX commands

Some useful UNIX commands (in case you forgot what you did in Lab 0):

“dir”: lists all the files in the directory.
“cp a.txt b.txt”: copies a.txt to b.txt.
“mv a.txt b.txt”: moves / renames a.txt to b.txt.
“cat a.txt”: shows the contents of a.txt.