bignum.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 1,299 行 · 第 1/4 页

  this->state = b.state;                        // Copy b's state
}



// operator= -- overloaded CoolBignum assignment operator
// Inputs:  reference to CoolBignum to be assigned
// Outputs:  reference to modified CoolBignum

CoolBignum& CoolBignum::operator= (const CoolBignum& b) {
  if (this != &b) {                             // So long as b is not "this"
    delete [] this->data;                       // Delete existing data
    this->count = b.count;                      // Copy b's count
    this->data =                                // Allocate data if necessary
      (this->count > 0 ? new Data[this->count] : 0);
    for (Counter i = 0; i < this->count; i++)   // Copy b's data
      this->data[i] = b.data[i];
    this->sign = b.sign;                        // Copy b's sign
    this->state = b.state;                      // Copy b's state
  }
  return *this;                                 // Return reference 
}



// operator- -- overloaded unary minus operator
// Inputs:  none
// Outputs:  CoolBignum, negated

CoolBignumE CoolBignum::operator- () const {
  CoolBignum temp(*this);                       // Temp stores result
  if (temp.count)                               // So long as this is non-zero
    temp.sign *= -1;                            // Flip its sign
  CoolBignumE& result = *((CoolBignumE*) &temp);// same physical object
  return result;                                // shallow swap on return
}


// operator++ overloaded increment operator for CoolBignums
// Inputs:  none
// Outputs:  reference to this CoolBignum, incremented

CoolBignum& CoolBignum::operator++ () {
  static CoolBignum one_s = 1l;                 // static CoolBignum equal to 1
  *this = *this + one_s;;                       // add one to this CoolBignum
  return *this;                                 // return reference to this B.
}



// operator--  overloaded decrement operator for CoolBignums
// Inputs:  none
// Outputs:  this CoolBignum, decremented

CoolBignum& CoolBignum::operator-- () {
  static CoolBignum one_s = 1l;                 // static CoolBignum equal to 1
  *this = *this - one_s;                        // add one to this CoolBignum
  return *this;                                 // return reference to this B.
}



// resize -- change the data allotment for a CoolBignum
// Inputs:  new size of data allotment
// Outputs:  none

void CoolBignum::resize (Counter new_count) {
  if (new_count != this->count) {               // If new size is really new
    Data *new_data =                            // Allocate data if necessary
      (new_count > 0 ? new Data[new_count] : 0);

    if (this->count <= new_count) {             // Copy old data into new
      Counter i;
      for (i = 0; i < this->count; i++)  
        new_data[i] = this->data[i];
      for (; i < new_count; i++)
        new_data[i] = 0;
    }
    else {                                     
      for (Counter i = 0; i < new_count; i++)  
        new_data[i] = this->data[i];
    }

    delete [] this->data;                       // Get rid of old data
    this->data = new_data;                      // Point to new data
    this->count = new_count;                    // Save new count
  }
}



// trim -- trim CoolBignum of excess data allotment
// Inputs:  none
// Outputs:  reference to modified CoolBignum

CoolBignum& CoolBignum::trim () {
  Counter i;
  for (i = this->count; i > 0; i--)             // Skip over high-order words
    if (this->data[i - 1] != 0) break;          //   that are zero
  if (i < this->count) {                        // If there are some such words
    Counter oldcount = this->count;
    this->count = i;                            // Update the count
    Data *new_data = (i > 0 ? new Data[i] : 0); // Allocate data if necessary
    for (; i > 0; i--)                          // Copy old data into new
      new_data[i - 1] = this->data[i - 1];
    delete [] this->data;                       // Delete old data
    this->data = new_data;                      // Point to new data
  }
  return *this;                                 // return reference to CoolBignum
}


// add -- add two CoolBignum values and save their sum
// Inputs:  references to two CoolBignum addends and the resulting sum
// Outputs:  none

