bigint.cpp

大数运算的库

// ==============================================================
//
//  Copyright (C) 1995  William A. Rossi
//                      Class RossiBigInt
// 
//  Copyright (C) 1999-2004  Alex Vinokur
//                           Class VinBigInt
//                           Upgrading class RossiBigInt
//
//  ------------------------------------------------------------
// 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 2
// 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, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//  ------------------------------------------------------------
// 
//  mailto:alex DOT vinokur AT gmail DOT com
//  http://up.to/alexv
//
// ==============================================================


// ##############################################################
//
//  SOFTWARE : Class BigInt
//  FILE     : bigint.cpp
//
//  DESCRIPTION :
//          Classes VinBigInt & RossiBigInt (Definitions)
//
// ##############################################################


// ================
#include "bigint.h"
// ================


//////////
// DEFINES
//////////

// ==================

#define MAX_UNIT_VALUE  (ULONG_MAX >> 2)
#define BASE1  10
#define BASE2  1000000000   // BASE1 ** (BASE1 - 1)

#if (BASE2 >= MAX_UNIT_VALUE)
#error Compilation Error-1 : (BASE2 >= MAX_UNIT_VALUE)
#endif

#if (!(BASE1 * (BASE2/BASE1 + 1) < MAX_UNIT_VALUE))
#error Compilation Error-2 : (!(BASE1 * (BASE2/BASE1 + 1) < MAX_UNIT_VALUE))
#endif

#define ULONG_MSB 0x80000000   // ULONG_MAX ^ (ULONG_MAX >> 1);


#define ROSSI_TEST_BINARY_OP(testcase_id, op) \
	{ \
	  RossiBigInt z(0); \
	  z = vtest[testcase_id].first op vtest[testcase_id].second; \
	  cout << vtest[testcase_id].first.getstr_hex_value() \
	       << " " \
	       << #op \
	       << " " \
               << vtest[testcase_id].second.getstr_hex_value() \
	       << " = " \
	       << z.getstr_hex_value() \
	       << endl; \
	}


#define VIN_TEST_BINARY_OP_BIG(testcase_id, op) \
	{ \
	  VinBigInt z(0); \
	  z = vtest[testcase_id].first op vtest[testcase_id].second; \
	  cout << vtest[testcase_id].first \
	       << " " \
	       << #op \
	       << " " \
               << vtest[testcase_id].second \
	       << " = " \
	       << z \
	       << endl; \
	}


#define VIN_TEST_BINARY_OP_ULONG(testcase_id, op) \
	{ \
	  VinBigInt z(0); \
	  z = vtest[testcase_id].first op vtest[testcase_id].second; \
	  cout << vtest[testcase_id].first \
	       << " " \
	       << #op \
	       << " " \
               << vtest[testcase_id].second \
	       << " = " \
	       << z \
	       << endl; \
	}


#define ROSSI_TEST_BINARY_WITH_LESS_OP(testcase_id, op) \
	{ \
	  RossiBigInt z(0); \
	  if (!(vtest[testcase_id].first < vtest[testcase_id].second)) \
	  { \
	  z = vtest[testcase_id].first op vtest[testcase_id].second; \
	  cout << vtest[testcase_id].first.getstr_hex_value() \
	       << " " \
	       << #op \
	       << " " \
               << vtest[testcase_id].second.getstr_hex_value() \
	       << " = " \
	       << z.getstr_hex_value() \
	       << endl; \
	  } \
	}



#define ROSSI_TEST_BOOLEAN_OP(testcase_id, op) \
	{ \
	  bool z; \
	  z = vtest[testcase_id].first op vtest[testcase_id].second; \
	  cout << vtest[testcase_id].first.getstr_hex_value() \
	       << " " \
	       << #op \
	       << " " \
               << vtest[testcase_id].second.getstr_hex_value() \
	       << " : " \
	       << (z ? "TRUE" : "FALSE") \
	       << endl; \
	}


