Big Integer Implementation
Hey! I've been working on implementing a Big Integer class for a few days now (mostly because I'm finding it useful for Project Euler problems and because I've wanted to do so for a while). My basic aim right now is to make my implementation at least as fast as Python or Java in-built Big Integer classes. I do have to let you know that I'm not very good at writing object-oriented code and I've tried keeping my code as simple as I could/need.
Now obviously I can program a Modular Arithmetic class for problem solving instead (and in fact, I'm working on one!) but there's something different I get to achieve by implementing Big Integer.
Till now, I've implemented only construction, addition, subtraction and multiplication. I'd like to have my code reviewed and criticised on. If someone could suggest better ways of doing things, and I can understand how the implementation would work, I'd use it to optimise the operations. I'm omitting the multiplication part as I know it's not very optimal because of a badly implemented Karatsuba algorithm. Also note that I've had no exposure to programming something for Big Integers except for simply having read/seen about it on some sites or using it in Python.
Presently, the only two benchmarks I've performed are generating 100000(1e5) valid 100-digit Big Integers and simply finding their sum. This takes 0.0995400000 seconds. For the other benchmark, scroll to the bottom. Now, I don't know if that's good or bad but hopefully you guys will let me know. Also, the algorithm I use in addition and subtraction is the simple method taught at elementary school level. I also don't know of a way to check if my implementation is correct (the only way I think it is correct is by testing on hand some simple operations with small numbers). If there's some way to test my implementation, like a program I can run against mine, please do let me know. Also, if you have any comments on code style and documentation (yeah, I know I'm terrible, but hey, I'm trying!), do share your opinions too.
Thanks in advance!
Code:
/*
Written by: Aryan V S
Date: Tuesday 2020-04-07
*/
#ifndef BIG_INTEGER_H
#define BIG_INTEGER_H
#include <vector>
#include <string>
#include <initializer_list>
#include <type_traits>
#include <typeinfo>
#include <cassert>
#include <cmath>
class BigInt {
private:
/**
* std::vector that stores the digits of a Big Integer
* Least significant digits stored first
*
* A digit 'Digits [i]' is not stored as it's ASCII value (as expected in
* a vector of char) i.e. '1' is stored simply as 1 instead of it's ASCII
* value 49. This is done to make arithmetic operations faster. When the
* actual character value is needed (like in the to_string() method), simply
* '0' is added in each step of conversion
*/
std::vector <char> Digits;
/**
* std::bool that stores the sign of a Big Integer
* false -> negative
* true -> non-negative
*/
bool Sign;
public:
/**
* Constructs a Big Integer with default values
* Sign: true
* Number: 0
*/
BigInt ();
/**
* Constructs a Big Integer from primitive integer types
*/
template <typename T> BigInt (T);
/**
* Constructs a Big Integer from a string
* Valid:
* -> "-...." (negative)
* -> "....." (non-negative)
*/
BigInt (const std::string&);
BigInt (const char*);
/**
* Constructs a Big Integer from std::initialzer_list
* Valid:
* -> {-a,b,c,...} (negative)
* -> {a,b,c,....} (non-negative)
* All integers must be in the range [0,9]
*/
template <typename T> BigInt (const std::initializer_list <T>&);
/**
* Constructs a Big Integer from std::vector
* Valid:
* -> {-a,b,c,...} (negative)
* -> {a,b,c,....} (non-negative)
* All integers must be in the range [0,9]
*/
template <typename T> BigInt (const std::vector <T>&);
/**
* Copy Constructor
*/
BigInt (const BigInt&);
/**
* Copy Assignment
*/
BigInt& operator = (const BigInt&);
/**
* Move Constructor
*/
BigInt (BigInt&&);
/**
* Move Assignment
*/
BigInt& operator = (BigInt&&);
/**
* Output stream overload
*/
friend std::ostream& operator << (std::ostream&, const BigInt&);
/**
* Input stream overload
*/
friend std::istream& operator >> (std::istream&, BigInt&);
/* Relational Methods */
bool operator == (const BigInt&) const;
bool operator != (const BigInt&) const;
bool operator < (const BigInt&) const;
bool operator > (const BigInt&) const;
bool operator <= (const BigInt&) const;
bool operator >= (const BigInt&) const;
/* Arithmetic Methods */
BigInt& operator += (const BigInt&);
BigInt& operator -= (const BigInt&);
BigInt& operator *= (const BigInt&);
BigInt& operator /= (const BigInt&);
BigInt& operator %= (const BigInt&);
BigInt& operator &= (const BigInt&);
BigInt& operator |= (const BigInt&);
BigInt& operator ^= (const BigInt&);
BigInt& operator <<= (const BigInt&);
BigInt& operator >>= (const BigInt&);
BigInt& operator ++ ();
BigInt& operator -- ();
BigInt operator ++ (int);
BigInt operator -- (int);
BigInt operator + () const;
BigInt operator - () const;
/* Utility Methods */
/**
* Accessing digits
*/
const int& operator [] (int) const;
int& operator [] (int);
/**
* to_vector: Returns a vector containing the digits. If parameter is false, default order returned.
* If parameter is true, reversed order returned (i.e. most significant digits start first).
* Default order is the order originally stored i.e. from LSD to MSD
*/
std::vector <int> to_vector (bool) const;
/**
* to_string: Returns a string containing the digits. If parameter is false, default order returned.
* If parameter is true, reversed order returned (i.e. most significant digits start first).
* Default order is the order originally stored i.e. from LSD to MSD
*/
std::string to_string (bool) const;
/**
* size: Returns the number of digits in the Big Integer
*/
size_t size () const;
/**
* abs: Returns the absolute value of the Big Integer
*/
BigInt abs () const;
};
BigInt::BigInt ()
: Digits ({0})
, Sign (true)
{ }
template <typename T>
BigInt::BigInt (T Integer)
: Digits ()
, Sign (Integer >= 0) {
/// Only types like int, long long, etc are allowed
static_assert(std::is_integral <T>::value, "Construction requires Integer types");
Sign = Integer >= T(0);
do {
int Value = Integer % 10;
/// Types like char, wchar_t, etc fail the assertion
assert(Value >= 0 && Value <= 9);
Digits.emplace_back(Value);
Integer /= 10;
}
while (Integer != 0);
}
BigInt::BigInt (const std::string& Integer)
: Digits ()
, Sign (*Integer.begin() != '-') {
size_t N = Integer.size();
if (Sign) Digits.resize(N);
else Digits.resize(N - 1);
for (int i = N - 1; i >= !Sign; --i) {
assert('0' <= Integer [i] && Integer [i] <= '9');
Digits [N - i - 1] = Integer [i] - '0';
}
}
BigInt::BigInt (const char* Integer)
: BigInt ((std::string)Integer)
{ }
template <typename T>
BigInt::BigInt (const std::initializer_list <T>& Integer)
: Digits ()
, Sign (*Integer.begin() >= 0) {
/// Only types like int, long long, etc are allowed
static_assert(std::is_integral <T>::value, "Construction requires Integer types");
size_t N = Integer.size();
Digits.resize(N);
for (size_t i = 0; i < N; ++i) {
int Value = std::abs(*(Integer.end() - i - 1));
/// Types like char, wchar_t, etc fail the assertion
assert(Value >= 0 && Value <= 9);
Digits [i] = Value;
}
}
template <typename T>
BigInt::BigInt (const std::vector <T>& Integer)
: Digits ()
, Sign (*Integer.begin() >= 0) {
/// Only types like int, long long, etc are allowed
static_assert(std::is_integral <T>::value, "Construction requires Integer types");
size_t N = Integer.size();
Digits.resize(N);
for (size_t i = 0; i < N; ++i) {
int Value = std::abs(*(Integer.end() - i - 1));
/// Types like char, wchar_t, etc fail the assertion
assert(Value >= 0 && Value <= 9);
Digits [i] = Value;
}
}
BigInt::BigInt (const BigInt& BigInteger)
: Digits (BigInteger.Digits)
, Sign (BigInteger.Sign)
{ }
BigInt& BigInt::operator = (const BigInt& BigInteger) {
Digits.assign(BigInteger.Digits.begin(), BigInteger.Digits.end());
Sign = BigInteger.Sign;
return *this;
}
BigInt::BigInt (BigInt&& BigInteger)
: Digits (std::move(BigInteger.Digits))
, Sign (std::move(BigInteger.Sign))
{ }
BigInt& BigInt::operator = (BigInt&& BigInteger) {
Digits.assign(BigInteger.Digits.begin(), BigInteger.Digits.end());
Sign = BigInteger.Sign;
return *this;
}
std::ostream& operator << (std::ostream& stream, const BigInt& BigInteger) {
if (!BigInteger.Sign) stream << '-';
for (auto Iterator = BigInteger.Digits.rbegin(); Iterator != BigInteger.Digits.rend(); ++Iterator)
stream << int(*Iterator);
return stream;
}
std::istream& operator >> (std::istream& stream, BigInt& BigInteger) {
std::string Integer;
stream >> Integer;
BigInteger = BigInt(Integer);
return stream;
}
inline bool BigInt::operator == (const BigInt& R) const {
/// If numbers have different sign, they cannot be equal
if (Sign != R.Sign)
return false;
/// If the number of digits in the two numbers is different, they cannot be equal
if (Digits.size() != R.Digits.size())
return false;
/// The number are of same sign and have the same number of digits
/// To test for equality, each digit must be same
for (size_t i = 0; i < Digits.size(); ++i)
if (Digits [i] != R.Digits [i])
return false;
return true;
}
inline bool BigInt::operator != (const BigInt& R) const {
return !(*this == R);
}
inline bool BigInt::operator < (const BigInt& R) const {
/// First is -ve, Second is non -ve
if (!Sign && R.Sign)
return true;
/// First is non -ve, Second is -ve
if (Sign && !R.Sign)
return false;
/// Both are non -ve
if (Sign && R.Sign) {
/// First is less than Second in terms of number of digits
if (Digits.size() < R.Digits.size())
return true;
/// First is greater than Second in terms of number of digits
else if (Digits.size() > R.Digits.size())
return false;
/// First and second have the same number of digits
else {
size_t N = Digits.size();
/// Start check from MSD
for (int i = N - 1; i >= 0; --i) {
if (Digits [i] > R.Digits [i])
return false;
if (Digits [i] < R.Digits [i])
return true;
}
}
}
/// Both are -ve
else {
if (Digits.size() < R.Digits.size())
return false;
else if (Digits.size() > R.Digits.size())
return true;
else {
size_t N = Digits.size();
/// Start check from MSD
for (int i = N - 1; i >= 0; --i) {
if (Digits [i] > R.Digits [i])
return true;
if (Digits [i] < R.Digits [i])
return false;
}
}
}
/// All digits are same
return false;
}
inline bool BigInt::operator > (const BigInt& R) const {
return !(*this <= R);
}
inline bool BigInt::operator <= (const BigInt& R) const {
return *this < R || *this == R;
}
inline bool BigInt::operator >= (const BigInt& R) const {
return *this > R || *this == R;
}
BigInt& BigInt::operator += (const BigInt& R) {
size_t MinSize = std::min(Digits.size(), R.Digits.size());
size_t MaxSize = std::max(Digits.size(), R.Digits.size());
bool isLesser = *this < R;
/// Opposite signs
if (Sign ^ R.Sign) {
BigInt L;
bool Swapped = false;
/// Case: Left(L:(-ve)), Right(R:(+ve))
if (isLesser) {
/// Case: If abs(L) is lesser or equal to R, sum is non -ve
if (this->abs() <= R) {
L = *this;
*this = R;
Swapped = true;
}
/// Case: If abs(L) is greater than R, sum is -ve
else { /* Nothing to do here. Everything is good! */ }
}
/// Case: Left(+ve), Right(-ve)
else {
/// Case: If L is lesser than abs(R), sum is -ve
if (*this < R.abs()) {
L = *this;
*this = R;
Swapped = true;
}
/// Case: If L is greater or equal abs(R), sum is non -ve
else { /* Nothing to do here. Everything is good! */ }
}
assert(Digits.size() == MaxSize);
std::function <void(const BigInt&)> Subtract = [&] (const BigInt& X) {
size_t i = 0;
bool Borrow = false;
for (; i < MinSize; ++i) {
if (Digits [i] < X.Digits [i])
Borrow = true;
else
Borrow = false;
Digits [i] = (Borrow ? 10 + Digits [i] - X.Digits [i] : Digits [i] - X.Digits [i]);
if (Borrow) {
size_t j = i + 1;
while (j < MaxSize) {
if (Digits [j] != 0) {
--Digits [j];
break;
}
else Digits [j] = 9;
++j;
}
}
}
};
/// If a swap has occured, we need to subtract L from *this
if (Swapped) Subtract(L);
/// Otherwise, we need to subtract R from *this
else Subtract(R);
size_t CountLeadingZeroes = 0;
for (int i = MaxSize - 1; i > 0; --i)
if (Digits [i] == 0) ++CountLeadingZeroes;
else break;
Digits.resize(MaxSize - CountLeadingZeroes);
}
/// Same signs
else {
size_t CarryOver = 0, i = 0;
for (; i < MinSize; ++i) {
Digits [i] += R.Digits [i] + CarryOver;
CarryOver = Digits [i] / 10;
Digits [i] %= 10;
}
if (isLesser)
for (; i < MaxSize; ++i) {
Digits.emplace_back(R.Digits [i] + CarryOver);
CarryOver = Digits [i] / 10;
Digits [i] %= 10;
}
else
for (; i < MaxSize; ++i) {
Digits [i] += CarryOver;
CarryOver = Digits [i] / 10;
Digits [i] %= 10;
}
while (CarryOver != 0) {
Digits.emplace_back(CarryOver % 10);
CarryOver /= 10;
}
}
return *this;
}
BigInt& BigInt::operator -= (const BigInt& R) {
return *this += -R;
}
BigInt& BigInt::operator ++ () {
return *this += 1;
}
BigInt& BigInt::operator -- () {
return *this -= 1;
}
BigInt BigInt::operator ++ (int) {
BigInt Copy = *this;
++*this;
return Copy;
}
BigInt BigInt::operator -- (int) {
BigInt Copy = *this;
--*this;
return Copy;
}
BigInt BigInt::operator + () const {
return *this;
}
BigInt BigInt::operator - () const {
BigInt B = *this;
if (B.Sign && B != 0) B.Sign = false;
else B.Sign = true;
return B;
}
std::string BigInt::to_string (bool Original = true) const {
size_t N = Digits.size();
std::string S (N, '0');
for (size_t i = 0; i < N; ++i)
S [i] = (Original ? Digits [N - i - 1] : Digits [i]) + '0';
return S;
}
std::vector <int> BigInt::to_vector (bool Original = true) const {
size_t N = Digits.size();
std::vector <int> V (N);
for (size_t i = 0; i < N; ++i)
V [i] = (Original ? Digits [N - i - 1] : Digits [i]);
return V;
}
inline size_t BigInt::size () const {
return Digits.size();
}
inline BigInt BigInt::abs () const {
if (Sign)
return *this;
else
return -*this;
}
BigInt operator + (const BigInt& L, const BigInt& R) {
return BigInt(L) += R;
}
BigInt operator - (const BigInt& L, const BigInt& R) {
return BigInt(L) -= R;
}
#endif /* BIG_INTEGER_H */
Benchmark 2: This computes (2^1e5)*A. A is a 100-digit number with all digits 9. This code takes about 15.4884130000 seconds (which is pretty bad, I think) compared to using Python to do the same in under 5 seconds. So, there's definitely something better about the Python Big Integer implementation, which I'd like to be as fast as. Please share your opinions on how I should be implementing to optimise for space and time. I know if I use bitsets to implement BigInt, it'd become really simple for me code and implement everything, which would also be really fast and space optimised. The only problem I'm facing is how would I calculate the actual number for presenting output. I have some ideas that I'll try but any input from others will be very valuable.
Code:
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cout.precision(10);
cout << fixed;// << boolalpha;
BigInt A = "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999";
for (int i = 0; i < 1e5; ++i)
A += A;
cout << A << endl;
return 0;
}