vnl_bignum.cxx

InsightToolkit-1.4.0(有大量的优化算法程序)

  Counter i = 0;
  do {                                  // repeat:
    divide(d,10L,q,r);                  //   Divide vnl_bignum by ten
    cbuf[i++] = char(long(r) + '0');    //   Get one's digit
    d = q;                              //   Then discard one's digit
    q = r = 0L;                         //   Prep for next divide
  } while (d != 0L);                    // until no more one's digits
  do {                                  // repeat;
    os << cbuf[--i];                    //   output char buf in reverse
  } while (i);                          // until no more chars
  delete [] cbuf;                       // delete temp char buf
  return os;                            // return output stream
}

//: Convert the number to a decimal representation in a string.
vcl_string& vnl_bignum_to_string (vcl_string& s, const vnl_bignum& b)
{
  s.erase();
  vcl_string::size_type insert_point = 0; // keep record of location of first number.

  vnl_bignum d = b;                     // Copy the input vnl_bignum
  if (d.sign == -1) {                   // If it's negative
    s.insert(insert_point,"-");         //   Output leading minus sign
    d.sign = 1;                         //   Make d positive for divide
    ++insert_point;                     // keep record of location of first number.
  }
  if (d.is_infinity()) return s+="Inf";
  vnl_bignum q,r;                       // Temp quotient and remainder
  do {                                  // repeat:
    divide(d,10L,q,r);                  //   Divide vnl_bignum by ten
    s.insert(insert_point, 1, char('0'+long(r))); //   Get one's digit, and insert it at head.
    d = q;                              //   Then discard one's digit
    q = r = 0L;                         //   Prep for next divide
  } while (d != 0L);                    // until no more one's digits
  return s;
}

//: Convert the number from a decimal representation in a string.
vnl_bignum& vnl_bignum_from_string (vnl_bignum& b, const vcl_string& s)
{
  // decimal:     "^ *[-+]?[1-9][0-9]*$"
  // Infinity:    "^ *[-+]?Inf(inity)?$"

  if (is_plus_inf(s.c_str()))
    b=vnl_bignum("+Inf");
  else if (is_minus_inf(s.c_str()))
    b=vnl_bignum("-Inf");
  else
    b.dtoBigNum(s.c_str());             // convert decimal to vnl_bignum
  return b; 
}


//: Implicit conversion from a vnl_bignum to a short.
vnl_bignum::operator short () const
{
  short s = 0;
  for (Counter i = this->count; i > 0; )
    s = short(s*0x10000 + this->data[--i]);
  return this->sign*s;
}


//: Implicit conversion from a vnl_bignum to an int.
vnl_bignum::operator int () const
{
  int j = 0;
  for (Counter i = this->count; i > 0; )
    j = int(j*0x10000 + this->data[--i]);
  return this->sign*j;
}


//: Implicit conversion from a vnl_bignum to a long.
vnl_bignum::operator long () const
{
  long l = 0;
  for (Counter i = this->count; i > 0; )
    l = l*0x10000L + this->data[--i];
  return this->sign*l;
}


//: Implicit conversion from a vnl_bignum to a float.
vnl_bignum::operator float () const
{
  float f = 0.0f;
  for (Counter i = this->count; i > 0; )
    f = f*0x10000 + this->data[--i];
  if (this->is_infinity()) f = 1.0f / zerof; // create inf
  return this->sign*f;
}


//: Implicit conversion from a vnl_bignum to a double.

vnl_bignum::operator double () const
{
  double d = 0.0;
  for (Counter i = this->count; i > 0; )
    d = d*0x10000 + this->data[--i];
  if (this->is_infinity()) d = 1.0 / zerod; // create inf
  return this->sign*d;
}

//: Implicit conversion from a vnl_bignum to a long double.

vnl_bignum::operator long double () const
{
  long double d = 0.0;
  for (Counter i = this->count; i > 0; )
    d = d*0x10000 + this->data[--i];
  if (this->is_infinity()) d = 1.0L / zerold; // create inf
  return this->sign*d;
}

//: dump the contents of a vnl_bignum to a stream, default cout.

void vnl_bignum::dump (vcl_ostream& os) const
{
  os << "{count=" << this->count       // output count field
     << ", sign=" << this->sign        // output sign field
     << ", data=" << this->data        // output data pointer
     << ", value=" << *this
     << ", {";
  // format string == "%04X%s" or "%02X%s", etc.
  //  static char format_str[10] =
  //    {'%','0',char(2*2 + '0'),'X','%','s'};
  //  format_str[2] = char(2*2 + '0');
  if (this->count > 0) { // output data array
    for (Counter i = this->count; i > 1; i--)
      os << (this->data[i - 1]) << ",";
    os << (this->data[0]);
  }
  os << "}}\n";                         // close brackets
}


//: Converts decimal string to a vnl_bignum.

