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 138 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 433 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 444 of file vnl_bignum.cxx.

---

Member Function Documentation

vnl_bignum::operator short

(

)

const

Implicit conversion from a vnl_bignum to a short.

Definition at line 725 of file vnl_bignum.cxx.

vnl_bignum::operator int

(

)

const

Implicit conversion from a vnl_bignum to an int.

Definition at line 735 of file vnl_bignum.cxx.

vnl_bignum::operator long

(

)

const

Implicit conversion from a vnl_bignum to a long.

Definition at line 745 of file vnl_bignum.cxx.

vnl_bignum::operator float

(

)

const

Implicit conversion from a vnl_bignum to a float.

Definition at line 755 of file vnl_bignum.cxx.

vnl_bignum::operator double

(

)

const

Implicit conversion from a vnl_bignum to a double.

Definition at line 767 of file vnl_bignum.cxx.

vnl_bignum::operator long double

(

)

const

Implicit conversion from a vnl_bignum to a long double.

Definition at line 778 of file vnl_bignum.cxx.

vnl_bignum::operator short

(

)

[inline]

Definition at line 162 of file vnl_bignum.h.

vnl_bignum::operator int

(

)

[inline]

Definition at line 163 of file vnl_bignum.h.

vnl_bignum::operator long

(

)

[inline]

Definition at line 164 of file vnl_bignum.h.

vnl_bignum::operator float

(

)

[inline]

Definition at line 165 of file vnl_bignum.h.

vnl_bignum::operator double

(

)

[inline]

Definition at line 166 of file vnl_bignum.h.

vnl_bignum::operator long double

(

)

[inline]

Definition at line 167 of file vnl_bignum.h.

vnl_bignum vnl_bignum::operator-

(

)

const

Returns the negation of a vnl_bignum.

Definition at line 466 of file vnl_bignum.cxx.

vnl_bignum vnl_bignum::operator+

(

)

const [inline]

Definition at line 170 of file vnl_bignum.h.

vnl_bignum & vnl_bignum::operator=

(

const vnl_bignum &

)

Copies rhs vnl_bignum to lhs vnl_bignum.

Definition at line 451 of file vnl_bignum.cxx.

vnl_bignum vnl_bignum::operator<<

(

int

l

)

const

Shifts bignum to the left l digits.

Definition at line 602 of file vnl_bignum.cxx.

vnl_bignum vnl_bignum::operator>>

(

int

l

)

const

Shifts bignum to the right l digits.

Definition at line 618 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 516 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

)

[inline]

Definition at line 178 of file vnl_bignum.h.

vnl_bignum & vnl_bignum::operator *=

(

vnl_bignum const &

r

)

Multiplies this with a vnl_bignum.

Definition at line 546 of file vnl_bignum.cxx.

vnl_bignum & vnl_bignum::operator/=

(

vnl_bignum const &

r

)

Divides this by a vnl_bignum.

Definition at line 568 of file vnl_bignum.cxx.

vnl_bignum & vnl_bignum::operator%=

(

vnl_bignum const &

r

)

Divides this by a vnl_bignum and replaces this by remainder.

Definition at line 585 of file vnl_bignum.cxx.

vnl_bignum& vnl_bignum::operator<<=

(

int

l

)

[inline]

Definition at line 182 of file vnl_bignum.h.

vnl_bignum& vnl_bignum::operator>>=

(

int

l

)

[inline]

Definition at line 183 of file vnl_bignum.h.

vnl_bignum & vnl_bignum::operator++

(

)

prefix increment (++b).

Definition at line 477 of file vnl_bignum.cxx.

vnl_bignum & vnl_bignum::operator--

(

)

decrement.

Definition at line 497 of file vnl_bignum.cxx.

vnl_bignum vnl_bignum::operator++

(

int

)

[inline]

postfix increment (b++).

Definition at line 190 of file vnl_bignum.h.

vnl_bignum vnl_bignum::operator--

(

int

)

[inline]

decrement.

Definition at line 192 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 634 of file vnl_bignum.cxx.

bool vnl_bignum::operator<

(

vnl_bignum const &

)

const

Compares two vnl_bignums.

Definition at line 648 of file vnl_bignum.cxx.

bool vnl_bignum::operator!=

(

vnl_bignum const &

r

)

const [inline]

Definition at line 196 of file vnl_bignum.h.

bool vnl_bignum::operator>

(

vnl_bignum const &

r

)

const [inline]

Definition at line 197 of file vnl_bignum.h.

bool vnl_bignum::operator<=

(

vnl_bignum const &

r

)

const [inline]

Definition at line 198 of file vnl_bignum.h.

bool vnl_bignum::operator>=

(

vnl_bignum const &

r

)

const [inline]

Definition at line 199 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!=

(

long

r

)

const [inline]

Definition at line 201 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>

(

long

r

)

const [inline]

Definition at line 203 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>=

(

long

r

)

const [inline]

Definition at line 205 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!=

(

int

r

)

const [inline]

Definition at line 207 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>

(

int

r

)

const [inline]

