bigint.cpp

大数运算的库

        units_[j] |= 1;
      }
      else
      {
        carry = units_[j] & ULONG_MSB;
        units_[j] <<= 1;
      }
    }
  }

  if (units_not_front_back_is_null ()) truncate_units ();
  return *this;
}



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

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

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

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

  if (units_not_front_back_is_null ()) truncate_units ();

  return *this;
}


// ------------------
RossiBigInt& RossiBigInt::operator++()  // Pre Increment operator -- faster than add
{
  units_.push_back(0);

  units_.front()++;
  for (ulong i = 1; i < units_.size(); i++)
  {
    if (units_[i-1]) break;
    units_[i]++;
  }

  if (units_not_front_back_is_null ()) truncate_units ();

  return *this;
}


// ------------------
RossiBigInt& RossiBigInt::operator++ (int)  // Post Increment operator -- faster than add
{
  units_.push_back(0);

  units_.front()++;
  for (ulong i = 1; i < units_.size(); i++)
  {
    if (units_[i-1]) break;
    units_[i]++;
  }

  if (units_not_front_back_is_null ()) truncate_units ();

  return *this;
}




// ------------------
RossiBigInt RossiBigInt::operator- ()  // Negates a number
{
static RossiBigInt ret;
  ret.resize_units(units_.size() + 1);

  for (ulong i = 0; i < units_.size(); i++)
  {
    ret.units_[i] = ~units_[i];
  }

  ret = ret + One;

  if (units_not_front_back_is_null ()) truncate_units ();

  return ret;
}



