Main Page | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members | Related Pages

vnl_bignum Class Reference

#include <vnl_bignum.h>

List of all members.

Detailed Description

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)

Definition at line 137 of file vnl_bignum.h.

Public Member Functions

 vnl_bignum ()
 Creates a zero vnl_bignum.
 vnl_bignum (long)
 Creates a vnl_bignum from a long integer.
 vnl_bignum (unsigned long)
 Creates a vnl_bignum from an unsigned long integer.
 vnl_bignum (int)
 Creates a vnl_bignum from an integer.
 vnl_bignum (unsigned int)
 Creates a vnl_bignum from an unsigned integer.
 vnl_bignum (float)
 Creates a vnl_bignum from a single-precision floating point number.
 vnl_bignum (double)
 Creates a vnl_bignum from a double floating point number.
 vnl_bignum (long double)
 Creates a vnl_bignum from a "long double" floating point number.
 vnl_bignum (vnl_bignum const &)
 Copies the contents of vnl_bignum b.
 vnl_bignum (const char *)
 Creates a vnl_bignum from the character string representation.
 ~vnl_bignum ()
 Frees space for vnl_bignum.
 operator short () const
 Implicit conversion from a vnl_bignum to a short.
 operator int () const
 Implicit conversion from a vnl_bignum to an int.
 operator long () const
 Implicit conversion from a vnl_bignum to a long.
 operator float () const
 Implicit conversion from a vnl_bignum to a float.
 operator double () const
 Implicit conversion from a vnl_bignum to a double.
 operator long double () const
 Implicit conversion from a vnl_bignum to a long double.
 operator short ()
 operator int ()
 operator long ()
 operator float ()
 operator double ()
 operator long double ()
vnl_bignum operator- () const
 Returns the negation of a vnl_bignum.
vnl_bignum operator+ () const
vnl_bignum & operator= (const vnl_bignum &)
 Copies rhs vnl_bignum to lhs vnl_bignum.
vnl_bignum operator<< (int l) const
 Shifts bignum to the left l digits.
vnl_bignum operator>> (int l) const
 Shifts bignum to the right l digits.
vnl_bignum operator+ (vnl_bignum const &r) const
 Adds two vnl_bignums, and returns new sum.
vnl_bignum & operator+= (vnl_bignum const &r)
vnl_bignum & operator-= (vnl_bignum const &r)
vnl_bignum & operator *= (vnl_bignum const &r)
 Multiplies this with a vnl_bignum.
vnl_bignum & operator/= (vnl_bignum const &r)
 Divides this by a vnl_bignum.
vnl_bignum & operator%= (vnl_bignum const &r)
 Divides this by a vnl_bignum and replaces this by remainder.
vnl_bignum & operator<<= (int l)
vnl_bignum & operator>>= (int l)
vnl_bignum & operator++ ()
 prefix increment (++b).
vnl_bignum & operator-- ()
 decrement.
vnl_bignum operator++ (int)
 postfix increment (b++).
vnl_bignum operator-- (int)
 decrement.
bool operator== (vnl_bignum const &) const
 Two vnl_bignums are equal if and only if they have the same integer representation.
bool operator< (vnl_bignum const &) const
 Compares two vnl_bignums.
bool operator!= (vnl_bignum const &r) const
bool operator> (vnl_bignum const &r) const
bool operator<= (vnl_bignum const &r) const
bool operator>= (vnl_bignum const &r) const
bool operator== (long r) const
bool operator!= (long r) const
bool operator< (long r) const
bool operator> (long r) const
bool operator<= (long r) const
bool operator>= (long r) const
bool operator== (int r) const
bool operator!= (int r) const
bool operator< (int r) const
bool operator> (int r) const
bool operator<= (int r) const
bool operator>= (int r) const
bool operator== (double r) const
bool operator!= (double r) const
bool operator< (double r) const
bool operator> (double r) const
bool operator<= (double r) const
bool operator>= (double r) const
bool operator== (long double r) const
bool operator!= (long double r) const
bool operator< (long double r) const
bool operator> (long double r) const
bool operator<= (long double r) const
bool operator>= (long double r) const
vnl_bignum abs () const
bool is_infinity () const
bool is_plus_infinity () const
bool is_minus_infinity () const
void dump (vcl_ostream &=vcl_cout) const
 dump the contents of a vnl_bignum to a stream, default cout.

