Homework 4 -- 91.201

Build a class HugeInt for unsigned integers of unbounded size.  Include arithmetic operators +, -, and optionally *. Implement an appropriate version of  "<<" for outputting an instance of HugeInt to an output stream. (The << operator must be implemented outside the class as a global function.  Furthermore, because it accesses a member variable of HugeInt, it must be a friend to HugeInt.  I'll explain this in class.  Don't miss class!)   Implement with the class vector from the standard template library.

Here's an example of the use of HugeInt:

HugeInt x(string("400000000000000000001"));
                 // calls the non-default constructor.
HugeInt y(string("700000000000000000005"));  // ditto
HugeInt z;       // calls the default constructor
z=x+y;
std::cout << z << endl;
                // causes 1100000000000000000006 to be
                // displayed on a single line of cout
z=y-x;
std::cout << z << endl;
                // causes 300000000000000000004 to be
                // displayed on a single line of cout
z=x-y;
std::cout << z << endl;
                // causes -1 to be
                // displayed on a single line of cout
z=x*y;          // * is for extra credit.
std::cout << z << endl;
       // causes
       // 280000000000000000000000000000000000000024
       // to be displayed on a single line of cout

This tester can be found here.

Use vectors of unsigned ints to represent HugeInts.   Find a skeletal definition of the class HugeInt here.

Each instance of HugeInt has in member variable value a vector of unsigned ints, each a decimal integer of 8 digits.  For example, given the definitions

HugeInt x(string("40000000000000001"));
HugeInt y(string("70000000000000005"));

the member variable value is as follows:

x.value[0]=1 // same as 00000001
x.value[1]=0 // same as 00000000
x.value[2]=4

y.value[0]=5 // same as 00000005
y.value[1]=0 // same as 00000000
y.value[2]=7

Use grade-school algorithms to do arithmetic, but instead of working in base (radix) 10, work in radix 10⁸.  For example, to add x and y to get result z, you must

1. Add x.value[0] and y.value[0].  z is (x.value[0]+y.value[0])%10⁸.   Carry to the next column (x.value[0]+y.value[0])/10⁸.
2. Add x.value[1] and y.value[1] and any carry from column 0.  z is (x.value[1]+y.value[1])%10⁸.   Carry to the next column (x.value[1]+y.value[1])/10⁸.
3. Add x.value[2] and y.value[2] and any carry from column 1.  z is (x.value[2]+y.value[2])%10⁸.   Carry to the next column (x.value[2]+y.value[2])/10⁸.

and so forth.  Encode this in a loop that adds the vectors' 0 cells (x.value[0] and y.value[0]) the first iteration, the 1 cells the second iteration, and so forth.  Handle the case where one of the operands has more cells than the other.

Multiplication is trickier than addition and subtraction, but it's your grade-school algorithm adapted for base 10⁸.  The basic idea is that for z=x*y,

z.value[i] = ((x.value[0]*y.value[i]) + (x.value[1]*y.value[i-1]) + (x.value[2]*y.value[i-2]) +...+ (x.value[i]*y.value[0]) + carry_from_previous_column) % 10⁸

carry_for_next_column = ((x.value[0]*y.value[i]) + (x.value[1]*y.value[i-1]) + (x.value[2]*y.value[i-2]) +...+ (x.value[i]*y.value[0]) + carry_from_previous_column) / 10⁸

Have fun!