#define ROSSI_CREATE_EMPTY_VTEST vector<pair<RossiBigInt, RossiBigInt> > vtest
#define VIN_CREATE_EMPTY_VTEST_BIG_BIG vector<pair<VinBigInt, VinBigInt> > vtest
#define VIN_CREATE_EMPTY_VTEST_BIG_ULONG vector<pair<VinBigInt, ulong> > vtest

#define ROSSI_ADD_TEST_CASE_ULONG(a, b) \
	  vtest.push_back(pair<RossiBigInt, RossiBigInt> (RossiBigInt(a), RossiBigInt(b)))

#define ROSSI_ADD_TEST_CASE_STRING_DEC(a, b) \
	  vtest.push_back(pair<RossiBigInt, RossiBigInt> (RossiBigInt(a, DEC_DIGIT), RossiBigInt(b, DEC_DIGIT)))

#define ROSSI_ADD_TEST_CASE_STRING_HEX(a, b) \
	  vtest.push_back(pair<RossiBigInt, RossiBigInt> (RossiBigInt(a, HEX_DIGIT), RossiBigInt(b, HEX_DIGIT)))


#define VIN_ADD_TEST_CASE_ULONG_for_BIG_BIG(a, b) \
	  vtest.push_back(pair<VinBigInt, VinBigInt> (VinBigInt(a), VinBigInt(b)))

#define VIN_ADD_TEST_CASE_STRING_DEC_for_BIG_BIG(a, b) \
	  vtest.push_back(pair<VinBigInt, VinBigInt> (VinBigInt(a, DEC_DIGIT), VinBigInt(b, DEC_DIGIT)))

#define VIN_ADD_TEST_CASE_STRING_HEX_for_BIG_BIG(a, b) \
	  vtest.push_back(pair<VinBigInt, VinBigInt> (VinBigInt(a, HEX_DIGIT), VinBigInt(b, HEX_DIGIT)))


#define VIN_ADD_TEST_CASE_ULONG_for_BIG_ULONG(a, b) \
	  vtest.push_back(pair<VinBigInt, ulong> (VinBigInt(a), b))

#define VIN_ADD_TEST_CASE_STRING_DEC_for_BIG_ULONG(a, b) \
	  vtest.push_back(pair<VinBigInt, ulong> (VinBigInt(a, DEC_DIGIT), b)))

#define VIN_ADD_TEST_CASE_STRING_HEX_for_BIG_ULONG(a, b) \
	  vtest.push_back(pair<VinBigInt, ulong> (VinBigInt(a, HEX_DIGIT), b))



////////////
// FUNCTIONS
////////////
void ShowVersion()
{
  cerr << endl;
  cerr << "BigInt - C++ class for computation with arbitrary large integers" << endl;
  cerr << "Version " << BIG_INT_VERSION_No << endl;

  cerr << endl;
  cerr << "Copyright (C) 1995       William A. Rossi - Class RossiBigInt" << endl;
  cerr << "Copyright (C) 1999-2004  Alex Vinokur - Class VinBigInt, Upgrading class RossiBigInt" << endl;

  cerr << endl;
  cerr << "This is free software; see the source for copying conditions." << endl;
  cerr << "There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE." << endl;
  cerr << endl;
}


////////////
// CONSTANTS
////////////
static const RossiBigInt Zero (0);
static const RossiBigInt One  (1);
static const RossiBigInt Two  (2);

static const ulong hex_digit_size_cns (4);
static const ulong digits_in_ulong_s ((sizeof (ulong) * CHAR_BIT)/hex_digit_size_cns);

///////////////
// STATIC INIT
///////////////

class Aux1
{
  private:
    map<char, ulong> hex_to_dec_digits_convertor_;

