This library contains a single class, BigInt, which works like an int of arbitrary size. At the moment, most of the basic functionality is in. There are still some operators that have not been implemented, but it’s in the works. In the next few months, I will be updating this library, re-writing it from scratch and uploading it to a repository so that everyone can see the progress. In addition, I will be making a tutorial on how this class was designed and the reasoning behind some of the decisions made.
Interface
/******************************************************************************/
/*
Author: Alejandro Hitti
Brief: Interface for the BigInt type. This object allows you to perform
unbounded integer operations. Useful when making operations that
would normally overflow a 32-bit or 64-bit integer.
All content (C) 2013-2014 Alejandro Hitti http://alejandrohitti.com.
All rights reserved.
*/
/******************************************************************************/
////////////////////////////////////////////////////////////////////////////////
#ifndef BIG_INT_H
#define BIG_INT_H
////////////////////////////////////////////////////////////////////////////////
#include <iostream> //istream, ostream
#include <string>
#include <vector>
class BigInt
{
public:
/*----------------------------------------
Constructors
----------------------------------------*/
BigInt(); // Default
BigInt(int num); // Non-default (integer)
BigInt(const std::string &str); // Non-default (string)
/*----------------------------------------
Arithmetic
----------------------------------------*/
const BigInt& operator += (const BigInt& rhs);
const BigInt& operator -= (const BigInt& rhs);
const BigInt& operator *= (const BigInt& rhs);
const BigInt& operator *= (int num);
// TODO(AleHitti): Implement these!
// BigInt& operator /= (const BigInt& rhs);
// Pow function
/*----------------------------------------
Assignment and Conversion
----------------------------------------*/
std::string ToString() const;
int ToInt() const;
double ToDouble() const;
/*----------------------------------------
Public Helper Functions
----------------------------------------*/
void Print(std::ostream& os) const; // Make a print with scanf? Test it
bool Equal(const BigInt& rhs) const; // Used for operators == and !=
bool LessThan(const BigInt& rhs) const; // Used for operators <, >, <=, >=
int Compare(const BigInt& rhs) const; // Returns 0 if equal than rhs.
// 1 if greater than rhs.
// -1 if less than rhs.
private:
/*----------------------------------------
Private Helper Functions
----------------------------------------*/
int GetDigit(int index) const;
void ChangeDigit(int index, int value);
void AddSignificantDigit(int value);
bool IsPositive() const; // Returns true if number is positive
bool IsNegative() const; // Returns false if number is negative
int NumDigits() const; // Returns number of digits in number
void Normalize(); // Converts number into it's standard form
/*----------------------------------------
Member Variables
----------------------------------------*/
enum Sign {positive, negative}; // Possible sign values
Sign sign_; // Is number positive or negative
std::vector<char> digits_; // Stores all digits in number
int numDigits_; // Stores number of digits in number
};
//////////////////////////////////////////
// Free Global Functions
//////////////////////////////////////////
/*----------------------------------------
Arithmetic
----------------------------------------*/
BigInt operator + (const BigInt& lhs, const BigInt& rhs);
BigInt operator - (const BigInt& lhs, const BigInt& rhs);
BigInt operator * (const BigInt& lhs, const BigInt& rhs);
BigInt operator * (const BigInt& lhs, int num);
BigInt operator * (int num, const BigInt& rhs);
//BigInt operator / (const BigInt& lhs, const BigInt& rhs);
/*----------------------------------------
Comparison
----------------------------------------*/
bool operator == (const BigInt& lhs, const BigInt& rhs);
bool operator != (const BigInt& lhs, const BigInt& rhs);
bool operator < (const BigInt& lhs, const BigInt& rhs);
bool operator > (const BigInt& lhs, const BigInt& rhs);
bool operator <= (const BigInt& lhs, const BigInt& rhs);
bool operator >= (const BigInt& lhs, const BigInt& rhs);
/*----------------------------------------
I/O
----------------------------------------*/
std::ostream& operator << (std::ostream& out, const BigInt& big);
std::istream& operator >> (std::istream& in, BigInt& big);
#endif // BIG_INT_H
Implementation
/******************************************************************************/
/*
Author: Alejandro Hitti
Brief: Implementation for the BigInt type. This object allows you to perform
unbounded integer operations. Useful when making operations that
would normally overflow a 32-bit or 64-bit integer.
All content (C) 2013-2014 Alejandro Hitti http://alejandrohitti.com.
All rights reserved.
*/
/******************************************************************************/
#include "BigInt.h"
#include <cctype> // isdigit
#include <limits.h> // INT_MIN
#include <stdlib.h>
// Allows different bases
#define BASE 10
/*----------------------------------------
Constructors
----------------------------------------*/
BigInt::BigInt()
: sign_(positive),
digits_(1, '0'),
numDigits_(1)
{
// All fields initialized in initializer list
}
BigInt::BigInt(int num)
: sign_(positive),
digits_(1, '0'),
numDigits_(0)
{
// Special case for Min Int
if (INT_MIN == num)
{
*this = INT_MIN + 1;
//*this -= 1;
return;
}
// Check for negative number and change state
if (num < 0)
{
sign_ = negative;
num *= -1;
}
// Handle least-significant digit of num (handles num == 0)
AddSignificantDigit(num % BASE);
num /= BASE;
// Handle the remaining digits of num
while (num != 0)
{
AddSignificantDigit(num % BASE);
num /= BASE;
}
}
BigInt::BigInt(const std::string &str)
: sign_(positive),
digits_(str.length(), '0'),
numDigits_(0)
{
// Boundary case
if (str.length() == 0)
{
digits_.resize(1);
AddSignificantDigit(0);
return;
}
int limit = 0; // Handles the cases with leading signs ('-' or '+')
// Set negative sign if first character is '-'
if (str[0] == '-')
{
sign_ = negative;
limit = 1;
}
// Sets the limit if it has a leading plus sign
if (str[0] == '+')
limit = 1;
for (int i = str.length() - 1; i >= limit; --i)
{
// Check validity of given integer
if ( !isdigit(str[i]) )
{
std::cout << str << " Is not a valid number." << std::endl;
//abort();
}
// Add digit to the container
AddSignificantDigit(str[i] - '0');
}
// Transform number into its standard format
Normalize();
}
/*----------------------------------------
Arithmetic
----------------------------------------*/
const BigInt& BigInt::operator += (const BigInt& rhs)
{
// If adding itself, multiply by 2
if (*this == rhs)
return *this *= 2;
// Adding zero is a special case
if (rhs == 0)
return *this;
// If the signs are different, substract instead
if (IsPositive() != rhs.IsPositive())
{
*this -= (-1 * rhs);
return *this;
}
// OPTIMIZE???
// Length will be the longest # of digits
int length = (NumDigits() < rhs.NumDigits()) ? rhs.NumDigits() : NumDigits();
int carry = 0; // Carry digit
int sum; // Partial sum
// Go through all the values in both numbers
for (int i = 0; i < length; ++i)
{
sum = GetDigit(i) + rhs.GetDigit(i) + carry;
carry = sum / BASE;
sum = sum % BASE;
if (i < NumDigits())
ChangeDigit(i, sum);
else
AddSignificantDigit(sum);
}
// If there is still a carry value
if (carry != 0)
AddSignificantDigit(carry);
return *this;
}
const BigInt& BigInt::operator -= (const BigInt& rhs)
{
// Substracting self
if (*this == rhs)
return *this = 0;
// If signs are different, add instead
if (IsNegative() != rhs.IsNegative())
{
*this += (-1 * rhs);
return *this;
}
/*
* Signs are the same. Check which number is larger
* and switch to get the larger number "on top" if
* necessary since the sign can change when substracting.
*/
if (IsPositive() && (*this) < rhs ||
IsNegative() && (*this) > rhs)
{
*this = rhs - *this;
// Toggle sign
sign_ = IsPositive() ? negative : positive;
return *this;
}
int diff;
int borrow = 0;
int length = NumDigits();
// Same sign and larger number on top
for (int i = 0; i < length; ++i)
{
diff = GetDigit(i) - rhs.GetDigit(i) - borrow;
borrow = 0;
if (diff < 0)
{
diff += 10;
borrow = 1;
}
ChangeDigit(i, diff);
}
// Prevents getting trailing zeroes on the left
Normalize();
return *this;
}
const BigInt& BigInt::operator *= (const BigInt& rhs)
{
if (IsNegative() != rhs.IsNegative())
sign_ = negative;
else
sign_ = positive;
BigInt self(*this);
BigInt sum(0);
int length = rhs.NumDigits();
for (int i = 0; i < length; ++i)
{
sum += self * rhs.GetDigit(i);
self *= 10;
}
*this = sum;
return *this;
}
const BigInt& BigInt::operator *= (int num)
{
// Special Cases (change order later? handle -1?)
// Zero is a special case
if (num == 0)
return *this = 0;
if (BASE < num || num < 0)
{
*this *= BigInt(num);
return *this;
}
// One is a special case. Do nothing.
if (num == 1)
return *this;
// -1 case?
int length = NumDigits();
int product;
int carry = 0;
// Multiplication happens here
for (int i = 0; i < length; ++i)
{
product = num * GetDigit(i) + carry;
carry = product / BASE;
ChangeDigit(i, product % BASE);
}
// Takes care of extra carry past the end of the numbers
while (carry != 0)
{
AddSignificantDigit(carry % BASE);
carry /= BASE;
}
return *this;
}
/*----------------------------------------
Assignment and Conversion
----------------------------------------*/
std::string BigInt::ToString() const
{
unsigned length = NumDigits();
std::string str = "";
if (IsNegative())
str = '-';
for (int i = length - 1; i >= 0; --i)
str += static_cast<char>('0' + GetDigit(i));
return str;
}
int BigInt::ToInt() const
{
// Handles int overflow
if (INT_MAX < *this)
return INT_MAX;
// Handles int underflow
if (*this < INT_MIN)
return INT_MIN;
int result = 0;
int length = NumDigits();
// Variation of Horner's rule
for (int i = length; i >= 0; --i)
result = result * 1- + GetDigit(i);
if (IsNegative())
result *= -1;
return result;
}
double BigInt::ToDouble() const
{
// Handles int overflow
if (DBL_MAX < *this)
return DBL_MAX;
// Handles int underflow
if (*this < DBL_MIN)
return DBL_MIN;
double result = 0.0;
int length = NumDigits();
// Variation of Horner's rule
for (int i = length; i >= 0; --i)
result = result * 1- + GetDigit(i);
if (IsNegative())
result *= -1;
return result;
}
/*----------------------------------------
Public Helper Functions
----------------------------------------*/
void BigInt::Print(std::ostream& out) const
{
out << ToString();
}
bool BigInt::Equal(const BigInt& rhs) const
{
// First check for optimization
if (NumDigits() != rhs.NumDigits() ||
IsNegative() != rhs.IsNegative() )
return false;
int length = NumDigits();
// If one digit is not equal, returns false
for (int i = 0; i < length; ++i)
if (GetDigit(i) != rhs.GetDigit(i))
return false;
// All elements are equal
return true;
}
bool BigInt::LessThan(const BigInt& rhs) const
{
// If signs aren't equal, this < rhs only if this is negative
if (IsNegative() != rhs.IsNegative())
return IsNegative();
// If # of digits aren't the same, we check # of digits and sign
if (NumDigits() != rhs.NumDigits())
return (NumDigits() < rhs.NumDigits() && IsPositive()) ||
(NumDigits() > rhs.NumDigits() && IsNegative());
int length = NumDigits();
// Check all digits and compare them
for (int i = length - 1; i >= 0; --i)
{
if (GetDigit(i) < rhs.GetDigit(i))
return IsPositive();
if (GetDigit(i) > rhs.GetDigit(i))
return IsNegative();
}
// this == rhs
return false;
}
int BigInt::Compare(const BigInt& rhs) const
{
// Equal
if (*this == rhs)
return 0;
// -1 if less than rhs, 1 if greater than rhs
return (*this < rhs) ? -1 : 1;
}
/*----------------------------------------
Private Helper Functions
----------------------------------------*/
int BigInt::GetDigit(int index) const
{
if (0 <= index && index < NumDigits())
return digits_[index] - '0';
return 0;
}
void BigInt::ChangeDigit(int index, int value)
{
if (0 <= index && index < NumDigits())
digits_[index] = static_cast<char>('0' + value);
}
void BigInt::AddSignificantDigit(int value)
{
// Resize container
if (static_cast<unsigned>(numDigits_) >= digits_.size())
digits_.resize(digits_.size() * 2);
digits_[numDigits_] = static_cast<char>('0' + value);
++numDigits_;
}
bool BigInt::IsPositive() const
{
return sign_ == positive;
}
bool BigInt::IsNegative() const
{
return sign_ == negative;
}
int BigInt::NumDigits() const
{
return numDigits_;
}
void BigInt::Normalize()
{
int length = NumDigits();
int i; // Declared outside because it will be used after the loop
for (i = length - 1; i >= 0; --i)
{
// Deletes leading zeroes
if (GetDigit(i) != 0)
break;
--numDigits_;
}
// This means it was all zeroes, leave the last one
if (i < 0)
{
numDigits_ = 1;
sign_ = positive;
}
// Makes the container not be unnecessarily big if a lot of leading zeroes
// Where introduced. Will have to test for efficiency.
digits_.shrink_to_fit();
}
//////////////////////////////////////////
// Free Global Functions
//////////////////////////////////////////
/*----------------------------------------
Arithmetic
----------------------------------------*/
BigInt operator + (const BigInt& lhs, const BigInt& rhs)
{
BigInt result(lhs);
result += rhs;
return result;
}
BigInt operator - (const BigInt& lhs, const BigInt& rhs)
{
BigInt result(lhs);
result -= rhs;
return result;
}
BigInt operator * (const BigInt& lhs, const BigInt& rhs)
{
BigInt result(lhs);
result *= rhs;
return result;
}
BigInt operator * (const BigInt& lhs, int num)
{
BigInt result(lhs);
result *= num;
return result;
}
BigInt operator * (int num, const BigInt& rhs)
{
BigInt result(rhs);
result *= num;
return result;
}
/*----------------------------------------
Comparison
----------------------------------------*/
bool operator == (const BigInt& lhs, const BigInt& rhs)
{
return lhs.Equal(rhs);
}
bool operator != (const BigInt& lhs, const BigInt& rhs)
{
return !(lhs == rhs);
}
bool operator < (const BigInt& lhs, const BigInt& rhs)
{
return lhs.LessThan(rhs);
}
bool operator > (const BigInt& lhs, const BigInt& rhs)
{
return rhs < lhs;
}
bool operator <= (const BigInt& lhs, const BigInt& rhs)
{
return lhs == rhs || lhs < rhs;
}
bool operator >= (const BigInt& lhs, const BigInt& rhs)
{
return lhs == rhs || lhs > rhs;
}
/*----------------------------------------
I/O
----------------------------------------*/
std::ostream& operator << (std::ostream& out, const BigInt& big)
{
big.Print(out);
return out;
}
std::istream& operator >> (std::istream& in, BigInt& big)
{
std::string str;
in >> str;
big = BigInt(str);
return in;
}
Alejandro Hitti 