Programming Languages assignment VI
The purpose of this assignment is to design a set of C++ functions to perform arbitrary precision arithmetic for integers and rational numbers. We want to be able to write: A = A * B + C * D; where A, B, C, and D each have more than 200 decimal digits. So we need to define the operators + and * accordingly. We also want to write: R = A / B; where R is defined to be a rational number, with A and B as its numerator and denominator respectively. We want to redefine the operator "/" accordingly (as well as the other arithmetic operations on rationals). To represent arbitrary precision integers, we can use either arrays of digits or lists of digits. You can use either data structure. The algorithms may be a tad simpler with arrays. In the description that follows, we speak of sequences of digits, and that means either representation. To represent rational numbers we use a pair of arbitrary precision integers. The algorithm for addition is similar to the paper and pencil method. You start from the least significant digits of the operands, add them, compute a carry if the result of this addition is greater than the base, and continue until you run out of digits. The algorithm for multiplication is also similar to the paper and pencil method: you multiply one operand by successive digits of the other operand, and each time you shift the first operand by one digit. However, unlike the paper and pencil method, you add each row as you go. So to implement multiplication you need to have addition, and one additional simple method that multiplies an arbitrary integer by a single digit. Each digit in this representation should have a large base, to minimize the total number of digits. A good choice is a large power of 10, because this will make the display of such numbers simpler. For example, if you use base 10,000 for each digit, then the product of two digits fits into 32 bits, and you can compute everything without overflow and without long arithmetic. For this assignment, design the classes Big_Integer and Rational, declare the arithmetic operators on each, provide a few constructors, and implement addition, multiplication, and an output method. Note that if the digits are a power of 10 you can just print the digits in sequence (as long as you make sure to fill in with zeroes if a given digit is less than 1000). Any other base would require more involved conversions. Once you have addition and multiplication for integers, the operations on rationals are trivial. However you will notice that there is an important aspect of rational numbers that we have not discussed: without division there is no way to reduce a rational to a simplest form. The division algorithm is quite complex, and I will send a version of it for next assignment, which you will use to complete the implementation of these classes. The output of your program should be the value of factorial (100) * 25 ^ 25 You can implement exponentiation with repeated multiplication, or else use the algorithm that we described in lecture 2.