  public:
    Aux1 ()
    {
      hex_to_dec_digits_convertor_ ['0'] = 0;
      hex_to_dec_digits_convertor_ ['1'] = 1;
      hex_to_dec_digits_convertor_ ['2'] = 2;
      hex_to_dec_digits_convertor_ ['3'] = 3;
      hex_to_dec_digits_convertor_ ['4'] = 4;
      hex_to_dec_digits_convertor_ ['5'] = 5;
      hex_to_dec_digits_convertor_ ['6'] = 6;
      hex_to_dec_digits_convertor_ ['7'] = 7;
      hex_to_dec_digits_convertor_ ['8'] = 8;
      hex_to_dec_digits_convertor_ ['9'] = 9;
      hex_to_dec_digits_convertor_ ['a'] = 10;
      hex_to_dec_digits_convertor_ ['A'] = 10;
      hex_to_dec_digits_convertor_ ['b'] = 11;
      hex_to_dec_digits_convertor_ ['B'] = 11;
      hex_to_dec_digits_convertor_ ['c'] = 12;
      hex_to_dec_digits_convertor_ ['C'] = 12;
      hex_to_dec_digits_convertor_ ['d'] = 13;
      hex_to_dec_digits_convertor_ ['D'] = 13;
      hex_to_dec_digits_convertor_ ['e'] = 14;
      hex_to_dec_digits_convertor_ ['E'] = 14;
      hex_to_dec_digits_convertor_ ['f'] = 15;
      hex_to_dec_digits_convertor_ ['F'] = 15;
  }

    map<char, ulong> get_hex_to_dec_digits_convertor ()
    {
      return hex_to_dec_digits_convertor_;
    }

};

Aux1 aux1_ins;

map<char, ulong> BaseBigInt::hex_to_dec_digits_convertor_s (aux1_ins.get_hex_to_dec_digits_convertor());





//////////////
// DEFINITIONS
//////////////


// ================
// class BaseBigInt
// ================

// ------------------
bool BaseBigInt::is_empty() const
{
  return units_.empty();
}


// ------------------
ulong BaseBigInt::get_units_size() const
{
  return units_.size();
}



// ------------------
BaseBigInt::~BaseBigInt()
{
}



// ===============
// class VinBigInt
// ===============

// ------------------
static ulong  head_s = 0;
ulong add_units(ulong n1, ulong n2)
{
  n1 += (n2 + head_s);
  head_s = n1/BASE2;
  return (n1%BASE2);
}



// ------------------
// Constructor-0
VinBigInt::VinBigInt () 
{
}


// ------------------
// Constructor-1
VinBigInt::VinBigInt (ulong unit_i) 
{
  if (!(unit_i < BASE2))
  {
    FATAL_ERROR ("ulong value too big");
    cerr << "unit_i         = " << dec << unit_i << ", Ox" << hex << unit_i << endl;
    cerr << "BASE2          = " << dec << BASE2 << ", Ox" << hex << BASE2 << endl;
    cerr << "MAX_UNIT_VALUE = " << dec << MAX_UNIT_VALUE << ", Ox" << hex << MAX_UNIT_VALUE << endl;
    cerr << endl;
  }
  ASSERTION (unit_i < BASE2);
  units_.reserve(units_.size() + 1);
  units_.push_back (unit_i);
}



// ------------------
// Constructor-2
VinBigInt::VinBigInt (const string& arg_i, ulong digit_base_i)
{
bool rc = init_via_string (arg_i, digit_base_i);
  ASSERTION (rc);
}

// ------------------
// Constructor-3
VinBigInt::VinBigInt (const RossiBigInt& arg_i)
{
const string str (arg_i.getstr_pure_hex_value ());
bool rc = init_via_string (str, HEX_DIGIT);
  ASSERTION (rc);
}



// ------------------
ulong VinBigInt::get_pure_ulong () const
{
  ASSERTION (!units_.empty());
  if (units_.size() > 1)
  {
    FATAL_ERROR ("ulong can't be obtained: units_.size() too big");
    cerr << "units_.size() = " << units_.size() << endl;
    cerr << "units_.size() must be = 1" << endl;
    ASSERTION (units_.size() == 1);
  }
  ASSERTION (units_.size() == 1);
  return units_.front();
}