Private Member Functions

void xtoBigNum (const char *s)
 convert hex string to vnl_bignum.
int dtoBigNum (const char *s)
 Converts decimal string to a vnl_bignum.
void otoBigNum (const char *s)
 convert octal string to vnl_bignum.
void exptoBigNum (const char *s)
 convert exponential string to a vnl_bignum.
void resize (short)
 change the data allotment for a vnl_bignum.
vnl_bignum & trim ()
 trim non-infinite vnl_bignum of excess data allotment.

Private Attributes

unsigned short count
int sign
unsigned short * data

Friends

int magnitude_cmp (const vnl_bignum &, const vnl_bignum &)
 compare absolute values of two vnl_bignums.
void add (const vnl_bignum &, const vnl_bignum &, vnl_bignum &)
 add two non-infinite vnl_bignum values and save their sum.
void subtract (const vnl_bignum &, const vnl_bignum &, vnl_bignum &)
 subtract bmin from bmax (unsigned, non-infinite), result in diff.
void increment (vnl_bignum &bnum)
 Add 1 to bnum (unsigned, non-infinite).
void decrement (vnl_bignum &bnum)
 Subtract 1 to bnum (unsigned, non-infinite, non-zero).
void multiply_aux (const vnl_bignum &, unsigned short, vnl_bignum &, unsigned short)
unsigned short normalize (const vnl_bignum &, const vnl_bignum &, vnl_bignum &, vnl_bignum &)
 normalize two vnl_bignums.
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 &)
 divide b2 into b1, getting quotient q and remainder r.
vnl_bignum left_shift (const vnl_bignum &b1, int l)
 left shift (arithmetic) non-infinite vnl_bignum by positive number.
vnl_bignum right_shift (const vnl_bignum &b1, int l)
 right shift (arithmetic) non-infinite vnl_bignum by positive number.
vcl_ostream & operator<< (vcl_ostream &, const vnl_bignum &)
 Formatted output for bignum.
vcl_istream & operator>> (vcl_istream &, vnl_bignum &)
 Reads a vnl_bignum from a stream.
vcl_string & vnl_bignum_to_string (vcl_string &s, const vnl_bignum &b)
 Convert the number to a decimal representation in a string.
vnl_bignum & vnl_bignum_from_string (vnl_bignum &b, const vcl_string &s)
 Convert the number from a decimal representation in a string.

Related Functions

(Note that these are not member functions.)

vnl_bignum operator+ (vnl_bignum const &r1, long r2)
 Returns the sum of two bignum numbers.
vnl_bignum operator- (vnl_bignum const &r1, vnl_bignum const &r2)
 Returns the difference of two bignum numbers.
vnl_bignum operator * (vnl_bignum const &r1, vnl_bignum const &r2)
 Returns the product of two bignum numbers.
vnl_bignum operator/ (vnl_bignum const &r1, vnl_bignum const &r2)
 Returns the division of two bignum numbers.
vnl_bignum operator% (vnl_bignum const &r1, vnl_bignum const &r2)
 Returns the remainder of r1 divided by r2.

Constructor & Destructor Documentation

vnl_bignum::vnl_bignum (   ) 
 

Creates a zero vnl_bignum.

Definition at line 22 of file vnl_bignum.cxx.

vnl_bignum::vnl_bignum (  long   ) 
 

Creates a vnl_bignum from a long integer.

Definition at line 29 of file vnl_bignum.cxx.

vnl_bignum::vnl_bignum (  unsigned  long  ) 
 

Creates a vnl_bignum from an unsigned long integer.

Definition at line 77 of file vnl_bignum.cxx.

vnl_bignum::vnl_bignum (  int   ) 
 

Creates a vnl_bignum from an integer.

Definition at line 53 of file vnl_bignum.cxx.

vnl_bignum::vnl_bignum (  unsigned  int  ) 
 

