vnl_bignum.h

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

// This is vxl/vnl/vnl_bignum.h
#ifndef vnl_bignum_h_
#define vnl_bignum_h_
//:
// \file
// \brief Infinite precision integers
//
// The vnl_bignum class implements near-infinite precision integers
// and arithmetic by using a dynamic bit vector. A
// vnl_bignum object will grow in size as necessary to hold its
// integer value.  Implicit conversion to the system defined
// types: short, int, long, float, double and long double
// is supported by overloaded operator member functions.
// Addition and subtraction operators are performed by
// simple bitwise addition and subtraction on
// unsigned short boundaries with checks for carry flag propagation.
// The multiplication, division, and remainder operations
// utilize the algorithms from Knuth's Volume 2 of "The
// Art of Computer Programming". However, despite the use of
// these algorithms and inline member functions, arithmetic
// operations on vnl_bignum objects are considerably slower than
// the built-in integer types that use hardware integer arithmetic
// capabilities.
//
// The vnl_bignum class supports the parsing of character string
// representations of all the literal number formats, PLUS the
// strings "Infinity", "+Infinity" and "-Infinity".  The following
// table shows an example of a character string
// representation on the left and a brief description of the
// interpreted meaning on the right:
//
// Character String  Interpreted Meaning
// 1234              1234
// 1234l             1234
// 1234L             1234
// 1234u             1234
// 1234U             1234
// 1234ul            1234
// 1234UL            1234
// 01234             1234 in octal (leading 0)
// 0x1234            1234 in hexadecimal (leading 0x)
// 0X1234            1234 in hexadecimal (leading 0X)
// 123.4             123 (value truncated)
// 1.234e2           123 (exponent expanded/truncated)
// 1.234e-5          0 (truncated value less than 1)
// Infinity          +Inf ("maxval", obeying all conventional arithmetic)
//
// \author
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// \verbatim
// Modifications
//  Peter Vanroose, 24 January 2002: ported to vnl from COOL
//  Peter Vanroose, 7 September 2002: added "Infinity" (incl. all arithmetic)
// \endverbatim

#include <vcl_iostream.h>
#include <vcl_string.h>

class vnl_bignum;

// These are all auxiliary functions:

int magnitude_cmp(const vnl_bignum&, const vnl_bignum&);
void add(const vnl_bignum&, const vnl_bignum&, vnl_bignum&);
void subtract(const vnl_bignum&, const vnl_bignum&, vnl_bignum&);
void multiply_aux(const vnl_bignum&, unsigned short d, vnl_bignum&, unsigned short i);
unsigned short normalize(const vnl_bignum&, const vnl_bignum&, vnl_bignum&, vnl_bignum&);
void divide_aux(const vnl_bignum&, unsigned short, vnl_bignum&, unsigned short&);
unsigned short estimate_q_hat(const vnl_bignum&, const vnl_bignum&, unsigned short);
unsigned short multiply_subtract(vnl_bignum&, const vnl_bignum&, unsigned short, unsigned short);
void divide(const vnl_bignum&, const vnl_bignum&, vnl_bignum&, vnl_bignum&);
vnl_bignum left_shift(const vnl_bignum& b1, int l);
vnl_bignum right_shift(const vnl_bignum& b1, int l);

//: formatted output
// \relates vnl_bignum
vcl_ostream& operator<<(vcl_ostream& s, vnl_bignum const& r);

//: simple input
// \relates vnl_bignum
vcl_istream& operator>>(vcl_istream& s, vnl_bignum& r);

