CSE-111 • Spring 2021 • Program 1 • Overloading and operators
Using C++11/14/17 (20?)All programming in this course will be done C++ style, not C style, as shown in thefollowing table.Do not use : Instead, use :char* strings <string>C arrays <vector><stdio.h>, <cstdio> <iostream>, <iomanip>pointers <shared_ptr>union inheritance<header.h> <cheader>Include only C++11/14/17 header files where feasible : using namespace std;Include <cheader> files only when C++-style files are unavailable. Include <header.h> files from C only when an appropriate <cheader> files is unavailable. Use thescript cpplint.py.perl (a wrapper for cpplint.py) to check style.OverviewThis assignment will involve overloading basic integer operators to perform arbitraryprecision integer arithmetic in the style of dc(1). Your class bigint will intermixarbitrarily with simple integer arithmetic.To begin read the man(1) page for the command dc(1) :man -s 1 dcA copy of that page is also in this directory. Your program will use the standard dcas a reference implemention and must produce exactly the same output for thecommands you have to implement :+-*/%^cdfpqIf you have any questions as to the exact format of your output, just run dc(1) andmake sure that, for the operators specified above, your program produces exactlythe same output. A useful program to compare output from your program with thatof dc(1) is diff(1), which compares the contents of two files and prints only the differences.Also look in the subdirectory misc/ for some examples.See also :• dc (computer program)https://en.wikipedia.org/wiki...(computer_program)• dc, an arbitrary precision calculatorhttps://www.gnu.org/software/...Implementation strategyAs before, you have been given starter code.(a) Makefile, debug, and util If you find you need a function which does not properlybelong to a given module, you may add it to util.CSE-111 • Spring 2021 • Program 1 • Overloading and operators 2 of 5(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 (theterminal_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 oninput, an underscore (_) indicates a negative number. The minus sign (-) isreserved only as a binary operator. The scanner also has defined a couple ofoperator<< for printing out scanner results in debug mode.(c) The main program main.cpp, has been implemented for you. For the six binaryarithmetic functions, the right operand is popped from the stack, then the leftoperand, then the result is pushed onto the stack.(d) The module iterstack can not just be the STL stack, since we want to iteratefrom top to bottom, and the STL stack does not have an iterator. A stackdepends on the operations back(), push_back(), and pop_back() in the underlyingcontainer. We could use a vector, a deque, or just a list, as long as the requisiteoperations are available.Class bigintThen 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 constantreference, for the sake of efficiency. But they have to return the result byvalue.(b) The operator<< can’t be a member since its left operand is an ostream, so wemake it a friend, so that it can see the innards of a bigint. Note now dc printsreally big numbers.(c) The relational operators == and < are coded individually as member functions.The others, !=, <=, >, and >= are defined in terms of the essential two.(d) All of the functions of bigint only work with the sign, using ubigint to do theactual computations. So bigint::operator+ and bigint::operator- will checkthe signs of the two operands then call ubigint::operator+ or ubigint::operator-,as appropriate, depending on the relative signs and magnitudes. Themultiplication and division operators just call the corresponding ubigint operators,then adjust the resulting sign according to the rule of signs.Class ubigintClass ubigint implements unsigned large integers and is where the computationalwork takes place. Class bigint takes care of the sign. Now we turn to the representationof a ubigint, which will be represented by vector of bytes.(a) Replace the declarationusing unumber = unsigned long;unumber uvalue {};withusing ubigvalue_t = vector<uint8_t>;ubigvalue_t ubig_value;in the header file <ubigint.h>. The type uint8_t is an unsigned 8-bit integerCSE-111 • Spring 2021 • Program 1 • Overloading and operators 3 of 5defined in <cstdint>.(b) In storing the big integer, each digit is kept as an integer in the range 0 to 9 inan element of the vector. Since the arithmetic operators add and subtractwork from least significant digit to most significant digit, store the elements ofthe vector in the same order. That means, for example, that the number 4629would 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 × 10k, then vk = d.(c) In order for the comparisons to work correctly, always store numbers in acanonical form : After computing a value from any one of the six arithmeticoperators, 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.(d) The scanner will produce numbers as strings, so scan each string from the endof the string, using a const_reverse_iterator (or other means) from the end ofthe 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(a) For bigint::operator+, check to see if the signs are the same or different. Ifthe same, call ubigint::operator+ to compute the sum, and set the result signas appopriate. If the signs are different, call ubigint::operator- with thelarger number first and the smaller number second. The sign is the sign of thelarger number.(b) The operator bigint::operator- should perform similarly. If the signs are different,it uses ubigint::operator+ but if the same, it uses ubigint::operator-.(c) To implement ubigint::operator+, create a new ubigint and proceed from thelow 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 toappend the new digits to the ubigint. When you run out of digits in theshorter number, continue, matching the longer vector with zeros, until it isdone. Make sure the sign of 0 is positive.(d) To implement ubigint::operator-, also create a new empty vector, startingfrom the low order end and continuing until the high end. If the left digit issmaller than the right digit, the subtraction will be less than zero. In thatcase, add 10 to the digit, and set the borrow to the next digit to −1. After thealgorithm is done, pop_back all high order zeros from the vector before returningit. Make sure the sign of 0 is positive.(e) To implement operator==, check to see if the signs are the same and thelengths of the vectors are the same. If not, return false. Otherwise run downboth vectors and return false as soon a difference is found. Otherwise returntrue.(f) To implement operator<, remember that a negative number is less than a positivenumber. If the signs are the same, for positive numbers, the shorter one isless, and for negative nubmers, the longer one is less. If the signs and lengthsare the same, run down the parallel vectors from the high order end to the lowCSE-111 • Spring 2021 • Program 1 • Overloading and operators 4 of 5order end. When a difference is found, return true or false, as appropriate. Ifno difference is found, return false.(g) Implement function bigint::operator*, which uses the rule of signs to determinethe result. The number crunching is delegated to ubigint::operator*,which produces the unsigned result.(h) Multiplication in ubigint::operator* proceeds by allocating a new vectorwhose size is equal to the sum of the sizes of the other two operands. If u is avector of size m and v is a vector of size n, then in O(mn) speed, perform anouter 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. Thealgorithm can be described mathematically as follows :p ← for i ∈ [0, m) :c ← 0for j ∈ [0, n) :d ← pi+ j + uivj + cpi+ j ← d rem 10c ← d ÷ 10pi+n ← cNote that the interval [a, b) refers to the set {x|a ≤ x < b}, i.e., to a half-openinterval including a but excluding b. In the same way,apair of iterators inC++ bound an interval.(i) Long division is complicated if done correctly. See a paper by P. BrinchHansen, ‘‘Multiple-length division revisited : A tour of the minefield’’, Software— Practice and Experience 24, (June 1994), 579–601. Algorithms 1 to 12 areon pages 13–23, Note that in Pascal, array bounds are part of the type, whichis not true for vectors in C++.multiple-length-division.pdfhttp://brinch-hansen.net/pape...http://citeseerx.ist.psu.edu/...(j) 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<digit_t>. The logic is shownalso in misc/divisioncpp.cpp. The algorithm is rather slow, but the big-Oanalysis is reasonable.(k) Modify operator<<, first just to print out the number all in one line. You willneed this to debug your program. When you are finished, make it print numbersin the same way as dc(1) does.(l) The pow function uses other operations to raise a number to a power. If theexponent does not fit into a single long print an error message, otherwise dothe computation. The power function is not a member of either bigint or ubigint,and is just considered a library function that is implemented using moreprimitive operations.CSE-111 • Spring 2021 • Program 1 • Overloading and operators 5 of 5Memory leak and other problemsMake sure that you test your program completely so that it does not crash on a SegmentationFault or any other unexpected error. Since you are not using pointers,and all values are inline, there should be no memory leak. Use valgrind(1) to checkfor and eliminate uninitialized variables and memory leak.If your program is producing strange output or segmentation faults, use gdb(1) andthe debug macros in the debug module of the code/ subdirectory.Version of g++The code must compile and run using g++ on unix.ucsc.edu, regardless of whether itruns elsewhere. When this document was formatted that was :bash-$ which g++/opt/rh/devtoolset-8/root/usr/bin/g++bash-$ g++ --version | head -1g++ (GCC) 8.3.1 20190311 (Red Hat 8.3.1-3)bash-$ echo $(uname -sp) - $(hostname) - $(date)Linux x86_64 - unix6.lt.ucsc.edu - Fri Mar 26 00:01:02 PDT 2021What to submitSubmit source files and only source files : Makefile, README, and all of the headerand implementation files necessary to build the target executable. If gmake does notbuild ydc your program can not be tested and you lose 1/2 of the points for theassignment. Use checksource on your code to verify basic formatting.Look in the .score/ subdirectory for instructions to graders. Read Syllabus/pairprogramming/and also submit PARTNER if you are doing pair programming. Eitherwa y submit the README described therein.Et cetera ( ‘´).The accuracy of the Unix utility dc(1) can be checked by :echo ’82 43/25 43+65P80P82P73P76P32P70P79P79P76P10P’ | dc