bignum.cpp

This program is to handle all possible arithmetic operations (+, -, *, /, %) and logic operations (<

#include <iostream.h>
#include <string.h>
#define SIZE 120

class bigInt {
public:
	bigInt(char aBigInt[], bool negativeFlag = false, bool zeroFlag = false) { strcpy(a, aBigInt); setNegative(negativeFlag); setZero(zeroFlag); }
	bigInt() { clear(a); setNegative(false); setZero(true); }
	~bigInt() {};
	
	bool getNegative(void) { return negative; }
	bool getZero(void) { return zero; }
	void setNegative(bool negativeFlag) { negative = negativeFlag; }
	void setZero(bool zeroFlag) { zero = zeroFlag; }
	
	const bigInt& operator=(const bigInt& rhs);
	const bigInt& operator+(bigInt& b);
	const bigInt& operator*(bigInt& b);
	const bigInt& operator-(bigInt& b);
	const bigInt& operator/(bigInt& b);
	const bigInt& operator%(bigInt& b);
	const void operator+=(bigInt& b);
	const void operator*=(bigInt& b);
	const void operator-=(bigInt& b);
	const void operator/=(bigInt& b);
	const void operator%=(bigInt& b);
	const bool operator>(bigInt& b);
	const bool operator<(bigInt& b);
	const bool operator==(bigInt& b);
	const bool operator!=(bigInt& b);
	const bool operator>=(bigInt& b);
	const bool operator<=(bigInt& b);
	
	void getValue(char thisBigInt[]) {strcpy(thisBigInt, a); } // return a string which is equivalent to the number
	void setValue(char thisBigInt[]) {strcpy(a, thisBigInt); } // set string thisBigInt to the value of an instance
	int getLength() { return strlen(a); }
	char getDigit(int pos) { return a[pos]; } // return CHARACTER at position i
	void setDigit(int pos, char value) { a[pos] = value; } // set CHARACTER at position i to value
	void print() { for (int i = 0; i < getLength(); i++) cout << a[i]; }
	void reverse(void);
	void clear(char ar[]) { ar[0] = '0'; ar[1] = '\0'; }
	void fixArray(char ar[]);

private:
	char a[SIZE];
	bool negative;
	bool zero;
	//helper functions
	int value(char c) { return c - 48; } //convert a character into the digit form
	char represent(int k) { return (char)(k + 48); } //convert a digit into the character form
	int maximum(int a, int b) { return (a > b) ? a : b; }
};

void bigInt::fixArray(char ar[])
{
	int j = 0;
	int len = strlen(ar);
	while ((ar[j] == '0') && (j < len))
		j++;
	if (j == len)
		clear(ar);
	else {
		for (int i = 0; i < len - j; i++)
			ar[i] = ar[i + j];
		ar[len - j] = '\0';
	}
}

const bigInt& bigInt::operator=(const bigInt& rhs)
{
	if (this != &rhs) {			// check for self assignment
		negative = rhs.negative;
		zero = rhs.zero;
		strcpy(a, rhs.a);
	}
	return *this;	//enable cascading
}

//reverse a string
void bigInt::reverse(void)
{
	int len = getLength();
	for (int i = 0; i < len/2; i++) {
		char temp = a[i];
		a[i] = a[len-1-i];
		a[len-1-i] = temp;
	}
}

//========================================== Multiplication function ==============================//
const bigInt& bigInt::operator*(bigInt& b)
{
	int len1 = getLength(), len2 = b.getLength();
	int i = 0, j = 0;
	int carry[SIZE][SIZE];
	int r[SIZE][SIZE];

	//reverse 2 number for the convenience in computing
	reverse();
	b.reverse();
	
	//initialize carry[][] and r[][]
	for (i = 0; i <SIZE; i++)
		for (j = 0; j < SIZE; j++) {
			carry[i][j] = 0;
			r[i][j] = 0;
	}

	//fill digits into the array r, which is the temp table in multiplying 2 numbers
	for (i = 0; i < len2; i++) {
		
		for (j = 0; j < len1; j++) {
			
			int x = value(getDigit(j));
			int y = value(b.getDigit(i));
			if (j != 0) {

				r[i][j+i] = (x * y + carry[i][j+i-1]) % 10; // each digit is computed from the product of 2 digits from the operands and the carry from the previous computation
				carry[i][j+i] = (x * y + carry[i][j+i-1]) /10;
				
			}
			else {
				r[i][j+i] = x * y % 10;
				carry[i][j+i] = x * y / 10;
			}
			
		}
		r[i][len1+i] = carry[i][len1+i-1];
		
	}
	
	int carry1[SIZE]; //carry array for the final product
	int tempResult[SIZE]; //final product in digit form
	
	//initialize carry1[] and tempResult[]
	for (i = 0; i < SIZE; i++)
		carry1[i] = 0;
	for (i = 0; i < SIZE; i++)
		tempResult[i] = 0;

	//compute tempResult from the temp table
	for (i = 0; i < len1 + len2; i++) {
		for (j = 0; j < len2; j++)
			tempResult[i] += r[j][i];
		if (i == 0) {
			carry1[i] = tempResult[i] / 10;
			tempResult[i] = tempResult[i] % 10;
		}
		else {
			int temp = tempResult[i];
			tempResult[i] = (temp + carry1[i-1]) % 10;
			carry1[i] = (temp + carry1[i-1]) / 10;
		}
	}
	
	char result[SIZE];
	//convert the final product in digit form into character form
	for (i = 0; i < len1 + len2; i++)
		result[i] = represent(tempResult[i]);
	
	//check if there is a '0' at the beginning of the product
	if (value(result[len1 + len2 - 1]) == 0)
		result[len1 + len2 - 1] = '\0'; // if so, obmit it
	else
		result[len1 + len2] = '\0';
	
	//reverse the operands to get back the original value
	reverse();
	b.reverse();
	//reverse the final result in character form to obtain the correct order
	bigInt returnResult(result);
	returnResult.reverse();

	return returnResult;
}
//=================================================================================================//

//========================================== Addition function ====================================//
const bigInt& bigInt::operator+(bigInt& b)
{
	int len1 = getLength(), len2 = b.getLength();
	int i = 0;
	
	//reverse 2 number for the convenience in computing
	reverse();
	b.reverse();
			
	int numA[SIZE], numB[SIZE];
	int carry[SIZE]; //carry array for the sum
	int tempResult[SIZE]; //sum in digit form
	
	//initialize numA[] and numB[]
	for (i = 0; i < SIZE; i++) {
		numA[i] = 0;
		numB[i] = 0;
	}

	if (len1 > len2) {
		for (i = 0; i < len1; i++)
			numA[i] = value(getDigit(i));
		for (i = 0; i < len2; i++)
			numB[i] = value(b.getDigit(i));
		for (i = len2; i < len1; i++)
			numB[i] = 0;
	}
	else {
		for (i = 0; i < len1; i++)
			numA[i] = value(getDigit(i));
		for (i = 0; i < len2; i++)
			numB[i] = value(b.getDigit(i));
		for (i = len1; i < len2; i++)
			numA[i] = 0;
	}

	//initialize carry[] and tempResult[]
	for (i = 0; i < SIZE; i++)
		carry[i] = 0;
	for (i = 0; i < SIZE; i++)
		tempResult[i] = 0;

	int len = maximum(len1, len2);
	//compute tempResult
	for (i = 0; i < len + 1; i++) {
		tempResult[i] = numA[i] + numB[i];
		if (i == 0) {
			carry[i] = tempResult[i] / 10;
			tempResult[i] = tempResult[i] % 10;
		}
		else {
			int temp = tempResult[i];
			tempResult[i] = (temp + carry[i-1]) % 10;
			carry[i] = (temp + carry[i-1]) / 10;
		}
	}
	tempResult[len+1] = carry[len];
	
	char result[SIZE];
	//convert the final product in digit form into character form
	for (i = 0; i < len + 1; i++)
		result[i] = represent(tempResult[i]);
	
	//check if there is a '0' at the beginning of the product
	if (value(result[len]) == 0)
		result[len] = '\0'; // if so, obmit it
	else
		result[len + 1] = '\0';
	
	reverse();
	b.reverse();
	//reverse the final result in character form to obtain the correct order
	bigInt returnResult(result);
	returnResult.reverse();
	
	return returnResult;
}
//=================================================================================================//

//========================================== Subtraction function =================================//
const bigInt& bigInt::operator-(bigInt& b)
{
	int len1 = getLength(), len2 = b.getLength();
	int i = 0, j;
	bool negativeFlagOfResult = false;
	bool zeroFlagOfResult = false;
	
	int numA[SIZE], numB[SIZE];
	int carry[SIZE]; //carry array for the sum
	int tempResult[SIZE]; //sum in digit form
	
	char result[SIZE];
	//initialize result[]
	for (i = 0; i < SIZE; i++)
		result[i] = '0';

	//initialize numA[] and numB[]
	for (i = 0; i < SIZE; i++) {
		numA[i] = 0;
		numB[i] = 0;
	}

	if (*this > b) { //positive number
		negativeFlagOfResult = false;
		zeroFlagOfResult = false;
		reverse();
		b.reverse();
		for (i = 0; i < len1; i++)
			numA[i] = value(getDigit(i));
		for (i = 0; i < len2; i++)
			numB[i] = value(b.getDigit(i));
		for (i = len2; i < len1; i++)
			numB[i] = 0;
	}
	else if (*this < b) { //negative number
		negativeFlagOfResult = true;
		zeroFlagOfResult = false;
		reverse();
		b.reverse();
		for (i = 0; i < len1; i++)
			numB[i] = value(getDigit(i));
		for (i = 0; i < len2; i++)
			numA[i] = value(b.getDigit(i));
		for (i = len1; i < len2; i++)
			numB[i] = 0;
	}
	else {
		negativeFlagOfResult = false;
		zeroFlagOfResult = true;
		clear(result);
		bigInt returnResult(result, negativeFlagOfResult, zeroFlagOfResult);
		returnResult.reverse();
		return returnResult;
	}
	
	//initialize carry[] and tempResult[]
	for (i = 0; i < SIZE; i++)
		carry[i] = 0;