bigint.cpp

大数运算的库

// ------------------
void VinBigInt::Test100_Operator_Add_Bigint()
{
ostringstream oss;
  oss << "VinBigInt::Test100_Operator_Add_Bigint" << endl;

  cout << endl;
  cout << endl;
  cout << endl;
  cout << string (oss.str().size(), '-') << endl;
  cout << oss.str() << endl;
  cout << string (oss.str().size(), '-') << endl;
  cout << endl;


  VIN_CREATE_EMPTY_VTEST_BIG_BIG;

vector<ulong>  ulong_nums;
vector<string> hexstr_nums;

  // --- ulong_nums ---
  ulong_nums.push_back (0);
  ulong_nums.push_back (1);
  ulong_nums.push_back (2);
  ulong_nums.push_back (3);
  ulong_nums.push_back (9);
  ulong_nums.push_back (10);
  ulong_nums.push_back (11);
  ulong_nums.push_back (15);
  ulong_nums.push_back (16);
  ulong_nums.push_back (17);
  ulong_nums.push_back (999999998);
  ulong_nums.push_back (999999999);

  for (ulong i = 0; i < ulong_nums.size(); i++)
  {
    for (ulong k = 0; k < ulong_nums.size(); k++)
    {
      VIN_ADD_TEST_CASE_ULONG_for_BIG_BIG (ulong_nums[i], ulong_nums[k]);
    }
  }


  // --- hexstr_nums ---
  hexstr_nums.push_back ("0");
  hexstr_nums.push_back ("1");
  hexstr_nums.push_back ("2");
  hexstr_nums.push_back ("3");
  hexstr_nums.push_back ("100");
  hexstr_nums.push_back ("ABC");
  hexstr_nums.push_back ("F000000000000000");
  hexstr_nums.push_back ("FEDCBA9876543210");
  hexstr_nums.push_back ("123456789ABCDEF");
  hexstr_nums.push_back ("FFFFFFFFFFFFFFFFFFFFFFFF");
  hexstr_nums.push_back ("123456789ABCDEF123456789FFFFFFFFFFF");
  hexstr_nums.push_back ("111222333444555666777888999AAABBBCC");


  for (ulong i = 0; i < hexstr_nums.size(); i++)
  {
    for (ulong k = 0; k < hexstr_nums.size(); k++)
    {
      VIN_ADD_TEST_CASE_STRING_HEX_for_BIG_BIG (hexstr_nums[i], hexstr_nums[k]);
    }
  }


  for (ulong i = 0; i < vtest.size(); i++)
  {
    VIN_TEST_BINARY_OP_BIG(i, +);
  }

}



// ------------------
void VinBigInt::Test300_Operator_Multiplication_Ulong()
{
ostringstream oss;
  oss << "VinBigInt::Test300_Operator_Multiplication_Ulong";

  cout << endl;
  cout << endl;
  cout << endl;
  cout << string (oss.str().size(), '-') << endl;
  cout << oss.str() << endl;
  cout << string (oss.str().size(), '-') << endl;
  cout << endl;


  VIN_CREATE_EMPTY_VTEST_BIG_ULONG;

vector<ulong>  ulong_nums;
vector<string> hexstr_nums;

  // --- ulong_nums ---
  ulong_nums.push_back (0);
  ulong_nums.push_back (1);
  ulong_nums.push_back (2);
  ulong_nums.push_back (3);
  ulong_nums.push_back (9);
  ulong_nums.push_back (10);
  ulong_nums.push_back (11);
  ulong_nums.push_back (15);
  ulong_nums.push_back (16);
  ulong_nums.push_back (17);
  ulong_nums.push_back (0x10);
  ulong_nums.push_back (0x100);

  for (ulong i = 0; i < ulong_nums.size(); i++)
  {
    for (ulong k = 0; k < ulong_nums.size(); k++)
    {
      VIN_ADD_TEST_CASE_ULONG_for_BIG_ULONG (ulong_nums[i], ulong_nums[k]);
    }
  }


  // --- hexstr_nums ---
  hexstr_nums.push_back ("0");
  hexstr_nums.push_back ("1");
  hexstr_nums.push_back ("2");
  hexstr_nums.push_back ("3");
  hexstr_nums.push_back ("100");
  hexstr_nums.push_back ("ABC");
  hexstr_nums.push_back ("F000000000000000");
  hexstr_nums.push_back ("FEDCBA9876543210");
  hexstr_nums.push_back ("123456789ABCDEF");
  hexstr_nums.push_back ("FFFFFFFFFFFFFFFFFFFFFFFF");
  hexstr_nums.push_back ("123456789ABCDEF123456789FFFFFFFFFFF");
  hexstr_nums.push_back ("111222333444555666777888999AAABBBCC");


  for (ulong i = 0; i < hexstr_nums.size(); i++)
  {
    for (ulong k = 0; k < ulong_nums.size(); k++)
    {
      VIN_ADD_TEST_CASE_STRING_HEX_for_BIG_ULONG (hexstr_nums[i], ulong_nums[k]);
    }
  }


  for (ulong i = 0; i < vtest.size(); i++)
  {
    VIN_TEST_BINARY_OP_ULONG(i, *);
  }

}


// =================
// class RossiBigInt
// =================


// ------------------
// Constructor-0
RossiBigInt::RossiBigInt () 
{
  ASSERTION(is_empty());
}


// ------------------
// Constructor-1
RossiBigInt::RossiBigInt (ulong unit_i) 
{
  ASSERTION (units_.empty());
  units_.push_back (unit_i);
}


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



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


// ------------------
ulong RossiBigInt::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 RossiBigInt::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
          + RossiBigInt (hex_to_dec_digits_convertor_s[arg_i[i]]);
  }
  return true;
}


