Programming Languages assignment VI

Assignment VI

Due date : Tuesday November 20
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.