## Description

$Id: asg1-dc-bigint.mm,v 1.4 2017-06-16 15:09:35-07 – – $

PWD: /afs/cats.ucsc.edu/courses/cmps109-wm/Assignments/asg1-dc-bigint

URL: http://www2.ucsc.edu/courses/cmps109-wm/:/Assignments/asg1-dc-bigint/

**Overview**

** **

This assignment will involve overloading basic integer operators to perform arbi-trary precision integer arithmetic in the style of **dc**(1). Your class **bigint** will inter-mix 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 :

**+ – * / % ^ c d f p** **q**

** **

Also look in the subdirectory **misc/** for some examples and in **output/** for the result of running the test data using **dc**.

**Implementation strategy**

** **

As before, you have been given starter code.

**Makefile**,**trace**, and**util**If you find you need a function which does not prop-erly belong to a given module, you may add it to**util**.

- 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**

- The main program
**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.

- 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 underly-ing container. We could use a**vector**, a**deque**, or just a**list**, as long as the req-uisite operations are available.

**Class****bigint**

** **

Then we come to the most complex part of the assignment, namely the class **bigint**.

Operators in this class are heavily overloaded.

- 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.

- 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.

- The relational operators
**==**and**<**are coded individually as member functions. The others,**!=**,**<=**,**>**, and**>=**are defined in terms of the essential two.

- All of the functions of
**bigint**only work with the sign, using**ubigint**to do the actual computations. So**bigint::operator+**and**bigint::operator-**will check the signs of the two operands then call**ubigint::operator+**or**ubigint::opera-tor-**, as appropriate, depending on the relative signs and magnitudes. The multiplication and division operators just call the corresponding**ubigint**oper-ators, then adjust the resulting sign according to the rule of signs.

**Class****ubigint**

** **

Class **ubigint** implements unsigned large integers and is where the computational work takes place. Class **bigint** takes care of the sign. Now we turn to the represen-tation of a **ubigint**, which will be represented by vector of bytes.

(a) Replace the declaration

**using unumber = unsigned long;**

** **

**unumber uvalue {};**

** **

with

**using udigit_t = unsigned char;**

** **

**using ubigvalue_t = vector<udigit_t>;**

** **

**ubigvalue_t ubig_value;**

in **ubigint.h**.

- In storing the big integer, each digit is kept as a number in the range 0 to 9 in an element of the vector. 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 4629 would be stored in a vector *v* as : *v*_{3} = 4, *v*_{2} = 6, *v*_{1} = 2, *v*_{0} = 9. In other words, if a digit’s value is *d* × 10* ^{k}*, then

*v*

*=*

_{k}*d*.

- 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() == 0) pop_back();**

** **

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

- The scanner will produce numbers as
**string**s, 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 signifi-cant digit) using**push_back**to append them to the vector.

**Implementation of Operators**

** **

- For
**bigint::operator+**, check to see if the signs are the same or different. If the same, call**ubigint::operator+**to compute the sum, and set the result sign as appopriate. If the signs are different, call**ubigint::operator-**with the larger number first and the smaller number second. The sign is the sign of the

larger number.

- The operator
**bigint::operator-**should perform similarly. If the signs are dif-ferent, it uses**ubigint::operator+**but if the same, it uses**ubigint::operator-**.

- To implement
**ubigint::operator+**, create a new**ubigint**and proceed from the low order end to the high order end, adding digits pairwise. For any sum >= 10, take the remainder and add the carry to the next digit. Use**push_back**to append the new digits to the**ubigint**. 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.

- To implement
**ubigint::operator-**, also create a new empty vector, starting from the low order end and continuing until the high end. If the left digit is smaller than the right digit, the subtraction will be less than zero. In that case, add 10 to the digit, and set the borrow to the next digit to −1. After the algorithm is done,**pop_back**all high order zeros from the vector before return-ing it. Make sure the sign of 0 is positive.

- 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.

- To implement
**operator<**, remember that a negative number is less than a posi-tive 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.

- Implement function
**bigint::operator***, which uses the rule of signs to deter-mine the result. The number crunching is delegated to**ubigint::operator***, which produces the unsigned result.

- Multiplication in
**ubigint::operator***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*) :

- ←
**p**_{i}_{+}+_{j}**u**_{i}**v**+_{j}*c***p**_{i}_{+}←_{j}*d*% 10 - ←
*d ÷*10

* *

**p**_{i}_{+}* _{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, a pair of iterators in C++ bound an interval.

- 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 **vector**s 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**

** **

- The function
**divide**as implemented uses the ancient Egyptian division algo-rithm, which is slower than Hansen’s Pascal program, but is easier to under-stand. Replace the**long**values in it by**vector<digit_t>**. The logic is shown also in**misc/divisioncpp.cpp**. The algorithm is rather slow, but the big-*O*analysis is reasonable.

- 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 num-bers in the same way as**dc**(1) does.

- The
**pow**function 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. The power function is not a member of either**bigint**or**ubig-int**, and is just considered a library function that is implemented using more primitive operations.

**Memory leak**

** **

Make sure that you test your program completely so that it does not crash on a Seg-mentation 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.

**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**.