Data types in Java and C++ (amongst other languages) are limited to a specified range. Even in most basic calculators, performing an operation with 9 or more digits will result in an error. Sometimes, though, you have to perform very large calculations. Wouldn’t it be nice if there were an ADT that can perform arbitrary calculations, and “grow” depending on the size of the number? Of course, Java has a class library that will do this for you (BigInt), and there is almost certainly one available in C++, as well. But what if you had to develop your own? Of course, this would mean you’d have to re-implement basic mathematical operations — which may turn out to be not so “basic” at all. In this project, I’ve developed a “Long Integer ADT” in C++. Because the code for this project is somewhat extensive, I will only post the header files and smaller source files. The full source code can be downloaded here.
The Implementation
We will use a doubly linked list to implement our ADT as this will provide us with the flexibility of moving forward and backward between nodes. This will be useful, considering that division starts from the most significant digit, while addition starts from the least significant digit. Thus, we will use a node which has a link to the left and right. Data will be represented in the node using only 4 digits. Note that I am not using operator overloading, but simply using methods.
Methods
Not all mathematical functions were employed. The following methods have been implemented:
- Addition
- Subtraction
- Multiplication
- Division
- Power
Doubly Linked List
Below, you will see the doubly linked list and its methods. Most of them are basic enough that they do not need explanation. The method getNumberOfDigits() returns the total number of digits in this Long Integer representation. Likewise, the method setNumberOfDigits( int _length ) is used to set the number of digits in this arbitrary number.
#include "Node.cpp"
#include <string>
#include <iostream>
#include <sstream>
using namespace std;
#ifndef DOUBLYLINKEDLIST_H_
#define DOUBLYLINKEDLIST_H_
class DoublyLinkedList
{
public:
DoublyLinkedList();
virtual ~DoublyLinkedList();
struct node * head;
struct node * tail;
struct node * get( int index );
struct node * getFirst();
struct node * getLast();
struct node * getNext( struct node * currentNode );
struct node * getPrev( struct node * currentNode );
void add( int index, int value );
void addFirst( int value );
void addLast( int value );
bool isEmpty();
void remove( int index );
int size();
int getNumberOfDigits();
void setNumberOfDigits( int _length );
string toString();
void print();
void empty();
private:
int length;
int no_of_digits;
int max_digits;
};
#endif /*DOUBLYLINKEDLIST_H_*/
Node
The next element we should look at is the node. This one is rather simple. We store the data, length of the data, the number of leading zeros, and links to the next and previous node.
struct node {
long int data;
int length;
int leadingZeros;
struct node * prev;
struct node * next;
node() {
data = 0;
prev = 0;
next = 0;
length = 0;
leadingZeros = 0;
}
};
Long Int
This next portion shows the Long Int header file. This class will utilize the doubly linked list to implement the Long Int ADT. Again, most of these functions are self-explanatory, with the exception of the following:
- getOverflow() – Calculates and returns the overflow. Since we are only storing 4 digits per node in the doubly linked list, if the value is more than 4 digits, this will be the overflow. We will usually add this overflow to a new node in the list.
- normalize() – Removes zeros from the beginning of a number (e.g. 00001234 = 1234).
- parse() – This method performs some initialization. It creates the doubly linked list, sets the number of digits variable, and adds the digits to nodes in the doubly linked list.
#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <math.h>
#include "DoublyLinkedList.h"
#ifndef LONGINT_H_
#define LONGINT_H_
using namespace std;
class LongInt
{
public:
LongInt();
LongInt( char sign, string value );
virtual ~LongInt();
char getSign();
LongInt add( LongInt _value );
LongInt sub( LongInt _value );
LongInt mult( LongInt _value );
LongInt div( LongInt _value );
LongInt pow( unsigned long int exponent );
bool isGreaterThan( LongInt _value );
void normalize();
DoublyLinkedList getList();
string getValue();
void setSign( char _sign );
void setValue( string _value );
void parse();
long int getOverflow( struct node * currentNode );
void print();
string toString();
private:
DoublyLinkedList * list;
char sign;
string value;
int max_digits;
LongInt add( LongInt operand1, LongInt operand2 );
LongInt sub( LongInt operand1, LongInt operand2 );
};
#endif /*LONGINT_H_*/
Usage
The above class allows us to use our Long Int ADT as such:
LongInt * num1 = new LongInt('+', "12345678901234567890");
LongInt * num2 = new LongInt('-', "98765432109876543210");
LongInt * addResult = num1->add( *num2 ); // Addition
LongInt * subResult = num1->sub( *num2 ); // Subtraction
LongInt * multResult = num1->mult( *num2 ); // Multiplication
LongInt * divResult = num1->div( *num2 ); // Division
Optimization
For optimization purposes, most of the base cases for each operation are taken care of before any calculations are made. If you believe I have left something out, please feel free to point it out in the comments.
Efficiency
Addition and subtraction may be performed relatively quickly, whereas multiplication, division, and power generally take more time to complete. The multiplication method can presumably be written more efficiently since, in the end, we are using a vector to add up partial products. The division algorithm, in my opinion, is already somewhat efficient, but due to the nature of the operation, it inevitably takes long to complete if very long numbers (e.g. 50+ digits long) are being divided. The power function uses 2*log(i) multiplication.
Conclusion
This project was pretty tricky to complete since there are so many cases to be handled in just these few basic mathematical operations. I especially had a difficult time as this was my first relatively big program written in C++. The toughest operation to implement was division, whereas addition, subtraction, and even multiplication were not that difficult (but did, nevertheless, require a great deal of attention). If you encounter any errors or are aware of mistakes that should be fixed or optimizations to be made, please feel free to share them in the comments section.
Tags: adt, long int, long integer, longint