BigInt Library

Page
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.

Download the source

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

[top]

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;
}

[top]