//: Infinite precision integers
//
// The vnl_bignum class implements near-infinite precision integers
// and arithmetic by using a dynamic bit vector. A
// vnl_bignum object will grow in size as necessary to hold its
// integer value.  Implicit conversion to the system defined
// types: short, int, long, float, double and long double 
// is supported by overloaded operator member functions.
// Addition and subtraction operators are performed by
// simple bitwise addition and subtraction on
// unsigned short boundaries with checks for carry flag propagation.
// The multiplication, division, and remainder operations
// utilize the algorithms from Knuth's Volume 2 of "The
// Art of Computer Programming". However, despite the use of
// these algorithms and inline member functions, arithmetic
// operations on vnl_bignum objects are considerably slower than
// the built-in integer types that use hardware integer arithmetic
// capabilities.
//
// The vnl_bignum class supports the parsing of character string
// representations of all the literal number formats, PLUS the
// strings "Infinity", "+Infinity" and "-Infinity".  The following
// table shows an example of a character string
// representation on the left and a brief description of the
// interpreted meaning on the right:
//
// Character String  Interpreted Meaning
// 1234              1234
// 1234l             1234
// 1234L             1234
// 1234u             1234
// 1234U             1234
// 1234ul            1234
// 1234UL            1234
// 01234             1234 in octal (leading 0)
// 0x1234            1234 in hexadecimal (leading 0x)
// 0X1234            1234 in hexadecimal (leading 0X)
// 123.4             123 (value truncated)
// 1.234e2           123 (exponent expanded/truncated)
// 1.234e-5          0 (truncated value less than 1)
// Infinity          +Inf ("maxval", obeying all conventional arithmetic)
//
class vnl_bignum {
  unsigned short count; // Number of data elements (never 0 except for "0")
  int sign;             // Sign of vnl_bignum (+1 or -1, nothing else!!)
  unsigned short* data; // Pointer to data value
public:
  vnl_bignum();                        // Void constructor
  vnl_bignum(long);                    // Long constructor
  vnl_bignum(unsigned long);           // Unsigned Long constructor
  vnl_bignum(int);                     // Int constructor
  vnl_bignum(unsigned int);            // Unsigned Int constructor
  vnl_bignum(float);                   // Float constructor
  vnl_bignum(double);                  // Double constructor
  vnl_bignum(long double);             // Long Double constructor
  vnl_bignum(vnl_bignum const&);       // Copy constructor
  vnl_bignum(const char*);             // String constructor
  ~vnl_bignum();                       // Destructor

  operator short() const;              // Implicit type conversion
  operator int() const;                // Implicit type conversion
  operator long() const;               // Implicit type conversion
  operator float() const;              // Implicit type conversion
  operator double() const;             // Implicit type conversion
  operator long double() const;        // Implicit type conversion
#ifndef VCL_CAN_NOT_SPECIALIZE_CONST
  inline operator short() { return ((const vnl_bignum*)this)->operator short(); }
  inline operator int() { return ((const vnl_bignum*)this)->operator int(); }
  inline operator long() { return ((const vnl_bignum*)this)->operator long(); }
  inline operator float() { return ((const vnl_bignum*)this)->operator float(); }
  inline operator double() { return ((const vnl_bignum*)this)->operator double(); }
  inline operator long double() { return ((const vnl_bignum*)this)->operator long double(); }
#endif
  vnl_bignum operator-() const;        // Unary minus operator
  inline vnl_bignum operator+() { return *this; } // Unary plus operator
  inline vnl_bignum operator+() const { return *this; } // Unary plus operator

  vnl_bignum& operator=(const vnl_bignum&); // Assignment operator

  vnl_bignum operator<<(int l) const;  // Bit shift
  vnl_bignum operator>>(int l) const;  // Bit shift
  vnl_bignum operator+(vnl_bignum const& r) const;
  inline vnl_bignum& operator+=(vnl_bignum const& r) { return *this = operator+(r); }
  inline vnl_bignum& operator-=(vnl_bignum const& r) { return *this = operator+(-r); }
  vnl_bignum& operator*=(vnl_bignum const& r);
  vnl_bignum& operator/=(vnl_bignum const& r);
  vnl_bignum& operator%=(vnl_bignum const& r);
  inline vnl_bignum& operator<<=(int l) { return *this = *this << l; }
  inline vnl_bignum& operator>>=(int l) { return *this = *this >> l; }

  //: prefix increment (++b)
  vnl_bignum& operator++();
  //: decrement
  vnl_bignum& operator--();
  //: postfix increment (b++)
  inline vnl_bignum operator++(int) { vnl_bignum b=(*this); operator++(); return b; }
  //: decrement
  inline vnl_bignum operator--(int) { vnl_bignum b=(*this); operator--(); return b; }

  bool operator==(vnl_bignum const&) const; // equality
  bool operator< (vnl_bignum const&) const; // less than