Hey all
I have been writing my own implementation of a BigInt class and I think I have most of it down. I am using a vector<int> container for my number. I'm curious to what you guys think about. This is my first program using 1000+ lines of code. Please fell free to point out anything I'm doing wrong or if any of it is confusing. I'm including the code as attachments as well so you don't have to copy and paste it. At present I have 12 warnings from my compiler possible loss of data when converting from size_t to int and I'm not sure yet how I want to fix that. Any suggestions on that would be helpful.
Thanks
Nathan Oliver
NumberClass.h
//**************************************************************************//
// This program is free software: you can redistribute it and/or modify //
// it under the terms of the GNU General Public License as published by //
// the Free Software Foundation, either version 3 of the License, or //
// (at your option) any later version. //
// //
// This program is distributed in the hope that it will be useful, //
// but WITHOUT ANY WARRANTY; without even the implied warranty of //
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the //
// GNU General Public License for more details. //
// //
// You should have received a copy of the GNU General Public License //
// along with this program. If not, see <http://www.gnu.org/licenses/>. //
// //
// Copyright © 2010 by Nathan Oliver, email: nathanoliver60097@hotamil.com //
//**************************************************************************//
// inclusion guarding
#ifndef NUMBERCLASS_H
#define NUMBERCLASS_H
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>
class Number
{
public:
// constructors
Number();
Number(int);
Number(unsigned int);
Number(char *);
Number(std::string);
Number(std::vector<int>, int);
// copy constructor
Number(const Number &);
// destructor
~Number() {};
// get functions
int GetNumberAsInt(); // return as a int if possible otherwise returns 0 and flags error
std::string GetNumber();
int GetSign(); // reuturns true if negative
bool GetToBig(); // returns true if GetNumberAsInt fails
// make functions
Number MakeNegative();
// math functions
Number pow(int) const;
bool PrimeCheck() const;
// ouput
friend std::ostream & operator<<(std::ostream &, Number &);
friend std::ofstream & operator<<(std::ofstream &, Number &);
// input
friend std::istream & operator>>(std::istream &, Number &);
friend std::ifstream & operator>>(std::ifstream &, Number &);
// math operators
Number operator=(const Number &);
Number operator=(const int &);
Number operator=(const unsigned int &);
Number operator+(const Number &) const;
Number operator+(const int &) const;
Number operator+(const unsigned int &) const;
Number operator+=(const Number &);
Number operator+=(const int &);
Number operator+=(const unsigned int &);
Number operator-(const Number &) const;
Number operator-(const int &) const;
Number operator-(const unsigned int &) const;
Number operator-=(const Number &);
Number operator-=(const int &);
Number operator-=(const unsigned int &);
Number operator*(const Number &) const;
Number operator*(const int &) const;
Number operator*(const unsigned int &) const;
Number operator*=(const Number &);
Number operator*=(const int &);
Number operator*=(const unsigned int &);
Number operator/(const Number &) const;
Number operator/(const int &) const;
Number operator/(const unsigned int &) const;
Number operator/=(const Number &);
Number operator/=(const int &);
Number operator/=(const unsigned int &);
Number operator%(const Number &) const;
Number operator%(const int &) const;
Number operator%(const unsigned int &) const;
Number operator%=(const Number &);
Number operator%=(const int &);
Number operator%=(const unsigned int &);
// increment and decrement operators
Number operator++();
Number operator++(int);
Number operator--();
Number operator--(int);
// compareison operators
bool operator >(const Number &) const;
bool operator >(const int &) const;
bool operator >(const unsigned int &) const;
bool operator >=(const Number &) const;
bool operator >=(const int &) const;
bool operator >=(const unsigned int &) const;
bool operator <(const Number &) const;
bool operator <(const int &) const;
bool operator <(const unsigned int &) const;
bool operator <=(const Number &) const;
bool operator <=(const int &) const;
bool operator <=(const unsigned int &) const;
bool operator ==(const Number &) const;
bool operator ==(const int &) const;
bool operator ==(const unsigned int &) const;
bool operator !=(const Number &) const;
bool operator !=(const int &) const;
bool operator !=(const unsigned int &) const;
private:
// private divied helper function
Number divied(const Number &, Number &);
// private data
std::vector<int> data;
size_t length;
int sign; // either -1 or 1
bool toBig;
bool DivdByZero;
};
#endif
NumberClass.cpp
#include "NumberClass.h"
#include <algorithm>
bool makeNeg = false; // used by functions to determin if the result should be negative
bool makePos = false; // used by functions to determin if the result should be positive
// should be changed but works for now
// constructors
Number::Number()
{
std::vector<int> data;
length = 0;
sign = 1;
toBig = false;
DivdByZero = false;
}
Number::Number(int number)
{
DivdByZero = false;
toBig = false;
sign = 1;
if(number < 0)
{
number *= -1;
sign = -1;
}
if (number == 0)
{
data.push_back(0);
length = 1;
}
// this loop store the number in reverse order in the vector.
// this is done for ease of later functions.
while (number > 0)
{
data.push_back(number % 10);
number /= 10;
}
length = data.size();
}
Number::Number(unsigned int number)
{
DivdByZero = false;
toBig = false;
sign = 1;
if (number == 0)
{
data.push_back(0);
length = 1;
}
// this loop store the number in reverse order in the vector.
// this is done for ease of later functions.
while (number > 0)
{
data.push_back(number % 10);
number /= 10;
}
length = data.size();
}
Number::Number(char * number)
{
DivdByZero = false;
toBig = false;
sign = 1;
std::vector<int> temp;
if (number[0] == '-')
{
number++;
sign = -1;
}
while(*number)
{
if (*number < '0' || *number > '9')
break;
temp.push_back(*number - '0');
number++;
}
length = temp.size();
for (int i = length - 1; i >= 0; i--)
{
data.push_back(temp[i]);
}
}
Number::Number(std::string number)
{
DivdByZero = false;
toBig = false;
sign = 1;
if (number[0] == '-')
{
sign = -1;
number.erase(number.begin());
}
length = number.size();
for (int i = length - 1; i >=0; i--)
{
if (number[i] < '0' || number[i] > '9')
break;
data.push_back(number[i] - '0');
}
}
Number::Number(std::vector<int> number, int neg)
{
for (int i = number.size() - 1; i > 0; i--)
{
if (number[i] != 0)
break;
if (number[i] == 0)
number.pop_back();
}
data = number;
length = number.size();
sign = neg;
toBig = false;
DivdByZero = false;
}
// copy constructor
Number::Number(const Number & number)
{
data = number.data;
sign = number.sign;
length = number.length;
}
// get functions
int Number::GetNumberAsInt()
{
int number = 0;
if (length > 10)
{
toBig = true;
return 0;
}
for (int i = length - 1; i >= 0; i--)
{
number *= 10;
number += data[i];
}
if (sign == -1)
number *= sign;
return number;
}
std::string Number::GetNumber()
{
char * temp = new char[length + 1];
int i = 0, j = 0;
if (sign == -1)
{
temp[0] = '-';
j = 1;
}
for (i = length - 1; i >= 0; i--, j++)
{
temp[j] = '0' + data[i];
}
if (sign == -1)
temp[length + 1] = '\0';
else
temp[length] = '\0';
std::string value(temp);
return value;
}
int Number::GetSign()
{
return sign;
}
bool Number::GetToBig()
{
return toBig;
}
// make functions
Number Number::MakeNegative()
{
sign = -1;
return *this;
}
// math functions
Number Number::pow(int exp) const
{
Number temp = *this;
if (exp == 0)
return Number(1);
if (exp == 1)
return *this;
for (int i = 1; i < exp; i++)
{
temp *= *this;
}
return temp;
}
bool Number::PrimeCheck() const
{
Number temp = *this;
if (sign == -1)
return false;
if (*this == 1 || *this == 2)
return true;
if ((*this % 2) == 0)
return false;
for (Number i = 3; i < (*this / 2); i += 2)
{
if ((*this % i) == 0)
return false;
}
return true;
}
// output functions
std::ostream & operator <<(std::ostream & stream, Number & number)
{
stream << number.GetNumber();
return stream;
}
std::ofstream & operator <<(std::ofstream & stream, Number & number)
{
stream << number.GetNumber();
return stream;
}
// input functions
std::istream & operator >>(std::istream & stream, Number & number)
{
std::string temp;
std::getline(stream, temp);
Number newNum(temp);
number = newNum;
return stream;
}
std::ifstream & operator >>(std::ifstream & stream, Number & number)
{
std::string temp;
std::getline(stream, temp);
Number newNum(temp);
number = newNum;
return stream;
}
// math operators
Number Number::operator =(const Number & number)
{
if (this == &number)
return *this;
data = number.data;
sign = number.sign;
toBig = number.toBig;
length = number.length;
return *this;
}
Number Number::operator =(const int & rhs)
{
if (*this == rhs)
return *this;
*this = Number(rhs);
return *this;
}
Number Number::operator =(const unsigned int & rhs)
{
if (*this == rhs)
return *this;
*this = Number(rhs);
return *this;
}
Number Number::operator +(const Number & number) const
{
int carry = 0;
std::vector<int>::const_iterator firstIt;
std::vector<int>::const_iterator secondIt;
std::vector<int>::const_iterator firstEnd;
std::vector<int>::const_iterator secondEnd;
std::vector<int> temp;
// this part is used to determin if the result should be negitive or positive
if (!makeNeg && !makePos)
{
if (sign == -1 && number.sign == 1)
{
if (*this > number)
makeNeg = true;
else
makePos = true;
return (number - *this);
}
if (sign == 1 && number.sign == -1)
{
if (*this > number)
makePos = true;
else
makeNeg = true;
return (*this - number);
}
}
// find the smaller number. that number gets added to the larger number
if (number.length > length || number.length == length)
{
firstIt = data.begin();
secondIt = number.data.begin();
firstEnd = data.end();
secondEnd = number.data.end();
}
else
{
firstIt = number.data.begin();
secondIt = data.begin();
firstEnd = number.data.end();
secondEnd = data.end();
}
while (firstIt != firstEnd)
{
carry = carry + *firstIt + *secondIt;
if (carry >= 10)
{
temp.push_back(carry - 10);
carry /= 10;
}
else
{
temp.push_back(carry);
carry = 0;
}
firstIt++;
secondIt++;
}
while (secondIt != secondEnd)
{
if (carry > 0)
{
carry = abs(carry + *secondIt);
if (carry >= 10)
{
temp.push_back(carry - 10);
carry /= 10;
}
else
{
temp.push_back(carry);
carry = 0;
}
}
else
{
temp.push_back(*secondIt);
}
secondIt++;
}
// if all addition is done and there is still carry add it to the end
if (carry)
temp.push_back(carry);
// gets rid of extra zeros. -100 + 100 is 000 so make it 0
for (int i = temp.size() - 1; i > 0; i--)
{
if (temp[i] != 0)
break;
if (temp[i] == 0)
temp.pop_back();
}
if (makeNeg)
{
makeNeg = false;
return Number(temp, -1);
}
if (makePos)
{
makePos = false;
return Number(temp, 1);
}
return Number(temp, sign);
}
Number Number::operator +(const int & number) const
{
return (*this + Number(number));
}
Number Number::operator +(const unsigned int & number) const
{
return (*this + Number(number));
}
Number Number::operator +=(const Number & number)
{
*this = (*this + number);
return *this;
}
Number Number::operator +=(const int & number)
{
*this = (*this + Number(number));
return *this;
}
Number Number::operator +=(const unsigned int & number)
{
*this = (*this + Number(number));
return *this;
}
Number Number::operator -(const Number & number) const
{
int carry = 0;
std::vector<int>::const_iterator firstIt;
std::vector<int>::const_iterator secondIt;
std::vector<int>::const_iterator firstEnd;
std::vector<int>::const_iterator secondEnd;
std::vector<int> temp;
// this part is used to determin if the result should be negitive or positive
if (!makeNeg && !makePos)
{
if (sign == 1 && number.sign == -1)
{
makePos = true;
return (*this + number);
}
if (sign == -1 && number.sign == 1)
{
makeNeg = true;
return (*this + number);
}
if (sign == -1 && number.sign == -1)
{
if (*this < number)
makePos = true;
else
makeNeg = true;
}
if (sign == 1 && number.sign == 1)
{
if (*this > number)
makePos = true;
else
makeNeg = true;
}
}
// find the smallest number. subtract that number from the larger number
if (number.length > length)
{
firstIt = data.begin();
secondIt = number.data.begin();
firstEnd = data.end();
secondEnd = number.data.end();
}
else
{
firstIt = number.data.begin();
secondIt = data.begin();
firstEnd = number.data.end();
secondEnd = data.end();
}
while (firstIt != firstEnd)
{
carry = *secondIt - carry - *firstIt;
if (carry < 0)
{
temp.push_back(10 - (-1 * carry));
// make carry 1 so it will be subtracted the next time around
carry = 1;
}
else
{
temp.push_back(carry);
carry = 0;
}
firstIt++;
secondIt++;
}
while (secondIt != secondEnd)
{
if (carry > 0)
{
carry = *secondIt - carry;
if (carry < 0)
{
temp.push_back(10 - (-1 * carry));
carry = 1;
}
else
{
temp.push_back(carry);
carry = 0;
}
}
else
temp.push_back(*secondIt);
secondIt++;
}
// if there still is carry add it to the end
if (carry > 0)
temp.push_back(carry);
// gets rid of extra zeros. 100 - 100 is 000 so make it 0
for (int i = temp.size() - 1; i > 0; i--)
{
if (temp[i] != 0)
break;
if (temp[i] == 0)
temp.pop_back();
}
if (makePos)
{
makePos = false;
return Number(temp, 1);
}
if (makeNeg)
{
makeNeg = false;
return Number(temp, -1);
}
return Number(temp, sign);
}
Number Number::operator -(const int & number) const
{
return (*this - Number(number));
}
Number Number::operator -(const unsigned int & number) const
{
return (*this - Number(number));
}
Number Number::operator -=(const Number & number)
{
*this = (*this - number);
return *this;
}
Number Number::operator -=(const int & number)
{
*this = (*this - Number(number));
return *this;
}
Number Number::operator -=(const unsigned int & number)
{
*this = (*this - Number(number));
return *this;
}
Number Number::operator *(const Number & number) const
{
int carry = 0, i = 0;
std::vector<int>::const_iterator firstIt;
std::vector<int>::const_iterator secondIt;
std::vector<int>::const_iterator firstEnd;
std::vector<int>::const_iterator secondEnd;
std::vector<int>::const_iterator secondStart;
std::vector<int> temp;
std::vector<Number> steps;
Number returner = 0;
if (number == 0)
return Number(0);
if (number == 1)
return *this;
if (sign == -1 && number.sign == 1)
makeNeg = true;
if (sign == 1 && number.sign == -1)
makeNeg = true;
if (number.length > length || number.length == length)
{
firstIt = data.begin();
secondStart = secondIt = number.data.begin();
firstEnd = data.end();
secondEnd = number.data.end();
}
else
{
firstIt = number.data.begin();
secondStart = secondIt = data.begin();
firstEnd = number.data.end();
secondEnd = data.end();
}
while (firstIt != firstEnd)
{
// skips multiplication if were multipling by 0
if (*firstIt == 0)
{
firstIt++;
i++;
continue;
}
// each new step starts at 10^i
if (i)
{
for (int j = 0; j < i; j++)
temp.push_back(0);
}
while (secondIt != secondEnd)
{
carry = *firstIt * *secondIt + carry;
if (carry >= 10)
{
temp.push_back(carry % 10);
carry /= 10;
}
else
{
temp.push_back(carry);
carry = 0;
}
secondIt++;
}
if (carry)
temp.push_back(carry);
secondIt = secondStart; // reset the iterator to the begining
steps.push_back(Number(temp, 1));
temp.clear();
firstIt++;
i++;
}
// after all the parts are found we have to add them up
std::vector<Number>::const_iterator end = steps.end();
for (std::vector<Number>::const_iterator it = steps.begin(); it != end; it++)
{
if (*it == 0)
continue;
returner = returner + *it;
}
if (makeNeg)
{
makeNeg = false;
return returner.MakeNegative();
}
return returner;
}
Number Number::operator *(const int & number) const
{
return (*this * Number(number));
}
Number Number::operator *(const unsigned int & number) const
{
return (*this * Number(number));
}
Number Number::operator *=(const Number & number)
{
*this = (*this * number);
return *this;
}
Number Number::operator *=(const int & number)
{
*this = (*this * Number(number));
return *this;
}
Number Number::operator *=(const unsigned int & number)
{
*this = (*this * Number(number));
return *this;
}
Number Number::operator /(const Number & number) const
{
Number carry, steps;
int i = 0;
std::vector<int> temp;
std::vector<int>::const_iterator firstIt = number.data.begin();
std::vector<int>::const_reverse_iterator secondIt = data.rbegin();
std::vector<int>::const_iterator firstEnd = number.data.end();
std::vector<int>::const_reverse_iterator secondEnd = data.rend();
std::vector<int>::const_iterator firstStart = firstIt;
if (*this == 0)
return Number(0);
if (number == 0)
{
steps = 0;
steps.DivdByZero = true;
return steps;
}
if (number == 1)
return *this;
if (*this == number)
return Number(1);
if (number > *this)
return Number(0);
if (sign == -1 && number.sign == 1)
makeNeg = true;
if (sign == 1 && number.sign == -1)
makeNeg = true;
// this gets the first part to divied by
while (firstIt != firstEnd)
{
temp.push_back(*secondIt);
firstIt++;
secondIt++;
}
while (secondIt != secondEnd)
{
// add one more and start dividing
temp.push_back(*secondIt);
// re reverse to divide
reverse(temp.begin(), temp.end());
Number divisor(temp, 1);
steps *= 10;
steps += divisor.divied(number, carry);
temp.clear();
temp = carry.data;
// reverse so we can add the digit to the end
reverse(temp.begin(), temp.end());
secondIt++;
}
if (makeNeg)
{
makeNeg = false;
return steps.MakeNegative();
}
return steps;
}
Number Number::operator /(const int & number) const
{
return (*this / Number(number));
}
Number Number::operator /(const unsigned int & number) const
{
return (*this / Number(number));
}
Number Number::operator /=(const Number & number)
{
*this = (*this / number);
return *this;
}
Number Number::operator /=(const int & number)
{
*this = (*this / number);
return *this;
}
Number Number::operator /=(const unsigned int & number)
{
*this = (*this / number);
return *this;
}
// this is the same is as division and we just return carry instead
Number Number::operator %(const Number & number) const
{
Number carry, steps;
std::vector<int> temp;
std::vector<int>::const_iterator firstIt = number.data.begin();
std::vector<int>::const_reverse_iterator secondIt = data.rbegin();
std::vector<int>::const_iterator firstEnd = number.data.end();
std::vector<int>::const_reverse_iterator secondEnd = data.rend();
std::vector<int>::const_iterator firstStart = firstIt;
if (*this == number)
return Number(0);
if (*this == 1)
return Number(1);
if (*this < number)
return *this;
if (number == 1)
return Number(0);
if (number == 0)
{
steps = 0;
steps.DivdByZero = true;
return steps;
}
while (firstIt != firstEnd)
{
temp.push_back(*secondIt);
firstIt++;
secondIt++;
}
while (secondIt != secondEnd)
{
temp.push_back(*secondIt);
reverse(temp.begin(), temp.end());
Number divisor(temp, 1);
steps *= 10;
steps += divisor.divied(number, carry);
temp.clear();
temp = carry.data;
reverse(temp.begin(), temp.end());
secondIt++;
}
if (sign == -1)
return carry.MakeNegative();
return carry;
}
Number Number::operator %(const int & number) const
{
return (*this % Number(number));
}
Number Number::operator %(const unsigned int & number) const
{
return (*this % Number(number));
}
Number Number::operator %=(const Number & number)
{
*this = (*this % number);
return *this;
}
Number Number::operator %=(const int & number)
{
*this = (*this % Number(number));
return *this;
}
Number Number::operator %=(const unsigned int & number)
{
*this = (*this % Number(number));
return *this;
}
// increment and decrement operators
Number Number::operator ++()
{
if (data[0] < 9)
data[0]++;
else
*this += 1;
return *this;
}
Number Number::operator ++(int post)
{
Number temp(*this);
if (data[0] < 9)
data[0]++;
else
*this += 1;
return temp;
}
Number Number::operator --()
{
if (data[0] > 1)
data[0]--;
else
*this -= 1;
return *this;
}
Number Number::operator --(int post)
{
Number temp(*this);
if (data[0] > 1)
data[0]--;
else
*this -= 1;
return temp;
}
// comparrison operators
bool Number::operator >(const Number & number) const
{
if (sign == 1 && number.sign == -1)
return true;
if (sign == -1 && number.sign == 1)
return false;
if (length > number.length)
return true;
if (length < number.length)
return false;
for (int i = data.size() - 1; i >= 0; i--)
{
if (data[i] > number.data[i])
return true;
if (data[i] < number.data[i])
return false;
}
return false;
}
bool Number::operator >(const int & number) const
{
return (*this > Number(number));
}
bool Number::operator >(const unsigned int & number) const
{
return (*this > Number(number));
}
bool Number::operator >=(const Number & number) const
{
if (sign == 1 && number.sign == -1)
return true;
if (sign == -1 && number.sign == 1)
return false;
if (length > number.length)
return true;
if (length < number.length)
return false;
for (int i = data.size() - 1; i >= 0; i--)
{
if (data[i] > number.data[i])
return true;
if (data[i] < number.data[i])
return false;
}
return true;
}
bool Number::operator >=(const int & number) const
{
return (*this >= Number(number));
}
bool Number::operator >=(const unsigned int & number) const
{
return (*this >= Number(number));
}
bool Number::operator <(const Number & number) const
{
if (sign == 1 && number.sign == -1)
return false;
if (sign == -1 && number.sign == 1)
return true;
if (length > number.length)
return false;
if (length < number.length)
return true;
for (int i = data.size() - 1; i >= 0; i--)
{
if (data[i] > number.data[i])
return false;
if (data[i] < number.data[i])
return true;
}
return false;
}
bool Number::operator <(const int & number) const
{
return (*this < Number(number));
}
bool Number::operator <(const unsigned int & number) const
{
return (*this < Number(number));
}
bool Number::operator <=(const Number & number) const
{
if (sign == 1 && number.sign == -1)
return false;
if (sign == -1 && number.sign == 1)
return true;
if (length > number.length)
return false;
if (length < number.length)
return true;
for (int i = data.size() - 1; i >= 0; i--)
{
if (data[i] > number.data[i])
return false;
if (data[i] < number.data[i])
return true;
}
return true;
}
bool Number::operator <=(const int & number) const
{
return (*this <= Number(number));
}
bool Number::operator <=(const unsigned int & number) const
{
return (*this <= Number(number));
}
bool Number::operator ==(const Number & number) const
{
if (sign == 1 && number.sign == -1)
return false;
if (sign == -1 && number.sign == 1)
return false;
if (length > number.length)
return false;
if (length < number.length)
return false;
for (int i = data.size() - 1; i >= 0; i--)
{
if (data[i] > number.data[i])
return false;
if (data[i] < number.data[i])
return false;
}
return true;
}
bool Number::operator ==(const int & number) const
{
return (*this == Number(number));
}
bool Number::operator ==(const unsigned int & number) const
{
return (*this == Number(number));
}
bool Number::operator !=(const Number & number) const
{
if (sign == 1 && number.sign == -1)
return true;
if (sign == -1 && number.sign == 1)
return true;
if (length > number.length)
return true;
if (length < number.length)
return true;
for (int i = data.size() - 1; i >= 0; i--)
{
if (data[i] > number.data[i])
return true;
if (data[i] < number.data[i])
return true;
}
return true;
}
bool Number::operator !=(const int & number) const
{
return (*this != Number(number));
}
bool Number::operator !=(const unsigned int & number) const
{
return (*this != Number(number));
}
// private divisor function
// this does the actual divsion of the pairs of numbers in the chain.
// using brute froce method. max steps is 9
Number Number::divied(const Number & number, Number & carry)
{
Number temp;
Number second;
if (*this == 0)
return Number(0);
if (*this < number)
{
carry *= 10;
return Number(0);
}
for (Number i = 2; i < 10; i++)
{
temp = (i * number);
if (temp > *this)
{
temp = (i - 1);
second = (temp * number);
carry = (*this - second);
break;
}
if (temp == *this)
{
temp = i;
carry = 0;
break;
}
}
return temp;
}