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 Acopy 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 whichdoes 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. Eachtoken returns a token_t,whichindicates 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. Forthe 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.Astack depends on the operations back(), push_back(),and pop_back() in the underlying container.Wecould use a vector,adeque, 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 • Spring 2015 • Program 2 • Overloading and operators 2 of 5
(b) Wewant 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 friendsinstead 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 amember 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,whichisprivate.One can not produce a quotient without a remainder,and vice versa, so it returns a pair whichisboth 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,whichwill 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<digit_t; bool negative; bigvalue_t big_value; in bigint.h.
(b) In storing the long integer it is recommended that eachdigit 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,ifadigit’svalue is d ×10k,then vk = d. (c) In order for the comparisons to work correctly,alwaysstore numbers in a canonical form:After computing a value from any one of the six arithmetic operators,alwaystrim 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’ssearchfunction to find all of the occurrences of long_value.Eachofthese 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, soscan eachstring 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.Ifthe signs are the same,itcalls do_bigadd to add the vectors and keeps the sign as the result. If the signs are different, call do_bigless to determine whichone is smaller, and then call do_bigsub to subtract the larger minus the smaller.Note that this is a different comparison function whichcompares absolute values only. Avoid duplicate code wherever possible.
(c) The operator- should perform similarly.Ifthe signs are different, it uses do_ bigadd,but if the same,ituses do_bigsub.
(d) Toimplement do_bigadd,create a new bigvalue_t and proceed from the low order end to the high order end, adding digits pairwise.Ifany 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) Toimplement 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.Inthat case,add 10, and set the borrow to the next number to −1. Youare,ofcourse, 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,whichwill compare the absolute values of the vectors to determine whichissmaller : bool do_bigless (const bigvalue_t&, const bigvalue_t&);
(g) Toimplement operator==,checktosee if the signs are the same and the lengths of the vectors are the same.Ifnot, 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) Toimplement operator<,remember that a negative number is less than a positive number.Ifthe signs are the same,for positive numbers,the shorter one is less,and for negative nubmers,the longer one is less.Ifthe 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,asappropriate.If no difference is found, return false.
(i) Implement function do_bigmul,whichiscalled 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.Ifu 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.Inthe 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:Atour 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, arraybounds are part of the type,which is not true for vectors in C++. multiple-length-division.pdf https://brinch-hansen.net/papers/1994b.pdf https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.5815
(l) The function divide as implemented uses the ancient Egyptian division algorithm, whichisslower than Hansen’sPascal program, but is easier to understand. Replace the long values in it by vector (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.Ifthe exponent does not fit into a single long print an error message,otherwise do the computation.
CMPS-109 • Spring 2015 • 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 checkfor 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.Ifgmake 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.