Description
1. Overview
In this assignment you will implement a subset of the dc(1) arbitrary precision calculator. For specifications, read the man page for that utility, and experiment by running dc itself. You will implement
six of its operators : +, -, *, c, f, p. Your program will be an executable image called mydc.
2. Modules in the program
The following modules are part of the program. For all but main a header (.h) file specifies the interface which is accompanied by an implementation (.c) file.
(a) Module debug contains useful debugging and tracing information.
(b) Module stack is a parameterized stack using an array implementation with array doubling to
take care of a full stack.
(c) Module bigint is the important part of this project and handles multiprecision integer arithmetic using an array of characters.
(d) Module token Reads long integers providing input to the rest of the program.
(e) Module main handles user interface, input and output.
3. Big integer implementation
Following is a more detailed discussion of how to implement the bigint module.
(a) Before attempting to implement bigint, perform each of the three operations on paper, reminding yourself how to perform the operations without a calculator.
(b) A bigint consists of an array of digits. Index 0 has the least significant digit, and the end of the
array has the most significant digit. Each byte contains a single digit in the range 0 … 9, inclusive. The capacity field specifies the dimension of the array, and the size field specifies the
number of significant digits in the array, with leading zeros suppressed.
(c) Addition, if the signs are the same : call do_add to actually perform the addition and return a
new bigint. Then set the sign to be the sign of one of the arguments.
(d) Addition, if the signs are different: call do_sub with the larger number as its left operand and
the smaller number as the right operand. Then set the sign to that of the larger number.
(e) Subtraction : if the signs are different, call do_add, otherwise call do_sub.
(f) Do_add and do_sub are called from either the addition or subtraction function to do the array
work. Note that it is marked static and is not called outside of the module.
(g) Do_add allocates a new bigint with space for a number of digits one larger than the largest
operand. Then it loops across each array from index [0] to the end, adding and carrying as is
done by hand :
digit = this->digits[index] + that->digits[index] + carry;
result->digits[index] = digit % 10;
carry = digit / 10;
There is a little extra trickiness at the high end of the shorter number.
(h) Do_sub allocates a new bigint whose size is the same as the left operand, and then performs the
subtraction instead of additionC :
digit = this->digits[index] – that->digits[index] – borrow + 10;
result->digits[index] = digit % 10;
borrow = 1 – digit / 10;
After computing the result, trim off high-order zeros.
CMPS-012B • Spring 2013 • Program 4 • Stacks and Arbitrary Precision page 2 of 2
(i) Multiplication proceeds by allocating a new bigint whose size is equal to the sum of the sizes of
the other two operands. If
→
u is a vector of size m and →
v is a vector of size n, then in O(mn)
speed, perform an outer loop over one argument and an inner loop over the other argument,
adding the new partial products to the product →
p as you would by hand. The algorithm can be
described mathematically as shown in Figure 1 (a).
(j) An alternative method of computing the product runs a little more slowly because of the extra
function calls, as shown in Figure 1 (b). The symbols +ˆ, ˆ−, ×, ˆ ÷ˆ, etc., represent vector rather
than scalar operations. A static function must be written for each of these if this implementation method is chosen.
(k) Note that malloc(3) returns uninitialized storage, but calloc(3) sets its allocated storage to 0, so
new_bigint calls calloc, not malloc, to allocate the underlying arrays. From the synopsis of malloc(3) :
#include
void *calloc (size_t nmemb, size_t size);
void *malloc (size_t size);
void *realloc (void *ptr, size_t size);
void free (void *ptr);
Algorithm (a) Algorithm (b) Algorithm (c)
→
p ←
→
0
for i ∈ 0 … m −1 :
c ← 0
for j ∈ 0 … n −1) :
d ←
→
pi+ j +
→
ui
→
v j + c
→
pi+ j ← d %10
c ← d ÷10
→
pi+n ← c
→
p ←
→
0
while →
v ≠ˆ
→
0 :
if odd →
v :
→
p ←
→
p +ˆ
→
u
→
v ←
→
v −ˆ
→
1
else :
→
u ←
→
u ׈
→
2
→
v ←
→
v ÷ˆ
→
2
// This algorithm is not
// acceptable because of
// exponential running time.
→
p ←
→
0
while →
v ≠ˆ
→
0 :
→
p ←
→
p +ˆ
→
u
→
v ←
→
v −ˆ
→
1
Figure 1. Tw o vector multiplication algorithms
4. Testing your program
Your program should write exactly the same output to both stdout and stderr as does dc(1), provided
that inputs do not contain those facilities of dc that your program is not expected to imitate. For
example :
dc test-dc.out 2>test-dc.err
mydc test-mydc.out 2>test-mydc.err
diff test-dc.out test-mydc.out
diff test-dc.err test-mydc.err
Both of the diff(1) commands should produce no output for comparing stdout, and only a difference
in the name of the ELF for diffing stderr.
5. What to submit
Submit Makefile, README, and all C source and header files necessary for the grader to build your program with the command make. If you are doing pair programming, see the additional requirements.