Creates a vnl_bignum from an unsigned integer.

Definition at line 97 of file vnl_bignum.cxx.

vnl_bignum::vnl_bignum (  float   ) 
 

Creates a vnl_bignum from a single-precision floating point number.

Definition at line 117 of file vnl_bignum.cxx.

vnl_bignum::vnl_bignum (  double   ) 
 

Creates a vnl_bignum from a double floating point number.

Definition at line 148 of file vnl_bignum.cxx.

vnl_bignum::vnl_bignum (  long  double  ) 
 

Creates a vnl_bignum from a "long double" floating point number.

Definition at line 178 of file vnl_bignum.cxx.

vnl_bignum::vnl_bignum (  vnl_bignum const &   ) 
 

Copies the contents of vnl_bignum b.

Definition at line 432 of file vnl_bignum.cxx.

vnl_bignum::vnl_bignum (  const char *   ) 
 

Creates a vnl_bignum from the character string representation.

Definition at line 374 of file vnl_bignum.cxx.

vnl_bignum::~vnl_bignum (   ) 
 

Frees space for vnl_bignum.

Definition at line 443 of file vnl_bignum.cxx.

Member Function Documentation

vnl_bignum vnl_bignum::abs (   )  const [inline]
 

Definition at line 224 of file vnl_bignum.h.

int vnl_bignum::dtoBigNum (  const char *  s  )  [private]
 

Converts decimal string to a vnl_bignum.

Definition at line 810 of file vnl_bignum.cxx.

void vnl_bignum::dump (  vcl_ostream &  = vcl_cout  )  const
 

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

Definition at line 788 of file vnl_bignum.cxx.

void vnl_bignum::exptoBigNum (  const char *  s  )  [private]
 

convert exponential string to a vnl_bignum.

Definition at line 826 of file vnl_bignum.cxx.

bool vnl_bignum::is_infinity (   )  const [inline]
 

Definition at line 227 of file vnl_bignum.h.

bool vnl_bignum::is_minus_infinity (   )  const [inline]
 

Definition at line 229 of file vnl_bignum.h.

bool vnl_bignum::is_plus_infinity (   )  const [inline]
 

Definition at line 228 of file vnl_bignum.h.

vnl_bignum & vnl_bignum::operator *= (  vnl_bignum const &  r  ) 
 

Multiplies this with a vnl_bignum.

Definition at line 545 of file vnl_bignum.cxx.

vnl_bignum::operator double (   )  [inline]
 

Definition at line 165 of file vnl_bignum.h.

vnl_bignum::operator double (   )  const
 

Implicit conversion from a vnl_bignum to a double.

Definition at line 766 of file vnl_bignum.cxx.

vnl_bignum::operator float (   )  [inline]
 

Definition at line 164 of file vnl_bignum.h.

vnl_bignum::operator float (   )  const
 

Implicit conversion from a vnl_bignum to a float.

Definition at line 754 of file vnl_bignum.cxx.

vnl_bignum::operator int (   )  [inline]
 

Definition at line 162 of file vnl_bignum.h.

vnl_bignum::operator int (   )  const
 

Implicit conversion from a vnl_bignum to an int.

Definition at line 734 of file vnl_bignum.cxx.

vnl_bignum::operator long (   )  [inline]
 

Definition at line 163 of file vnl_bignum.h.

vnl_bignum::operator long (   )  const
 

Implicit conversion from a vnl_bignum to a long.

Definition at line 744 of file vnl_bignum.cxx.

vnl_bignum::operator long double (   )  [inline]
 

Definition at line 166 of file vnl_bignum.h.

vnl_bignum::operator long double (   )  const
 

Implicit conversion from a vnl_bignum to a long double.

Definition at line 777 of file vnl_bignum.cxx.

vnl_bignum::operator short (   )  [inline]
 

Definition at line 161 of file vnl_bignum.h.

vnl_bignum::operator short (   )  const
 

Implicit conversion from a vnl_bignum to a short.

Definition at line 724 of file vnl_bignum.cxx.

