- Problem 2 Designing Implementing Powerful Superint Class On Most Machines The Data Type Long Is Stored Using 64 Bits 1 (119.41 KiB) Viewed 24 times
Problem 2 Designing & Implementing Powerful SuperInt Class On most machines, the data type long is stored using 64 bits, which means that the largest positive value of type long is 263-1, or 9,223,372,036,854,775,807. While this number seems enormous, there are some applications that require even larger integers. For example, if you were asked to compute the number of possible arrangements for 2/5 a deck of 52 cards, you would need to calculate 52!, which works out to be: 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824, 000,000,000,000 If you are solving problems involving integer values on this scale (which come up often in cryptography, for example), you need to use a software package that provides extended-precision arithmetic, in which large integers are represented in a form that allows them to grow dynamically. Although there are more efficient techniques for doing so, one strategy for implementing extended-precision arithmetic is to store the individual digits in a linked list. In such representations, it is conventional mostly because it makes implementing arithmetic operators easier to arrange the linked list so that the units digit comes first, followed by the tens digit, then the hundreds digit, and so on. Thus, to represent the number 1729 as a linked list, you would arrange the linked-list cells in the following order: Read number in this direction In C++, it is almost always appropriate to encapsulate this sort of pointer-based structure inside a class definition so that the class can take care of memory management issues. Here, the best thing to do would be to define a class called SuperInt that uses this linked list representation internally to represent an arbitrarily large interface. A part of that interface appears on the following part. A complete interface would, of course, include other methods including the arithmetic operators, but the constructor, destructor, and toString methods shown in the figure offer at least a starting point. ent erere2
Partial listing of an interface to support extended-precision integers: /* ★ File: superint.h * * This interface exports the SuperInt class, which makes it * possible to represent integers of arbitrary magnitude. */ #ifndef_superint_h #define _superint_h #include <string> class SuperInt { public: /* * Constructor:Super Int * Usage: SuperInt superint(str); * Creates a new Super Int from a string of decimal digits, * which may begin with a minus sign to indicate a negative value. */ SuperInt(std::string str); * Destructor: -SuperInt * Usage: (usually implicit) * Frees the memory used by a SuperInt when it goes out of scope. */
*/ -SuperInt(); /* * Method: toString * Usage: string str = superint.toString(); * Converts a SuperInt object to the correspond */ std::string toString(); .. more methods not described here... private: ... the contents of the private section go here... }; #endif Here are a few details about our expectations for your solutions: 1. Write the private section for the superint.h, which must include whatever structure definitions and instance variables you need to represent an integer in this linked-list-of-digits form. 2. Write the superint.cpp file necessary to implement the constructor, destructor, and toString methods as defined in the interface. 3. Extend the superint.h and superint.cpp to support operator + and * for addition and multiplication, respectively. 4. Write the main.cpp to test and verify your implementation by applying your SuperInt class to generate a table showing the value of n! for all values of n string. PA++ Assment
between 0 to 52, inclusive. In writing your answer to this problem, you should keep the following points in mind: 1. Your internal representation for SuperInt must use the Linked List format specified in the problem description. 2. As implied by the comments for the constructor, the value stored in a SuperInt can be either positive or negative. As a result, your internal data structure will have to include an instance variable to store the sign of the value along with the linked list of digits. The fact that the value is signed will also affect your implementation of toString to ensure that negative values are preceded by a negative sign. 3. You should give at least some thought as to how you will represent the SuperInt corresponding to the integer 0. In particular, you should make sure that calling toString on a zero value returns the string "0" rather than the empty string. 4. You can implement the arithmetic operators by simulating what you do if you perform these calculations by hand. Addition, for example, requires you to keep track of the carrier from one digit position to the next. Multiplication is a bit more challenging, but is still straightforward to implement if you find the right recursive decomposition. Assig