1. Submission deadline: 11:59pm, Saturday, Nov. 7, 2015
2. [NEW]There are some revision on bigint.h and main.cpp. Please use the latest version for your assignment. (Thanks to Brian So.)
Normally, computers use storage of a certain size to store primitive data types. For example, on x86 PCs, "int" (integer) is of 4 bytes, meaning that it can only represent any integer ranging from -2^31 to 2^31-1 only. If we want to handle bigger integers out of this range without loss of precision, we have to introduce a new abstract data type (ADT), Big Integer. With this ADT, we can manipulate integers of any size. In this assignment, you will implement the ADT named BigInt which supports all the essential operations of integers for arbitrary large positive or negative integers without overflowing.
To implement BigInt, we need two fields, a vector of “unsigned short” (1 byte) for the absolute value and a “char” for the sign:
classBigInt {
// public functions here
private:
vector<unsigned short> abs_value;
char sign;
};
The vector abs_value is able to expand depending on the size of the integer. The way is to use a polynomial expression in terms of a0+a1*x+a2*x^2+..., where 0<=ai<x are the coefficients kept in the vector. In this problem, we choose the base of 100, because it can be stored in the unsigned short and is simple to manipulate (with some sacrifice in storage as compared with the base of 128). As an example, the big integer “12345678” may be expressed as 12*100^3+34*100^2+56*100+78, and hence it is stored as a vector of <12, 34, 56, 78> as shown below:
| 12 | 34 | 56 | 78 |
As for the sign, we use ‘+’ to represent a positive number, and ‘-’ to represent a negative number.
1. You must use the template of class BigInt that we provide. Note that you can add your own helper private methods if needed. Public member functions are reserved for the users to call. The header file bigint.h is provided.
2. There are 4 ways to construct BigInt:
a. DefaultNo parameter can be passed. The default value of the BigInt should be 0.
Usage example:BigInt bi;b. From a string
A null-terminated string can be passed.
Usage example:BigInt bi(“-1234567”);c. From an integer
An integer can be passed.
Usage example:BigInt bi(-23);d. From a BigInt
A BigInt can be passed.
Usage example:BigInt bi(bi2);
3. There are two public functions in BigInt, namely from_stringand to_string, which convert a BigInt to a null-terminated string, and vice versa, explained below:
a.
bool from_string(const char*)converts a string into the BigInt object. If the string is valid, it will be parsed and stored in the object, and then return true. Otherwise, false will be returned. Note that a valid string means that it contains only digits (0-9) with leading ‘-’ (for negative integer), or leading ‘+’ or nothing (for positive integer).b.
void to_string(char*)outputs a readable string according to current data in the object. If the BigInt is possitive, no leading '+' should be output. Note that all strings must be null-terminated.
4. To achieve all the operations of BigInt, you need to overload the following operators. If in doubt, please refer to integer primitive type operations:
| No. | Operator(s) | Remark |
| 1 | + |
You need to implement three types of addition operations, BigInt+BigInt, BigInt+int and int+BigInt. The returned type should be BigInt. |
| 2 | - |
The requirements are similar to entry <1>. |
| 3 | * |
The requirements are similar to entry <1>. |
| 4 | / |
The requirements are similar to entry <1>. |
| 5 | % |
% is the one similar to integer mod operation for its primitive counterpart. The requirements are similar to entry <1>. |
| 6 | = |
You need to implement both BigInt=BigInt and BigInt=int. The returned type should be &BigInt to support concatenation. |
| 7 | ++, -- |
You need to implement both BigInt++ (or BigInt--) and ++BigInt (or --BigInt). The returned type should be &BigInt. |
| 8 | >, >= |
You need to implement the comparison between two BigInts, or a BigInt and an integer type. It returns either true or false. |
| 9 | >>, << |
These two are the bit shifting operators. Note that as the shifting value may be large, it should be represented as BigInt. The returned type should be BigInt. |
| 10 | >>, << |
These two are the input and output operators. The returned type should be istream& (or ostream&) to support concatenation. |
5. We have provided you a main.cpp for your basic testing only. You may need to come up with your own testing program. Note that we will use our own testing program to grade your program.
6. Please submit your bigint.cpp and bigint.h to us (you should write it in two files). If you have a good tester program for us to consider, please also submit it. This will help us understand how your program works and some of the unique features you have implemented.
1. The correct implementation of the two helper protected methods, i.e. from_string(const char*) and to_string(char*) will worth 10 points.
2. Each of the correct overloaded operators would worth 5 points.
In the basic part above, you only need to implement all the operators without efficiency consideration. For example, there are several ways to implement integer multiplication and division. Let’s take multiplication as an example. The simplest but inefficient one is to obtain the result based on multiple additions. For example, if we want to calculate 4*5, we can add 4 (or 5) for 5 times (or 4 times). Though you get the result with full basic credits, this kind of method is not efficient enough. Division can be similarly but inefficiently done with subtraction.
If you can implement the operations (not limited to multiplication and division) in a much more efficient way, you can get a maximum of 20 bonus points for them. Please explain your approaches in README.