bool vnl_bignum::operator!= (  long double  r  )  const [inline]
 

Definition at line 218 of file vnl_bignum.h.

bool vnl_bignum::operator!= (  double  r  )  const [inline]
 

Definition at line 212 of file vnl_bignum.h.

bool vnl_bignum::operator!= (  int  r  )  const [inline]
 

Definition at line 206 of file vnl_bignum.h.

bool vnl_bignum::operator!= (  long  r  )  const [inline]
 

Definition at line 200 of file vnl_bignum.h.

bool vnl_bignum::operator!= (  vnl_bignum const &  r  )  const [inline]
 

Definition at line 195 of file vnl_bignum.h.

vnl_bignum & vnl_bignum::operator%= (  vnl_bignum const &  r  ) 
 

Divides this by a vnl_bignum and replaces this by remainder.

Definition at line 584 of file vnl_bignum.cxx.

vnl_bignum vnl_bignum::operator+ (  vnl_bignum const &  r  )  const
 

Adds two vnl_bignums, and returns new sum.

Definition at line 515 of file vnl_bignum.cxx.

vnl_bignum vnl_bignum::operator+ (   )  const [inline]
 

Definition at line 169 of file vnl_bignum.h.

vnl_bignum vnl_bignum::operator++ (  int   )  [inline]
 

postfix increment (b++).

Definition at line 189 of file vnl_bignum.h.

vnl_bignum & vnl_bignum::operator++ (   ) 
 

prefix increment (++b).

Definition at line 476 of file vnl_bignum.cxx.

vnl_bignum& vnl_bignum::operator+= (  vnl_bignum const &  r  )  [inline]
 

Definition at line 176 of file vnl_bignum.h.

vnl_bignum vnl_bignum::operator- (   )  const
 

Returns the negation of a vnl_bignum.

Definition at line 465 of file vnl_bignum.cxx.

vnl_bignum vnl_bignum::operator-- (  int   )  [inline]
 

decrement.

Definition at line 191 of file vnl_bignum.h.

vnl_bignum & vnl_bignum::operator-- (   ) 
 

decrement.

Definition at line 496 of file vnl_bignum.cxx.

vnl_bignum& vnl_bignum::operator-= (  vnl_bignum const &  r  )  [inline]
 

Definition at line 177 of file vnl_bignum.h.

vnl_bignum & vnl_bignum::operator/= (  vnl_bignum const &  r  ) 
 

Divides this by a vnl_bignum.

Definition at line 567 of file vnl_bignum.cxx.

bool vnl_bignum::operator< (  long double  r  )  const [inline]
 

Definition at line 219 of file vnl_bignum.h.

bool vnl_bignum::operator< (  double  r  )  const [inline]
 

Definition at line 213 of file vnl_bignum.h.

bool vnl_bignum::operator< (  int  r  )  const [inline]
 

Definition at line 207 of file vnl_bignum.h.

bool vnl_bignum::operator< (  long  r  )  const [inline]
 

Definition at line 201 of file vnl_bignum.h.

bool vnl_bignum::operator< (  vnl_bignum const &   )  const
 

Compares two vnl_bignums.

Definition at line 647 of file vnl_bignum.cxx.

vnl_bignum vnl_bignum::operator<< (  int  l  )  const
 

Shifts bignum to the left l digits.

Definition at line 601 of file vnl_bignum.cxx.

vnl_bignum& vnl_bignum::operator<<= (  int  l  )  [inline]
 

Definition at line 181 of file vnl_bignum.h.

bool vnl_bignum::operator<= (  long double  r  )  const [inline]
 

Definition at line 221 of file vnl_bignum.h.

bool vnl_bignum::operator<= (  double  r  )  const [inline]
 

Definition at line 215 of file vnl_bignum.h.

bool vnl_bignum::operator<= (  int  r  )  const [inline]
 

Definition at line 209 of file vnl_bignum.h.

bool vnl_bignum::operator<= (  long  r  )  const [inline]
 

Definition at line 203 of file vnl_bignum.h.

bool vnl_bignum::operator<= (  vnl_bignum const &  r  )  const [inline]
 