void add (const CoolBignum& b1, const CoolBignum& b2, CoolBignum& sum) {
  const CoolBignum *bmax, *bmin;                        // Determine which of the two
  if (b1.count >= b2.count) {                   //   addends has the most
    bmax = &b1;                                 //   data.
    bmin = &b2;
  }
  else {
    bmax = &b2;
    bmin = &b1;
  }
  sum.data = ((sum.count = bmax->count) > 0 ?   // Allocate data for their sum
              new Data[sum.count] : 0);
  unsigned long temp, carry = 0;
  Counter i = 0;
  while (i < bmin->count) {                     // Add, element by element.
    // Add both elements and carry
    temp = (unsigned long)b1.data[i] + (unsigned long)b2.data[i] + carry;
    carry = temp/radix_s;                       // keep track of the carry
    sum.data[i] = Data(temp);                   // store sum
    i++;                                        // go to next element
  }
  while (i < bmax->count) {                     // bmin has no more elements
    temp = bmax->data[i] + carry;               // propagate the carry through
    carry = temp/radix_s;                       // the rest of bmax's elements
    sum.data[i] = Data(temp);                   // store sum
    i++;
  }
  if (carry) {                                  // if carry left over
    sum.resize(bmax->count + 1);                //   allocate another word
    sum.data[bmax->count] = 1;                  //   save the carry in it
  }
}



// subtract - subtract min CoolBignum from max CoolBignum (unsigned), result in diff
// Inputs:  references to CoolBignum
// Outputs:  none

void subtract (const CoolBignum& bmax, const CoolBignum& bmin, CoolBignum& diff) {
  diff.data = new Data[diff.count = bmax.count];// Allocate data for difference
  unsigned long temp;
  int borrow = 0;
  Counter i;
  for (i = 0; i < bmin.count; i++) {    // Subtract word by word.
    
    temp = (unsigned long)bmax.data[i] 
      + (unsigned long)radix_s - borrow;        // Add radix to bmax's data
    temp -= (unsigned long)bmin.data[i];        // Subtract off bmin's data
    borrow = (temp/radix_s == 0);               // Did we have to borrow?
    diff.data[i] = (Data) temp;                 // Reduce modulo radix and save
  }
  for (; i < bmax.count; i++) {                 // No more data for bmin
    temp = (unsigned long)bmax.data[i] 
      + (unsigned long)radix_s - borrow;        // Propagate the borrow through
    borrow = (temp/radix_s == 0);               //   rest of bmax's data
    diff.data[i] = (Data) temp;
  }
  diff.trim();                                  // Done. Now trim excess data
}



// magnitude_cmp - compare absolute values of two CoolBignums
// Inputs:  two CoolBignums
// Outputs:  result of comparison:  -1 if abs(b1) < abs(b2)
//                                   0 if abs(b1) == abs(b2)
//                                  +1 if abs(b1) > abs(b2)

int magnitude_cmp (const CoolBignum& b1, const CoolBignum& b2) {
  if (b1.count > b2.count) return 1;            // If one has more data than
  if (b2.count > b1.count) return -1;           //   the other, it wins
  Counter i = b1.count;                         // Else same number of elmts
  while (i > 0) {                               // Do lexicographic comparison
    if (b1.data[i - 1] > b2.data[i - 1])        
      return 1;                                 
    else if (b1.data[i - 1] < b2.data[i - 1])   
      return -1;
    i--;
  }                                             // No data, or all elmts same
  return 0;                                     //  so must be equal
}



// operator+ -- overloaded CoolBignum addition operator
// Inputs:  two references to CoolBignum addends
// Outputs:  new CoolBignum sum

CoolBignumE operator+ (const CoolBignum& b1, const CoolBignum& b2) {
  CoolBignum sum;                               // Init sum to zero
  if (b1.sign == b2.sign) {                     // If both have same sign
    add(b1,b2,sum);                             //   Do simple addition
    sum.sign = b1.sign;                         // Attach proper sign
  }
  else {                                        // Else different signs
    int mag = magnitude_cmp(b1,b2);             // Determine relative sizes
    if (mag > 0) {                              // If abs(b1) > abs(b2)
      subtract(b1,b2,sum);                      //   sum = b1 - b2
      sum.sign = b1.sign;                       // Sign of sum follows b1
    }
    else if (mag < 0) {                         // Else if abs(b1) < abs(b2)
      subtract(b2,b1,sum);                      //   sum = b2 - b1
      sum.sign = b2.sign;                       // Sign of sum follows b2
    }                                           // (Else abs(b1) == abs(b2)
  }                                             //   so sum must be zero)
  CoolBignumE& result = *((CoolBignumE*) &sum); // same physical object
  return result;                                // shallow swap on return
}