Definition at line 209 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>=

(

int

r

)

const [inline]

Definition at line 211 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!=

(

double

r

)

const [inline]

Definition at line 213 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>

(

double

r

)

const [inline]

Definition at line 215 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>=

(

double

r

)

const [inline]

Definition at line 217 of file vnl_bignum.h.

bool vnl_bignum::operator==

(

long double

r

)

const [inline]

Definition at line 218 of file vnl_bignum.h.

bool vnl_bignum::operator!=

(

long double

r

)

const [inline]

Definition at line 219 of file vnl_bignum.h.

bool vnl_bignum::operator<

(

long double

r

)

const [inline]

Definition at line 220 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<=

(

long double

r

)

const [inline]

Definition at line 222 of file vnl_bignum.h.

bool vnl_bignum::operator>=

(

long double

r

)

const [inline]

Definition at line 223 of file vnl_bignum.h.

vnl_bignum vnl_bignum::abs

(

)

const [inline]

Definition at line 225 of file vnl_bignum.h.

bool vnl_bignum::is_infinity

(

)

const [inline]

Definition at line 228 of file vnl_bignum.h.

bool vnl_bignum::is_plus_infinity

(

)

const [inline]

Definition at line 229 of file vnl_bignum.h.

bool vnl_bignum::is_minus_infinity

(

)

const [inline]

Definition at line 230 of file vnl_bignum.h.

void vnl_bignum::dump

(

vcl_ostream &

= vcl_cout

)

const

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

Definition at line 789 of file vnl_bignum.cxx.

void vnl_bignum::xtoBigNum

(

const char *

s

)

[private]

convert hex string to vnl_bignum.

Definition at line 853 of file vnl_bignum.cxx.

int vnl_bignum::dtoBigNum

(

const char *

s

)

[private]

Converts decimal string to a vnl_bignum.

Definition at line 812 of file vnl_bignum.cxx.

void vnl_bignum::otoBigNum

(

const char *

s

)

[private]

convert octal string to vnl_bignum.

Definition at line 868 of file vnl_bignum.cxx.

void vnl_bignum::exptoBigNum

(

const char *

s

)

[private]

convert exponential string to a vnl_bignum.

Definition at line 828 of file vnl_bignum.cxx.

void vnl_bignum::resize

(

short

)

[private]

change the data allotment for a vnl_bignum.

Definition at line 882 of file vnl_bignum.cxx.

vnl_bignum & vnl_bignum::trim

(

)

[private]

trim non-infinite vnl_bignum of excess data allotment.

Definition at line 908 of file vnl_bignum.cxx.

---

Friends And Related Function Documentation

int magnitude_cmp	(	const vnl_bignum &	,
		const vnl_bignum &
	)			[friend]

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)

Definition at line 1026 of file vnl_bignum.cxx.

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 927 of file vnl_bignum.cxx.

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

subtract bmin from bmax (unsigned, non-infinite), result in diff.

Definition at line 983 of file vnl_bignum.cxx.

void increment

(

vnl_bignum &

bnum

)

[friend]

Add 1 to bnum (unsigned, non-infinite).

Definition at line 963 of file vnl_bignum.cxx.

void decrement

(

vnl_bignum &

bnum

)

[friend]

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

Definition at line 1006 of file vnl_bignum.cxx.

void multiply_aux	(	const vnl_bignum &	,
		unsigned	short,
		vnl_bignum &	,
		unsigned	short
	)			[friend]

unsigned short normalize	(	const vnl_bignum &	,
		const vnl_bignum &	,
		vnl_bignum &	,
		vnl_bignum &
	)			[friend]

normalize two vnl_bignums.

(Refer to Knuth, V.2, Section 4.3.1, Algorithm D for details. A digit here is one data element in the radix 2**2.)

• Inputs: references to two vnl_bignums b1, b2
• Outputs: their normalized counterparts u and v, and the integral normalization factor used

Definition at line 1084 of file vnl_bignum.cxx.

void divide_aux	(	const vnl_bignum &	,
		unsigned	short,
		vnl_bignum &	,
		unsigned short &
	)			[friend]

unsigned short estimate_q_hat	(	const vnl_bignum &	,
		const vnl_bignum &	,
		unsigned	short
	)			[friend]

unsigned short multiply_subtract	(	vnl_bignum &	,
		const vnl_bignum &	,
		unsigned	short,
		unsigned	short
	)			[friend]

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 Algorithm D.)

• Inputs: references to a vnl_bignum dividend b1, divisor b2, quotient q, and remainder r.

Definition at line 1241 of file vnl_bignum.cxx.

vnl_bignum left_shift	(	const vnl_bignum &	b1,
		int	l
	)			[friend]

left shift (arithmetic) non-infinite vnl_bignum by positive number.

• Inputs: reference to vnl_bignum, positive shift value
• Outputs: vnl_bignum, multiplied by the corresponding power of two

Definition at line 1314 of file vnl_bignum.cxx.

vnl_bignum right_shift	(	const vnl_bignum &	b1,
		int	l
	)