int vnl_bignum::dtoBigNum (const char *s)
{
  this->resize(0); sign = 1;            // Reset number to 0. 
  Counter len = 0;                      // No chars converted yet
  while (*s == ' ' || *s == '\t' || *s == '\n' || *s == '\r') ++s; // skip whitespace
  if (s[0] == '-' || s[0] == '+') len++;// Skip over leading +,-
  while (vcl_isdigit(s[len])) {         // If current char is digit
    (*this) = ((*this) * 10L) +         // Shift vnl_bignum left a decimal
      vnl_bignum(long(s[len++] - '0')); // digit and add new digit
  }
  if (s[0] == '-') this->sign = -1;     // If s had leading -, note it
  return len;                           // Return # of chars processed
}

//: convert exponential string to a vnl_bignum

void vnl_bignum::exptoBigNum (const char *s)
{
  while (*s == ' ' || *s == '\t' || *s == '\n' || *s == '\r') ++s; // skip whitespace
  Counter pos = this->dtoBigNum(s) + 1; // Convert the base, skip [eE]
  long pow = atol(s + pos);             // Convert the exponent to long
  while (pow-- > 0)                     // Raise vnl_bignum to the given
    *this = (*this) * 10L;              // power
}


//: convert hex character to integer hex value (ASCII or EBCDIC)
// - Inputs:  character representation of a hex number
// - Outputs: integer value of the hex number

unsigned int ctox (int c)
{
  if ('0' <= c && c <= '9')
    return c - '0';
  if ('a' <= c && c <= 'f')
    return c - 'a' + 10;
  return c - 'A' + 10;
}

//: convert hex string to vnl_bignum

void vnl_bignum::xtoBigNum (const char *s)
{
  this->resize(0); sign = 1;            // Reset number to 0. 
  while (*s == ' ' || *s == '\t' || *s == '\n' || *s == '\r') ++s; // skip whitespace
  Counter size = vcl_strlen(s);
  Counter len = 2;                      // skip leading "0x"
  while (len < size) {                  // While there are more chars
    (*this) = ((*this) * 16L) +         // Shift vnl_bignum left one hex
      vnl_bignum(long(ctox(s[len++]))); //   digit and add next digit
  }
}


//: convert octal string to vnl_bignum

void vnl_bignum::otoBigNum (const char *s)
{
  this->resize(0); sign = 1;           // Reset number to 0. 
  while (*s == ' ' || *s == '\t' || *s == '\n' || *s == '\r') ++s; // skip whitespace
  Counter size = vcl_strlen(s);
  Counter len = 0;                      // No chars converted yet
  while (len < size) {                  // While there are more chars
    (*this) = ((*this) * 8L) +          // Shift vnl_bignum left 1 oct dig.
      vnl_bignum(long(s[len++] - '0')); // Add next character value
  }
}

//: change the data allotment for a vnl_bignum

void vnl_bignum::resize (short new_count)
{
  assert(new_count >= 0);
  if (new_count == this->count) return;
  Data *new_data = (new_count > 0 ? new Data[new_count] : 0); // Allocate data if necessary

  if (this->count <= new_count) {       // Copy old data into new
    short i = 0;
    for (; i < this->count; i++)
      new_data[i] = this->data[i];
    for (; i < new_count; i++)
      new_data[i] = 0;
  }
  else {
    for (short 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 non-infinite vnl_bignum of excess data allotment

vnl_bignum& vnl_bignum::trim ()
{
  Counter i = this->count;
  for (; 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
    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 vnl_bignum
}


//: add two non-infinite vnl_bignum values and save their sum

void add (const vnl_bignum& b1, const vnl_bignum& b2, vnl_bignum& sum)
{
  const vnl_bignum *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/0x10000L;              // 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/0x10000L;              // 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 bmin from bmax (unsigned, non-infinite), result in diff

void subtract (const vnl_bignum& bmax, const vnl_bignum& bmin, vnl_bignum& diff)
{
  diff.data = new Data[diff.count = bmax.count];// Allocate data for difference
  unsigned long temp;
  int borrow = 0;
  Counter i = 0;
  for (; i < bmin.count; i++) {                 // Subtract word by word.
    temp = (unsigned long)bmax.data[i] + 0x10000L - borrow; // Add radix to bmax's data
    temp -= (unsigned long)bmin.data[i];        // Subtract off bmin's data
    borrow = (temp/0x10000L == 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] + 0x10000L - borrow; // Propagate the borrow through
    borrow = (temp/0x10000L == 0);              //   rest of bmax's data
    diff.data[i] = (Data) temp;
  }
  diff.trim();                                  // Done. Now trim excess data
}


//: compare absolute values of two vnl_bignums
// 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 vnl_bignum& b1, const vnl_bignum& b2)
{
  if (b1.is_infinity()) return b2.is_infinity() ? 0 : 1;