Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSE 101
Introduction to Data Structures and Algorithms
Programming Assignment 6
In this assignment you will create a BigInteger ADT in C++ that is capable of performing arithmetic
operations on arbitrarily large signed integers. The underlying data structure for this ADT will be a List of
longs. It will therefore be necessary to alter your List ADT from pa5 slightly. Fortunately, this can be done
by changing a single line of code in List.h, namely line 15, which changes from
typedef int ListElement;
to
typedef long ListElement;
Make this change, then test your List again using your ListTest.cpp (and my ListClient.cpp if you like).
The BigInteger ADT will represent a signed integer by encapsulating two pieces of data: an int (which will
be either 1, -1, or 0) giving its sign, and a List of non-negative longs representing its magnitude. Each List
element will be a single digit in the base positional numbering system, where is a power of 10: =
10. For reasons that will become clear, we restrict the exponent to the range 1 ≤ ≤ 9. The BigInteger
arithmetic operations will utilize the long arithmetic built into the C++ language to perform operations on
single (base ) digits, and build up the standard arithmetic operations (add, subtract, multiply) out of these
(base ) digit operations. The reason we chose to be a power of 10 is to facilitate the conversion between
base 10 and base . In the case = 2, we have = 100, each base digit consists of 2 base 10 digits.
Base 100 digits = {00, 01, 02, … … … , 97, 98, 99}
The 52-digit base 10 number
= 6523485630758234007488392857982374523487612398700554,
(too large for any built-in C++ data type) becomes the following List of 26 base 100 digits.
= (65 23 48 56 30 75 82 34 00 74 88 39 28 57 98 23 74 52 34 87 61 23 98 70 05 54)
where we have separated digits by a space for the sake of readability. The same number in base 1,000 (i.e.,
= 3) would have 18 digits:
= (006 523 485 630 758 234 007 488 392 857 982 374 523 487 612 398 700 554),
and in base 1,000,000,000 ( = 9) it would have 6 digits:
= (006523485 630758234 007488392 857982374 523487612 398700554).
Observe that to obtain the base 10 representation of such a number, we can merely concatenate the base 10
digits of each of its base digits, then strip off any leading zeros. To go in the opposite direction and parse
a string of base 10 digits into a List of base digits, we can separate the string into groups of characters,
working from right to left. The final, leftmost, base digit may be parsed from fewer than characters.
In all of these Lists, we regard the front as being the right end, and the back as the left. With this convention,
the List index of a base digit is the corresponding power on . Thus
2
= (−1 −2 ⋯ ⋯ ⋯ 2 1 0)
represents the number
= −1
−1 + −2
−2 + ⋯ ⋯ ⋯ + 2
2 + 1
1 + 0
0.
It is instructive at this point to do some arithmetic examples using the above representation. To illustrate,
we take = 2, so = 100.
Example
carry: 1 1 −1
(35 57 97) (35 57 97)
+ (14 90 82) − (14 90 82)
(50 48 79) (20 67 15)
As we can see, it is very useful to think of a borrow in subtraction as nothing more than a negative carry.
One checks easily that in base 10: 355797 + 149082 = 504879 and 355797 − 149082 = 206715.
Another way to do these examples is to add and subtract Lists as vectors, then "normalize" the results, by
working from right to left in each vector, carrying and borrowing as needed to obtain a List of longs x in
the range 0 ≤ < , i.e., base digits.
Example
(35 57 97) (35 57 97)
+ (14 90 82) − (14 90 82)
(49 147 179) (21 − 33 15)
carry: 1 1 0 −1 0 0
normalize: (49 147 179) (21 − 33 15)
−100 − 100 100
result: (50 48 79) (20 67 15)
The reader is urged at this point to do a large number of such examples, since these are exactly the
algorithms needed to perform BigInteger addition and subtraction. The subtraction example above (in
particular the value −33) illustrates why it is useful to use long instead of unsigned long as our List
element data type. It allows us to do signed arithmetic at the level of each base digit. You should also
attempt to do some multiplication problems in this representation. When multiplying, it is necessary for
each digit in the first BigInteger to multiply each digit in the second BigInteger. If and are two such
digits, then 0 ≤ < and 0 ≤ < , hence 0 ≤ < 2. In order to guarantee that this product is always
computable in type long, we must have 2 no larger than the maximum possible long value, i.e.
2 ≤ 263 − 1
and therefore
≤ √263 − 1 = 3,037,000,499.97 …
The largest such that is also a power of 10 is = 1,000,000,000 = 109, which explains why the power
on 10 must be in the range 1 ≤ ≤ 9.
3
BigInteger ADT Specifications
The BigInteger ADT will be implemented in files BigInteger.h and BigInteger.cpp. Following our standard
practice, BigInteger.h will contain the definition of class BigInteger, along with prototypes of member
functions, as well those of overloaded operators. The file BigInteger.h is provided on the webpage under
Examples/pa6, and should be submitted unaltered with your project. All functions and operators in this
file will be implemented by you in BigInteger.cpp. (The one exception is the destructor, which is
commented out and marked as optional.)