Project#5 : BigNum

This project builds a class called BigNum which can be used to define very large numbers, ie infinite precision arithmetic.  A normal int can only hold 9 digits and a long long can only hold 18 or so digits.  This class can hold as many digits as the memory can handle. We will use a linked list to contain the digits.  Even though the method we will implement is is not particularly efficient (uses way too much memory and is somewhat slow) it is nice practice for working with linked list. For simplicity , our linked list will contain the large number by storing one digit per node.  Consider the integer 2957.  When a BigNum data type is loaded with this value it will be turned into as linked list with header as follows. The blue rectangles are pointer variables.

 

 

 

 

 

Note the first node is a header node that is not part of the number proper.  We will keep the length of the list in its digit attribute.  The remaining of the list is in reverse order to the number.  The last pointer will point to the last node.   The reverse and last node ptr will allow us to add two linked lists easily.

Below is the .h file I want you to use to build this class.  It has all the methods that you need to complete this project.  You need to implement the first four methods and test carefully BEFORE you work on the remaining ones.

#pragma once
#include <iostream>
using namespace std;
class BigNum
{
 // note that storing 1 digit per node is extreemly
 // inefficient. This can easily be fix later if we desire.
 struct Node {// Will store 1 digit per node
   int _d;// the int makes more sence if we store a lot of digits
   Node * _next;
   Node(int d) :_d(d),_next(nullptr) {};
 };
 Node * header;//uses a header node but no trailer
 Node * last;// points to last digit in the linked list
private:
 void Rev(Node * lst);// Private recursive function for printing backwards
 void AddDigit(int d);// Private method to add a digit node on the end of the list
public:
 BigNum();//default constructor. Creates empty list with just the header node, value 0
 BigNum(long long);//construct the linked list for int (allows 18 digits)
 ~BigNum();// The destructor
 void Print();// just calls the private function Rev to print the list in reverse
 BigNum(const BigNum & bn);// this is the copy constructor
 void Add(const BigNum &, const BigNum &);// add A and B to the object , destroying the object first
 // Note we could have done something like Add(const BigNum & A) and add A to the object putting it
 // back in the object. A cooler way to do this would be to use an overloaded + and assignment but
 // this will suffice for now. If we get time maybe we can do this.
//Note: the fact that the BigNum linked lists are reversed it
// is much easier to add them. 
// int carry=0;
// Repeat until only one list has remaining digits.
// Just start with the first value node in two linked 
// lists stored in A and B and and add the two digits from these nodes + carry.
// If there is a carry (ie >10) then set carry to 1 else
// set carry to 0. Take the least significant digit of this sum
// and create a new node with this value. Add the new node to the
// result object, say C. 
// end_repeat
 // now add carry to the next digit from the remaining list, creating
 // a new sum and carry. Do this until the end of the remaining list.
};

When the above class is working properly you may begin on the following.  First create a file called data.txt and store it in the project directory that contains the .cpp files. In this file place 8 integers ( of varying lengths) ,  two integers per line.   In your main program you will read these integers using cin from this file (using the file redirection method that we previously discussed when working with the UVa Judge).  Each pair of integers is to be converted to BigNums , added together and then printed out using the BigNum Print() method.  Here is an example data.txt file and its resulting output. Note the format of the output that is expected.  Read pairs of integers until the end of the file.

example data.txt 
2 3
12 9
123 999
2343 99989

example output
2 + 3 = 5
12 + 9 = 21
123 + 999 = 1122
2343 + 99989 = 102332

 

 

Comments are closed.