## Description

1. Overview

This assignment will involve overloading basic integer operators to perform arbitrary precision integer arithmetic in the style of dc(1). Your class bigint will intermix arbitrarily with simple integer arithmetic.

To begin read the man(1) page for the command dc(1) :

man -s 1 dc

A copy of that page is also in this directory. Your program will use the standard dc

as a reference implemention and must produce exactly the same output for the

commands you have to implement :

+-*/%^cdfpq

Also look in the subdirectory misc/ for some examples and in output/ for the result

of running the test data using dc.

2. Implementation strategy

As before, you have been given starter code.

(a) Makefile, trace, and util are similar to the previous program. If you find you

need a function which does not properly belong to a given module, you may

add it to util.

(b) The module scanner reads in tokens, namely a NUMBER, an OPERATOR, or SCANEOF.

Each token returns a token_t, which indicates what kind of token it is (the

terminal_symbol symbol), and the string lexinfo associated with the token.

Only in the case of a number is there more than one character. Note that on

input, an underscore (_) indicates a negative number. The minus sign (-) is

reserved only as a binary operator. The scanner also has defined a couple of

operator<< for printing out scanner results in TRACE mode.
(c) The main program main.cpp, has been implemented for you. For the six binary
arithmetic functions, the right operand is popped from the stack, then the left
operand, then the result is pushed onto the stack.
(d) The module iterstack can not just be the STL stack, since we want to iterate
from top to bottom, and the STL stack does not have an iterator. A stack
depends on the operations back(), push_back(), and pop_back() in the underlying container. We could use a vector, a deque, or just a list, as long as the requisite operations are available.
3. Class bigint
Then we come to the most complex part of the assignment, namely the class bigint.
Operators in this class are heavily overloaded.
(a) most of the functions take a arguments of type const bigint &, i.e., a constant
reference, for the sake of efficiency. But they have to return the result by
value.
CMPS-109 • • Program 2 • Overloading and operators 2 of 5
(b) We want all of the operators to be able to take either a bigint or a long as
either the left or right operand. Because of this we make the arithmetic operators friends instead of members. That will cause automatic conversion from a
long to a bigint via the constructor that accepts a long argument.
(c) The operator<< can’t be a member since its left operand is an ostream, so we
make it a friend, so that it can see the innards of a bigint. Note now dc prints
really big numbers.
(d) The pow function exponentiates in O(log2 n) and need not be changed. It is not
a member of bigint, but it behaves as a member, since it uses only other functions.
(e) The relational operators == and < are coded individually as member functions.
The others, !=, <=, >, and >= are defined in terms of the essential two.

(f) The / and % functions call divide, which is private. One can not produce a quotient without a remainder, and vice versa, so it returns a pair which is both

the quotient and remainder, and the operator just discards the one that is not

needed.

(g) The given implementation works for small integers, but overflows for large

integers.

4. Representation of a bigint

Now we turn to the representation of a bigint, which will be represented by a

boolean flag and a vector of integers.

(a) Replace the declaration

long long_value;

with

using digit_t = unsigned char;

using bigvalue_t = vector

bool negative;

bigvalue_t big_value;

in bigint.h.

(b) In storing the long integer it is recommended that each digit in the range 0 to

9 is kept in an element, although true dc(1) stores two digits per byte. But we

are not concerned here with extreme efficiency. Since the arithmetic operators

add and subtract work from least significant digit to most significant digit,

store the elements of the vector in the same order. That means, for example,

that the number 46 29 would be stored in a vector v as : v3 = 4, v2 = 6, v1 = 2,

v0 = 9. In other words, if a digit’s value is d ×10

k

, then vk = d.

(c) In order for the comparisons to work correctly, always store numbers in a

canonical form : After computing a value from any one of the six arithmetic

operators, always trim the vector by removing all high-order zeros. While

size() > 0 and back() returns zero, pop_back() the high order digit. Zero

should be represented as a vector of zero length and a positive sign.

CMPS-109 • Spring 2015 • Program 2 • Overloading and operators 3 of 5

(d) The representation of a number will be as follows : negative is a flag which

indicates the sign of the number ; big_value contains the digits of the number.

(e) Then use grep or your editor’s search function to find all of the occurrences of

long_value. Each of these occurrences needs to be replaced. Change all of the

constructors so that instead of initializing long_value, they initialize the

replacement value.

(f) The scanner will produce numbers as strings, so scan each string from the end

of the string, using a const_reverse_iterator (or other means) from the end of

the string (least significant digit) to the beginning of the string (most significant digit) using push_back to append them to the vector.

5. Implementation of Operators

