CPE/CSC 101
Spring 2007
Programming Project #3
Due Date
Test Plan due Tuesday 22 May at class time.
Completed program due Friday 25 May 11:59pm.
You must turn in your source electronically on Hornet using the handin
command by this deadline. Instructions are provided below.
No late submittals will be accepted!
Objectives
- To demonstrate your mastery of writing programs with arrays.
- To demonstrate your mastery of linking multi-file programs.
Resources
- Your instructor or the designated department tutors in the
tutoring center.
- Your textbook(s)
- Your own innate capabilities and resourcefulness!
- A working program exhibiting the behavior that your program
should exhibit when you finish it that you can run on Hornet by typing
the
command
~cs101-1/www/mdcalc
Ground Rules
- Keep track of the time you spend developing the
project. Recommended: Time
Log Form
- Your program must not use any global
variables. You may declare variables that are local to the main
function.
- Your program must implement the
required functions as specified in the header files.
- Your program must use the required
functions appropriately.
- Your program must mimic the sample
program’s behavior exactly , letter for letter (see Resources
section above on how to run the sample program).
- You may not use the Web for research
or assistance with any aspect of this assignment.
- NOTE: This project is to be an
individual effort! DO NOT
collaborate with any of your classmates -- or anyone else on this
project. Violating this rule may result in being failed
from the
course.
1.0 Problem
Description
The largest integer that can be stored in a computer is always limited
by the number of bits in a word. In the not so distant past,
8-bit
computers were standard, and the largest integer they could manipulate
was 32767. On a 32-bit Pentium PC the maximum integer is
2147483647,
ten digits in length. This is adequate for most purposes,
but some applications require many more digits than this. For example,
public-key encryption with the RSA algorithm typically requires 300
digit numbers. Computing the probabilities of certain real events often
involves very large numbers. For example, what is the probability of
winning the Texas Lottery jackpot
prize with one ticket? The number of combinations of 50 numbers taken
6 at a time, "50 choose 6", is 50!/((50-6)!6!). 50
factorial is a huge number, specifically:
30,414,093,201,713,378,043,612,608,166,064,768,844,377,641,568,960,512,000,000,000,000
So we must move to a different representation of
non-negative integers.
The solution we will use is to represent a large integer as a sequence
of digits where each digit is stored as one element in an array
of integers.
We can define the array to be as large as we need.
In our new representation, we have an array of "digits"
(integers). Let's say we use a preprocessor directive to specifiy
the
length of the array:
#define kNumDigits 20 /* How many digits to use for
arithmetic operations */
The most significant digit of the number will be store in position zero
in the array, and the least significant digit will be stored in
position 19.
How do we perform arithmetic on our new "big" integers? We'll
use the algorithm we learned in grade school: add corresponding digits,
plus a "carry" generated by previous overflows. We imagine that
the
computer is limited to performing only single digit arithmetic
operations. So it can add 3 + 5 to get 8, but can not add 13 +
6. We
use a boolean variable Carry
to indicate whether or not the sum is greater than 9. If asked to
add
7 + 8 it would give 5 and the "carry" flag would be set. Then two
arrays are added by looping through the array (from right to left) and
adding together corresponding elements of the arrays (and adding one
more if the "carry" flag is set).
As a practical matter our multi-digit arithmetic won't be very useful
unless we can display the results or read in values from the
user. The scanf() function is limited to reading normal
integers. We will have to accept a big integer as a string of
characters and then convert each character into a numeric digit and
store it in the proper position in the array. The user should not
have to enter leading zeroes, so if the
input is the number three hundred seventy-two the user would enter
"372"
not "0000000372".
The goal of this assignment is to create a multi-digit integer math
library. We will also create a command line calculator that
uses our library.
The calculator operates on numbers typed on the command line itself
(not read in with scanf). We will implement two operators,
addition and increment. The addition operator is the plus sign,
and the increment operator is the @ sign.For
example:
a.out 32 + 45
77
a.out 1111123456789 + 2
1111123456791
a.out 23 @
24
The calculator should display specific error messages for certain error
conditions. The error conditions that require handling are:
- Not enough arguments supplied on the command line.
- Unrecognized arithmetic operator on the command line (for
anything other than a plus sign or an @ sign).
- Arithmetic overflow if the addition exceeds the number of digits
allowed.
1:18pm falcon > a.out
Not enough arguments.
1:18pm falcon > a.out 123
Not enough arguments.
1:18pm falcon > a.out 111 +
Not enough arguments.
1:19pm falcon > a.out 111 #
Unrecognized operator.
1:19pm falcon > a.out 111 @
112
1:19pm falcon > a.out 111 + 222
333
1:20pm falcon > a.out 11111555552222266666 + 1
11111555552222266667
1:20pm falcon > a.out 9999999999999999999 + 1
10000000000000000000
1:20pm falcon > a.out 99999999999999999999 + 12
Addition Overflow!
11
1:40pm falcon > a.out 12345678901234567890123 + 1
12345678901234567891
1:35pm falcon ~/www> a.out 12 + 3
15
1:35pm falcon > a.out 12 ++ 3
Unrecognized operator.
1:39pm falcon > a.out 12 * 3
Unrecognized operator.
1:39pm falcon > a.out 12+3
Not enough arguments.
1:40pm falcon > a.out 12 +3
Unrecognized operator.
The program does not have to deal with these conditions:
- Non-numeric input on the command line.
- Negative numbers.
2.0 Constraints
You must use this header file that defines the multi-digit math library
functions: multidigitlib.h
You must write your own implementation for these functions in a
a separate source file named multidigitlib.c
Do not include a main function in this file.
The print() function is the only function that does any
printing.
Compile this file separately without linking it using the icon
of the
single green plus in jGRASP.
Your implementation of increment() should invoke the add()
function to perform the addition.
The calculator is to be implemented in the main function of a
separate
driver file named multidigitcalc.c.
Compile this file separately without linking it using the icon
of the
single green plus in jGRASP.
Link all the object files
(.o) together
into an executable (a.out) by issuing the following command at
the DOS/UNIX
prompt:
gcc multidigitlib.o multidigitcalc.o
Sorry this command isn't part of jGRASP, you have to issue it from a
command window (in Windows) or the UNIX prompt on hornet. Issue the
command in the directory where you compiled your source files.
3.0 Implementation Hints
To obtain the command line arguments, use the technique described in
section 13.7 of the textbook. A more elaborate explanation
and examples about how to provide arguments to the main function can be
found in this tutorial.
To convert a character digit into numeric form use the technique shown
in chapter 7 and in this prediction
exercise.
The strlen() function returns how many characters are in a
string (See page 441 in the textbook)..
4.0 Testing
You are required to write a test plan for your program. Use the
Test
Plan form that we have used in class to describe the input data
and expected outputs of your program. Your test plan
should include enough test cases to demonstrate
minimum complete coverage. That is, your test data must cause
every statement in the program to be executed, and produce correct
results.
The instructor has provided a
working implementation of his library functions. You
can write a test driver for these functions to see how they
behave. While developing your driver, you may link it with the
instructor's library until you get yours implemented.
Object file for Hornet: multidigitlib.o
(available on Hornet as ~cs101-1/www/multidigitlib.o)
The instructor will provide a unit test driver that he will use during
grading of your program. (Be sure to use the -lm flag
when you link with this object file).
Object file for Hornet: mdtester.o
(available on Hornet as ~cs101-1/www/mdtester.o)
When the instructor grades your program, he will change the value of kNumDigits
in the header file. Your program should still compile and execute
correctly.
5.0 Grading
| 10% |
Test Plan provides minimum complete coverage |
| 5% |
toBigInt() passes unit test
|
| 5% |
clear() passes unit test
|
| 5% |
increment() passes unit test
|
5%
|
increment() overflow detected properly
during unit test.
|
| 5% |
overflow detected properly during system test. |
10%
|
print()and increment() pass system tests |
15%
|
print()and add() pass system tests |
5%
|
Error conditions produce correct error message
during system test. |
| 15% |
Algorithm design meets quality standards for flexibility,
maintainability, etc.
|
| 10% |
Coding
standards are followed. |
| 10% |
Clean compile (no warnings using the required compiler flags)
and all components integrate properly. |
Remember, your program will be tested on Hornet. Code that does
not compile will receive a grade of zero.
6.0 Submitting Your Work
You need to submit your source code electronically using the
handin utility:
- You will submit two source code files, named as follows:
multidigitlib.c contains the implementation of
the
functions defined in multidigitlib.h.
multidigitcalc.c
contains the calculator main program.
Do not submit any other files.
- Move
the necessary file(s)
to your hornet account using your favorite secure file transfer program.
- Log
on to hornet using your favorite Secure Shell client program.
- Change directory (cd) to the directory containing your source
file to hand in.
- Be
sure to compile and test your code on hornet using the required
compiler flags ( -Wall –ansi – pedantic)
one last time just before turning the files in.
- Submit your code using handin:
handin cs101-7 Program3
multidigitlib.c multidigitcalc.c
- You should see messages that indicate handin occurred without
error. You can (and should) always verify what has been handed in by
executing the following command:
handin cs101-7 Program3
- Determine the number of lines of code in your files:
~cs101-1/bin/countloc multidigitlib.c
~cs101-1/bin/countloc multidigitcalc.c
- Complete the programmer productivity summary
form for this project.
Extra Credit
Enhance the multidigitlib.c library to include a multiplication
function named multiply.
Enhance the calculator to include another operator, the asterisk, for
multiplication.
Recall from grade school how you multiplied
two large numbers A and B: starting with
the least significant digit, you multiplied each digit of A
with every digit of B, forming a partial product. You shifted
this product over to the left for each new digit, writing overflowed
digits above A to remind yourself to add them in. You should
create a function multiply_one_digit that will multiply an
entire big integer by a single digit, placing the result in
a new big int. You should also create a function shift_left
that shift
a number over to the left a number of spaces, effectively multiplying
it by 10i where i is the number
of spaces.
An alternate algorithm for multiplying A and B is to
add A to itself B times. This sounds like
something that could be done easily with a for statement;
however, B is a big int so can't be used as a loop control
variable. So it's more complicated than it might first seem.
The product of 2 n-digit numbers might possibly be 2n digits
long. Your multiply function should produce an overflow return
code in the same manner as the add function does.
The extra credit is worth 2% of your course grade and is due at the
same time as the original assignment.