Definition at line 197 of file vnl_bignum.h.

vnl_bignum & vnl_bignum::operator= (  const vnl_bignum &   ) 
 

Copies rhs vnl_bignum to lhs vnl_bignum.

Definition at line 450 of file vnl_bignum.cxx.

bool vnl_bignum::operator== (  long double  r  )  const [inline]
 

Definition at line 217 of file vnl_bignum.h.

bool vnl_bignum::operator== (  double  r  )  const [inline]
 

Definition at line 211 of file vnl_bignum.h.

bool vnl_bignum::operator== (  int  r  )  const [inline]
 

Definition at line 205 of file vnl_bignum.h.

bool vnl_bignum::operator== (  long  r  )  const [inline]
 

Definition at line 199 of file vnl_bignum.h.

bool vnl_bignum::operator== (  vnl_bignum const &   )  const
 

Two vnl_bignums are equal if and only if they have the same integer representation.

Definition at line 633 of file vnl_bignum.cxx.

bool vnl_bignum::operator> (  long double  r  )  const [inline]
 

Definition at line 220 of file vnl_bignum.h.

bool vnl_bignum::operator> (  double  r  )  const [inline]
 

Definition at line 214 of file vnl_bignum.h.

bool vnl_bignum::operator> (  int  r  )  const [inline]
 

Definition at line 208 of file vnl_bignum.h.

bool vnl_bignum::operator> (  long  r  )  const [inline]
 

Definition at line 202 of file vnl_bignum.h.

bool vnl_bignum::operator> (  vnl_bignum const &  r  )  const [inline]
 

Definition at line 196 of file vnl_bignum.h.

bool vnl_bignum::operator>= (  long double  r  )  const [inline]
 

Definition at line 222 of file vnl_bignum.h.

bool vnl_bignum::operator>= (  double  r  )  const [inline]
 

Definition at line 216 of file vnl_bignum.h.

bool vnl_bignum::operator>= (  int  r  )  const [inline]
 

Definition at line 210 of file vnl_bignum.h.

bool vnl_bignum::operator>= (  long  r  )  const [inline]
 

Definition at line 204 of file vnl_bignum.h.

bool vnl_bignum::operator>= (  vnl_bignum const &  r  )  const [inline]
 

Definition at line 198 of file vnl_bignum.h.

vnl_bignum vnl_bignum::operator>> (  int  l  )  const
 

Shifts bignum to the right l digits.

Definition at line 617 of file vnl_bignum.cxx.

vnl_bignum& vnl_bignum::operator>>= (  int  l  )  [inline]
 

Definition at line 182 of file vnl_bignum.h.

void vnl_bignum::otoBigNum (  const char *  s  )  [private]
 

convert octal string to vnl_bignum.

Definition at line 866 of file vnl_bignum.cxx.

void vnl_bignum::resize (  short   )  [private]
 

change the data allotment for a vnl_bignum.

Definition at line 880 of file vnl_bignum.cxx.

vnl_bignum & vnl_bignum::trim (   )  [private]
 

trim non-infinite vnl_bignum of excess data allotment.

Definition at line 906 of file vnl_bignum.cxx.

void vnl_bignum::xtoBigNum (  const char *  s  )  [private]
 

convert hex string to vnl_bignum.

Definition at line 851 of file vnl_bignum.cxx.

Friends And Related Function Documentation

void add (  const vnl_bignum &  ,
const vnl_bignum &  ,
vnl_bignum & 
)  [friend]
 

add two non-infinite vnl_bignum values and save their sum.

Definition at line 925 of file vnl_bignum.cxx.

void decrement (  vnl_bignum &  bnum  )  [friend]
 

Subtract 1 to bnum (unsigned, non-infinite, non-zero).

Definition at line 1002 of file vnl_bignum.cxx.

void divide (  const vnl_bignum &  ,
const vnl_bignum &  ,
vnl_bignum &  ,
vnl_bignum & 
)  [friend]
 

divide b2 into b1, getting quotient q and remainder r.

(Refer to Knuth, V.2, Section 4.3.1, Algorithm D for details. This function implements