// ------------------
RossiBigInt RossiBigInt::operator-(const RossiBigInt& arg_i)
{
RossiBigInt ret (Zero);
RossiBigInt arg (arg_i);
ulong borrow = 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);

  if (*this < arg)
  {
    FATAL_ERROR ("minuend < subtracter");
    cerr << "minuend    = " << this->getstr_hex_value() << endl;
    cerr << "subtracter = " << arg.getstr_hex_value() << endl;
    ASSERTION (0);
  }

  for (ulong i = 0; i < units_.size(); i++)
  {
    ret.units_[i] = units_[i] - arg.units_[i] - borrow;
    
    if (borrow == 0)
    {
      borrow = ((units_[i] < arg.units_[i]) ? 1 : 0);
    }
    else
    {
      borrow = ((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-= (const RossiBigInt& arg_i)
{
ulong borrow = 0;
ulong prevdigit;

  for (ulong i=0; i < units_.size(); i++)
  {
    prevdigit = units_[i];
    units_[i] = units_[i] - arg_i.units_[i] - borrow;

    if (borrow == 0)
    {
      borrow = ((prevdigit < arg_i.units_[i]) ? 1 : 0);
    }
    else
    {
      borrow = ((prevdigit <= arg_i.units_[i]) ? 1 : 0);
    }
  }

  if (units_not_front_back_is_null ()) truncate_units ();

  return *this;
}




// ------------------
RossiBigInt& RossiBigInt::operator--()  // Pre Decrement operator -- faster than add
{
  units_.front()--;
  for (ulong i = 1; i < units_.size(); i++)
  {
    if (units_[i-1] != ULONG_MAX) break;
    ASSERTION (units_[i-1] < ULONG_MAX);

    units_[i]--;
  }

  if (units_not_front_back_is_null ()) truncate_units ();

  return *this;
}


// ------------------
RossiBigInt& RossiBigInt::operator-- (int)  // Post Decrement operator -- faster than add
{
  units_.front()--;
  for (ulong i = 1; i < units_.size(); i++)
  {
    if (units_[i-1] != ULONG_MAX) break;
    ASSERTION (units_[i-1] < ULONG_MAX);

    units_[i]--;
  }

  if (units_not_front_back_is_null ()) truncate_units ();

  return *this;
}



// ------------------
RossiBigInt RossiBigInt::operator& (const RossiBigInt& arg_i)
{
const ulong max_size (MAX_VAL (get_units_size (), arg_i.get_units_size ()));

static RossiBigInt ret;
RossiBigInt arg (arg_i);

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

  for (long i = (units_.size() - 1); i>=0; i--)   // i must be of signed type
  {
    ret.units_[i] = units_[i] & arg.units_[i];
  }

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

  return ret;
}


// ------------------
RossiBigInt RossiBigInt::operator| (const RossiBigInt& arg_i)
{
const ulong max_size (MAX_VAL (get_units_size (), arg_i.get_units_size ()));

static RossiBigInt ret;
RossiBigInt arg (arg_i);

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

  for (long i = (units_.size() - 1); i>=0; i--)   // i must be of signed type
  {
    ret.units_[i] = units_[i] | arg.units_[i];
  }

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

  return ret;
}



// ------------------
RossiBigInt RossiBigInt::operator^ (const RossiBigInt& arg_i)
{
const ulong max_size (MAX_VAL (get_units_size (), arg_i.get_units_size ()));

static RossiBigInt ret;
RossiBigInt arg (arg_i);

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

  for (long i = (units_.size() - 1); i>=0; i--)   // i must be of signed type
  {
    ret.units_[i] = units_[i] ^ arg.units_[i];
  }

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

  return ret;

}


// ------------------
RossiBigInt RossiBigInt::operator~ ()
{
static RossiBigInt ret;

  ret.resize_units(get_units_size());

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

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

  return ret;

}



// ------------------
RossiBigInt& RossiBigInt::operator&= (const RossiBigInt& arg_i)
{
const ulong max_size (MAX_VAL (get_units_size (), arg_i.get_units_size ()));

RossiBigInt arg (arg_i);

  arg.resize_units(max_size);
  resize_units(max_size);

  for (long i = (units_.size() - 1); i>=0; i--)   // i must be of signed type
  {
    units_[i] = units_[i] & arg.units_[i];
  }

  if (units_not_front_back_is_null ()) truncate_units ();

  return *this;

}


// ------------------
RossiBigInt& RossiBigInt::operator|=(const RossiBigInt& arg_i)
{
const ulong max_size (MAX_VAL (get_units_size (), arg_i.get_units_size ()));

RossiBigInt arg (arg_i);

  arg.resize_units(max_size);
  resize_units(max_size);

  for (long i = (units_.size() - 1); i>=0; i--)   // i must be of signed type
  {
    units_[i] = units_[i] | arg.units_[i];
  }

  if (units_not_front_back_is_null ()) truncate_units ();

  return *this;

}


// ------------------
RossiBigInt& RossiBigInt::operator^=(const RossiBigInt& arg_i)
{
const ulong max_size (MAX_VAL (get_units_size (), arg_i.get_units_size ()));

RossiBigInt arg (arg_i);

  arg.resize_units(max_size);
  resize_units(max_size);

  for (long i = (units_.size() - 1); i>=0; i--)   // i must be of signed type
  {
    units_[i] = units_[i] ^ arg.units_[i];
  }

  if (units_not_front_back_is_null ()) truncate_units ();

  return *this;

}




// ------------------
RossiBigInt RossiBigInt::operator* (RossiBigInt arg_i) const
{
// static RossiBigInt tmp;
RossiBigInt tmp;
// static RossiBigInt ret;
RossiBigInt ret;

  tmp = *this;
  ret = Zero;
  // ret.resize_units (get_units_size () + arg_i.get_units_size ());

  do
  {
    if ((arg_i.units_.front() & 1) != 0) ret += tmp;
    arg_i >>= 1;
    tmp <<= 1;
  } while (arg_i != Zero);

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

  return ret;
}


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

				 

// ------------------
RossiBigInt RossiBigInt::Divide (
		const RossiBigInt& dividend_i, 
		const RossiBigInt& divisor_i, 
		RossiBigInt *remainder_o
		) const
{
RossiBigInt dividend (dividend_i); 
RossiBigInt divisor (divisor_i); 

long shiftcnt (0);

  // --- Check for attempt to divide by zero ---

  if (divisor == Zero)
  {
    FATAL_ERROR ("divisor == Zero");
    ASSERTION (0 && "divisor == Zero");

    shiftcnt = 1 / shiftcnt;  // Force a divide by zero exception. (shiftcnt=0)
  }

RossiBigInt quotient (Zero);

  quotient.resize_units (dividend.get_units_size ());

  if (remainder_o != NULL)
  {
    remainder_o->resize_units (dividend.get_units_size ());
  }


  // --- Left shift divisor until it is greater than or equal to dividend ---
  // while ( divisor < dividend && ((divisor.units_.back() & ULONG_MSB) == 0))
  while ( divisor < dividend)
  {
    divisor <<= 1;
    shiftcnt++;
  }

  if (divisor > dividend)      // If divisor is greater than dividend, right shift divisor
  {
    divisor >>= 1;
    shiftcnt--;
  }

  if (shiftcnt >= 0)
  {
    for(long i = 0; i <= shiftcnt; i++)
    {
      if ( divisor <= dividend)  // If divisor is greater than dividend, then the bit is a 1 
      {
        dividend -= divisor;     // Subtract divisor from dividend 
        divisor  >>= 1;          // Right shift divisor 
        quotient <<= 1;          // Left shift quotient
        quotient++;              // Increment quotient 
      }
      else
      {
        divisor >>= 1;             // Bit is 0, right shift divisor, left shift quotient
        quotient <<= 1;
      }
    }
  }

RossiBigInt remainder (dividend); 
  if (remainder.units_not_front_back_is_null ()) remainder.truncate_units ();
  if (remainder_o != NULL) 
  {
    *remainder_o = remainder;
    if (remainder_o->units_not_front_back_is_null ()) remainder_o->truncate_units ();
  }

  if (quotient.units_not_front_back_is_null ()) quotient.truncate_units ();

  ASSERTION ((quotient * divisor_i + remainder) == dividend_i);
  return quotient;
}



// ------------------
RossiBigInt RossiBigInt::sqrt()		// Returns the square root of this
{
static RossiBigInt ret;
static RossiBigInt tmp;
static RossiBigInt delta;

RossiBigInt mask (Two);

  tmp = *this;
  mask = -mask;

ulong i = 0;
  ret = tmp; 
  for (i = 0; ret != Zero; ret >>= 1, i++)
  {
    // Do nothing
  }

  ret = tmp; 
  for (ulong j = 0; j < ulong(i >> 1); ret >>= 1, j++)
  {
    // Do nothing
  }

  do
  {
    // -----------------------------------------------
    // We are really performing the fuction:
    //	 delta = (tmp/ret - ret) / 2;
    //   below, but since these are unsigned numbers,
    //   we MUST do the subtraction last in order for
    //   the ret = ret + delta;  equation to work properly.
    // -----------------------------------------------

    delta = ( tmp >>1 ) / ret - (ret >> 1);
    ret = ret + delta;
  } while ((delta &= mask) != Zero);

  return ret;
}