(a) Add two new private functions do_bigadd and do_bigsub :

bigvalue_t do_bigadd (const bigvalue_t&, const bigvalue_t&);

bigvalue_t do_bigsub (const bigvalue_t&, const bigvalue_t&);

(b) Change operator+ so that it compares the two numbers it gets. If the signs are

the same, it calls do_bigadd to add the vectors and keeps the sign as the result.

If the signs are different, call do_bigless to determine which one is smaller,

and then call do_bigsub to subtract the larger minus the smaller. Note that

this is a different comparison function which compares absolute values only.

Avoid duplicate code wherever possible.

(c) The operator- should perform similarly. If the signs are different, it uses do_

bigadd, but if the same, it uses do_bigsub.

(d) To implement do_bigadd, create a new bigvalue_t and proceed from the low

order end to the high order end, adding digits pairwise. If any sum is >= 10,

take the remainder and add the carry to the next digit. Use push_back to

append the new digits to the bigvalue_t. When you run out of digits in the

shorter number, continue, matching the longer vector with zeros, until it is

done. Make sure the sign of 0 is positive.

(e) To implement do_bigsub, also create a new empty vector, starting from the low

order end and continuing until the high end. In this case, if the left number is

smaller than the right number, the subtraction will be less than zero. In that

case, add 10, and set the borrow to the next number to −1. You are, of course,

guaranteed here, that the left number is at least as large as the right number.

After the algorithm is done, pop_back all high order zeros from the vector

before returning it. Make sure the sign of 0 is positive.

(f) You will need to implement do_bigless, which will compare the absolute values of the vectors to determine which is smaller :

bool do_bigless (const bigvalue_t&, const bigvalue_t&);

(g) To implement operator==, check to see if the signs are the same and the

lengths of the vectors are the same. If not, return false. Otherwise run down

both vectors and return false as soon a difference is found. Otherwise return

true.

CMPS-109 • Spring 2015 • Program 2 • Overloading and operators 4 of 5

(h) To implement operator<, remember that a negative number is less than a positive number. If the signs are the same, for positive numbers, the shorter one is
less, and for negative nubmers, the longer one is less. If the signs and lengths
are the same, run down the parallel vectors from the high order end to the low
order end. When a difference is found, return true or false, as appropriate. If
no difference is found, return false.
(i) Implement function do_bigmul, which is called from operator*. Operator* uses
the rule of signs to determine the sign of the result, and calls do_bigmul to
compute the product vector.
(j) Multiplication in do_bigmul proceeds by allocating a new vector 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 follows :
p ← Φ
for i ∈[0, m) :
c ← 0
for j ∈[0, n) :
d ← pi+ j + uivj + c
pi+ j ← d %10
c ← d ÷10
pi+n ← c
Note that the interval [a, b) refers to the set {x|a ≤ x < b}, i.e., to a half-open
interval including a but excluding b. In the same way,apair of iterators in
C++ bound an interval.
(k) Long division is complicated if done correctly. See a paper by P. Brinch
Hansen, ‘‘Multiple-length division revisited : A tour of the minefield’’, Software
— Practice and Experience 24, (June 1994), 579–601. Algorithms 1 to 12 are
on pages 13–23, Note that in Pascal, array bounds are part of the type, which
is not true for vectors in C++.
multiple-length-division.pdf
http://brinch-hansen.net/papers/1994b.pdf
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.5815
(l) The function divide as implemented uses the ancient Egyptian division algorithm, which is slower than Hansen’s Pascal program, but is easier to understand. Replace the long values in it by vector

also in [misc/divisioncpp.cpp]. The algorithm is rather slow, but the big-O

analysis is reasonable.

(m) Modify operator<<, first just to print out the number all in one line. You will
need this to debug your program. When you are finished, make it print numbers in the same way as dc(1) does.
(n) The pow function is not a member and uses other operations to raise a number
to a power. If the exponent does not fit into a single long print an error message, otherwise do the computation.
CMPS-109 • • Program 2 • Overloading and operators 5 of 5
6. Memory leak
Make sure that you test your program completely so that it does not crash on a Segmentation Fault or any other unexpected error. Since you are not using pointers,
and all values are inline, there should be no memory leak. Use valgrind to check for
and eliminate uninitialized variables and memory leak.
7. What to submit
Submit source files and only source files : Makefile, README, and all of the header
and implementation files necessary to build the target executable. If gmake does not
build ydc your program can not be tested and you lose 1/2 of the points for the
assignment. Use checksource on your code.
If you are doing pair programming, follow the additional instructions in Syllabus/
pair-programming/ and also submit PARTNER.