// ------------------
bool VinBigInt::init_via_string (const string& arg_i, ulong digit_base_i)
{
  ASSERTION (units_.empty());
  ASSERTION ((digit_base_i ==  16) || (digit_base_i ==  10));

  units_.push_back(0);

  for (ulong i = 0; i < arg_i.size(); i++)
  {
    switch (digit_base_i)
    {
      case DEC_DIGIT:
        if (!isdigit (arg_i[i])) 
        {
          FATAL_ERROR ("string contains non-decimal digit");
          cerr << "string = " << arg_i << endl;
          cerr << i << "-th char = " << arg_i[i] << endl;
          ASSERTION (0);
          return false; // unused
        }
        break;

      case HEX_DIGIT:
        if (!isxdigit (arg_i[i])) 
        {
          FATAL_ERROR ("string contains non-hexadecimal digit");
          cerr << "string = " << arg_i << endl;
          cerr << i << "-th char = " << arg_i[i] << endl;
          ASSERTION (0);
          return false; // unused
        }
        break;

      default:
        ASSERTION (0);
        return false;
        break; // unused

    }
  }

  for (ulong i = 0; i < arg_i.size(); i++)
  {
    *this = (*this) * digit_base_i
          + VinBigInt (hex_to_dec_digits_convertor_s[arg_i[i]]);
  }
  return true;
}

// ------------------
VinBigInt VinBigInt::operator+ (const VinBigInt& arg_i) const
{
VinBigInt ret;
const ulong max_size (MAX_VAL (units_.size (), arg_i.units_.size ()));

vector<ulong> u1 (units_);
vector<ulong> u2 (arg_i.units_);

  u1.reserve(max_size);
  u2.reserve(max_size);
  ret.units_.reserve(max_size + 1);

  u1.resize(max_size);
  u2.resize(max_size);
  ret.units_.resize(max_size);

  head_s = 0;
  transform (&u1[0], &u1[0] + max_size, &u2[0], &ret.units_[0], add_units);

  if (head_s) ret.units_.push_back (head_s);

  return ret;

}


// ------------------
VinBigInt VinBigInt::operator* (ulong arg_i) const
{
VinBigInt ret (0);
  for (ulong i = 0; i < arg_i; i++) ret = ret + (*this);
  return ret;
}


// ------------------
bool VinBigInt::operator< (const VinBigInt& arg_i) const
{
  if (units_.size() < arg_i.units_.size()) return true;
  if (arg_i.units_.size() < units_.size()) return false;

  ASSERTION (units_.size() == arg_i.units_.size());
  for (ulong i = (units_.size() - 1); i > 0; i--)
  {
    if (units_[i] < arg_i.units_[i]) return true;
    if (arg_i.units_[i] < units_[i]) return false;
  }
  return (units_[0] < arg_i.units_[0]);
}


// ------------------
bool VinBigInt::operator<= (const VinBigInt& arg_i) const
{
  if (*this < arg_i) return true;
  if (*this == arg_i) return true;
  return false;
}



// ------------------
bool VinBigInt::operator> (const VinBigInt& arg_i) const
{
  return (!(*this <= arg_i));
}


// ------------------
bool VinBigInt::operator>= (const VinBigInt& arg_i) const
{
  return (!(*this < arg_i));
}

// ------------------
bool VinBigInt::operator== (const VinBigInt& arg_i) const
{
  if (*this < arg_i) return false;
  if (arg_i < *this) return false;
  return true;
}

// ------------------
bool VinBigInt::operator!= (const VinBigInt& arg_i) const
{
  return (!(*this == arg_i));
}


// ------------------
ostream& operator<< (ostream& os, const VinBigInt& ins_i)
{
  // ASSERTION (!ins_i.units_.empty ());
  if (ins_i.is_empty ()) return os << "is_empty";

  for (ulong i = (ins_i.units_.size () - 1); i; --i) 
  {
    os << ins_i.units_ [i] << setw (BASE1 - 1) << setfill ('0');
  }
  return os << ins_i.units_ [0];
}




// ------------------
void VinBigInt::All_Tests()
{
  Test100_Operator_Add_Bigint();
  Test300_Operator_Multiplication_Ulong ();
}