// multiply_aux -- multiply a CoolBignum by a "single digit"
// Inputs:  CoolBignum reference, single word multiplier, reference to the product,
//          and index of starting storage location to use in product
// Outputs:  none

void multiply_aux (const CoolBignum& b, Data d, CoolBignum& prod, Counter i) {
  // this function works just like normal multiplication by hand, in that the
  // top number is multiplied by the first digit of the bottom number, then the
  // second digit, and so on.  The only difference is that instead of doing all
  // of the multiplication before adding the rows, addition is done
  // concurrently.
  Counter j;
  if (i == 0) {                                 // if index is zero
    j = 0;                                      //   then zero out all of
    while (j < prod.count)                      //   prod's data elements
      prod.data[j++] = 0;                  
  }
  if (d != 0) {                                 // if d == 0, nothing to do
    unsigned long temp;
    Data carry = 0;

    Counter j;
    for (j = 0; j < b.count; j++) {     
      // for each of b's data elmts, multiply times d and add running product
      temp = (unsigned long)b.data[j] * (unsigned long)d
        + (unsigned long)prod.data[i + j] + carry;
      prod.data[i + j] = Data(temp % radix_s);  //   store result in product
      carry = Data(temp/radix_s);               //   keep track of carry
    }
    if (i+j < prod.count)
      prod.data[i + j] = carry;                 // Done.  Store the final carry
  }
}



// operator* -- overload * for CoolBignums
// Inputs:  references to two CoolBignum multiplicands
// Outputs:  CoolBignum product

CoolBignumE operator* (const CoolBignum& b1, const CoolBignum& b2) {
  CoolBignum prod;                              //   init product to zero
  if (b1 != zero_s && b2 != zero_s) {           // if neither multiplicand == 0
    prod.data =                                 //   allocate data for product
      new Data[prod.count = b1.count + b2.count];
    for (Counter i = 0; i < b2.count; i++)      //   multiply each b2 "digit" 
      multiply_aux(b1, b2.data[i], prod, i);    //   times b1 and add to total
    prod.sign = b1.sign * b2.sign;              //   determine correct sign
    prod.trim();                                //   trim excess data and ret.
  }
  CoolBignumE& result = *((CoolBignumE*) &prod);// same physical object
  return result;                                // shallow swap on return
}



// normalize -- normalize two CoolBignums  (Refer to Knuth, V.2, Section 4.3.1,
//              Algorithm D for details.  A digit here is one data element in
//              the radix 2**sizeof(Data).)
// Inputs:  references to two CoolBignums b1, b2, and their normalized counterparts
// Outputs:  the integral normalization factor used

Data normalize (const CoolBignum& b1, const CoolBignum& b2, CoolBignum& u, CoolBignum& v) {
  Data d =                                      // Calcualte normalization
    Data(radix_s/(((long)(b2.data[b2.count - 1])) + 1));        //   factor.
                //^^^^- JAM added this cast because Test#115 was overflowing resulting
                // in Divide Error because value was 65535 and wrapping to 0 with +1
  u.data = new Data[u.count = b1.count + 1];    // Get data for u (plus extra)
  v.data = new Data[v.count = b2.count];        // Get data for v
  u.data[b1.count] = 0;                         // Set u's leading digit to 0
  multiply_aux(b1,d,u,0);                       // u = b1 * d
  multiply_aux(b2,d,v,0);                       // v = b2 * d
  return d;                                     // return normalization factor
}



// divide_aux -- divide a CoolBignum by a "single digit" (Refer to Knuth, V.2,
//               Section 4.3.2, exercise 16 for details.  A digit here is one
//               data element in the radix 2**sizeof(Data).)
// Inputs:  reference to CoolBignum dividend, single digit divisor d, CoolBignum
//          quotient, and single digit remainder r
// Outputs:  none

void divide_aux (const CoolBignum& b1, Data d, CoolBignum& q, Data& r) {
  r = 0;                                        // init remainder to zero
  unsigned long temp;
  for (Counter j = b1.count; j > 0; j--) {
    temp = (unsigned long)r*radix_s 
      + (unsigned long)b1.data[j - 1];          // get remainder, append next
    if (j-1 < q.count) 
      q.data[j - 1] = Data(temp/d);             //   digit, then divide
    r = Data(temp % d);                         // calculate new remainder
  }
}


// estimate_q_hat -- estimate next dividend (Refer to Knuth, V.2, Section