// ------------------
void RossiBigInt::resize_units(ulong size_i)
{
  units_.resize(size_i);
}

// ------------------
void RossiBigInt::truncate_units()
{
  while ((units_.size() > 1) && (units_.back() == 0))
  {
    units_.pop_back();
  }
  ASSERTION(!is_empty());

}

// ------------------
bool RossiBigInt::units_not_front_back_is_null () const
{
  ASSERTION (!units_.empty());
  if (units_.size() == 1) return false;
  return (units_.back() == 0);
}


// ------------------
RossiBigInt RossiBigInt::operator+ (const RossiBigInt& arg_i)
{
// static RossiBigInt ret;
RossiBigInt ret (0);
RossiBigInt arg (arg_i);
ulong carry = 0;

const ulong max_size (MAX_VAL (get_units_size(), arg.get_units_size()));

  resize_units (max_size + 1);
  arg.resize_units (max_size + 1);
  ret.resize_units (max_size + 1);

  for (ulong i = 0; i < units_.size(); i++)
  {
    ret.units_[i] = units_[i] + arg.units_[i] + carry;
    if (carry == 0)
    {
      carry = ((ret.units_[i] < units_[i] || ret.units_[i] < arg.units_[i]) ? 1 : 0);
    }
    else
    {
      carry = ((ret.units_[i] <= units_[i] || ret.units_[i] <= arg.units_[i]) ? 1 : 0);
    }
  }

  if (units_not_front_back_is_null ()) truncate_units ();
  if (ret.units_not_front_back_is_null ()) ret.truncate_units ();

  return ret;

}


// ------------------
RossiBigInt RossiBigInt::operator+ (ulong arg_i)
{
  return (*this + RossiBigInt (arg_i));
}


// ------------------
bool RossiBigInt::operator< (const RossiBigInt& 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 RossiBigInt::operator<= (const RossiBigInt& arg_i) const
{
  if (*this < arg_i) return true;
  if (*this == arg_i) return true;
  return false;
}



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


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

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

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



// ------------------
RossiBigInt RossiBigInt::operator/ (const RossiBigInt& arg_i) const
{
  return Divide(*this, arg_i, NULL);
}


// ------------------
RossiBigInt RossiBigInt::operator% (const RossiBigInt& arg_i) const
{
RossiBigInt ret;
  Divide(*this, arg_i, &ret);
  return ret;
}



// ------------------
RossiBigInt RossiBigInt::operator>> (ulong shift_i)
{
static RossiBigInt tmp;
static RossiBigInt ret;

  tmp = *this;

  ret.resize_units (units_.size());

  ASSERTION (ret.get_units_size() == tmp.get_units_size());

  for (ulong i = 0; i < shift_i; i++)
  {
    ret.units_.back() = (tmp.units_.back() >> 1);

    for (long j = (tmp.units_.size() - 1); j >= 0; j--)   // j must be of signed type
    {
      ret.units_[j] = (tmp.units_[j] >> 1);

      if ((tmp.units_[j + 1] & 1) != 0)
      {
        ret.units_[j] |= ULONG_MSB;      // Set MSB bit
      }
    }
    tmp = ret;
  }

  if (ret.units_not_front_back_is_null ()) ret.truncate_units ();

  return ret;
}


// ------------------
RossiBigInt RossiBigInt::operator<< (ulong shift_i)
{
static RossiBigInt tmp;
static RossiBigInt ret;

  tmp = *this;

  ret.resize_units (units_.size() + 1);

  ASSERTION ((ret.get_units_size() + 1) == tmp.get_units_size());

  for (ulong i = 0; i < shift_i; i++)
  {
    ret.units_.front() = (tmp.units_.front() << 1);
    for (ulong j = 1; j < tmp.units_.size(); j++)
    {
      ret.units_[j] = (tmp.units_[j] << 1);
      if ((tmp.units_[j-1] & ULONG_MSB) != 0)
      {
        ret.units_[j] |= 1;     // Set MSB bit
      }
    }
    if ((tmp.units_.back() & ULONG_MSB) != 0)
    {
      ret.units_.back() |= 1;   // Set MSB bit
    }
    tmp = ret;
  }

  if (ret.units_not_front_back_is_null ()) ret.truncate_units ();

  return ret;
}



// ------------------
RossiBigInt& RossiBigInt::operator>>= (ulong shift_i)
{
ulong carry;
  units_.push_back(0);

  for (ulong i = 0; i < shift_i; i++)
  {
    carry = units_.back() & 1;
    units_.back() >>= 1;

    for (long j = (units_.size() - 1); j>=0; j--)   // j must be of signed type
    {
      if (carry)
      {
        carry = units_[j] & 1;
        units_[j] >>= 1;
        units_[j] |= ULONG_MSB;
      }
      else
      {
        carry = units_[j] & 1;
        units_[j] >>= 1;
      }
    }
  }

  if (units_not_front_back_is_null ()) truncate_units ();

  return *this;
}



// ------------------
RossiBigInt& RossiBigInt::operator<<= (ulong shift_i)
{
ulong carry;

const ulong push_back_size (shift_i/(sizeof (ulong) * CHAR_BIT) + 1);

  for (ulong i = 0; i < (push_back_size + 1); i++)
  {
    units_.push_back(0);
  }

  for (ulong i = 0; i < shift_i; i++)
  {

    carry = units_.front() & ULONG_MSB;
    units_.front() <<= 1;

    for (ulong j = 1; j < units_.size(); j++)
    {
      if (carry)
      {
        carry = units_[j] & ULONG_MSB;
        units_[j] <<= 1;