core/vnl/vnl_bignum.h File Reference

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)

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.

   Modifications
    Peter Vanroose, 24 January 2002: ported to vnl from COOL
    Peter Vanroose, 7 September 2002: added "Infinity" (incl. all arithmetic)
    Ian Scott, 23 March 2004: made ++ and -- much more efficient.
    Peter Vanroose, March 2008: try to fix divide bug: partially succeeded

Definition in file vnl_bignum.h.

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

Go to the source code of this file.


Classes
class	vnl_bignum
	Infinite precision integers. More...
Functions
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	multiply_aux (const vnl_bignum &, unsigned short d, vnl_bignum &, unsigned short i)
	multiply a non-infinite vnl_bignum by a "single digit".
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.
void	decrement (vnl_bignum &bnum)
	Subtract 1 to bnum (unsigned, non-infinite, non-zero).
void	increment (vnl_bignum &bnum)
	Add 1 to bnum (unsigned, non-infinite).
vnl_bignum	operator+ (vnl_bignum const &r1, int r2)
vnl_bignum	operator+ (vnl_bignum const &r1, double r2)
vnl_bignum	operator+ (vnl_bignum const &r1, long double r2)
vnl_bignum	operator+ (long r2, vnl_bignum const &r1)
vnl_bignum	operator+ (int r2, vnl_bignum const &r1)
vnl_bignum	operator+ (double r2, vnl_bignum const &r1)
vnl_bignum	operator+ (long double r2, vnl_bignum const &r1)
vnl_bignum	operator- (vnl_bignum const &r1, long r2)
vnl_bignum	operator- (vnl_bignum const &r1, int r2)
vnl_bignum	operator- (vnl_bignum const &r1, double r2)
vnl_bignum	operator- (vnl_bignum const &r1, long double r2)
vnl_bignum	operator- (long r2, vnl_bignum const &r1)
vnl_bignum	operator- (int r2, vnl_bignum const &r1)
vnl_bignum	operator- (double r2, vnl_bignum const &r1)
vnl_bignum	operator- (long double r2, vnl_bignum const &r1)
vnl_bignum	operator * (vnl_bignum const &r1, long r2)
vnl_bignum	operator * (vnl_bignum const &r1, int r2)
vnl_bignum	operator * (vnl_bignum const &r1, double r2)
vnl_bignum	operator * (vnl_bignum const &r1, long double r2)
vnl_bignum	operator * (long r2, vnl_bignum const &r1)
vnl_bignum	operator * (int r2, vnl_bignum const &r1)
vnl_bignum	operator * (double r2, vnl_bignum const &r1)
vnl_bignum	operator * (long double r2, vnl_bignum const &r1)
vnl_bignum	operator/ (vnl_bignum const &r1, long r2)
vnl_bignum	operator/ (vnl_bignum const &r1, int r2)
vnl_bignum	operator/ (vnl_bignum const &r1, double r2)
vnl_bignum	operator/ (vnl_bignum const &r1, long double r2)
vnl_bignum	operator/ (long r1, vnl_bignum const &r2)
vnl_bignum	operator/ (int r1, vnl_bignum const &r2)
vnl_bignum	operator/ (double r1, vnl_bignum const &r2)
vnl_bignum	operator/ (long double r1, vnl_bignum const &r2)
vnl_bignum	operator% (vnl_bignum const &r1, long r2)
vnl_bignum	operator% (vnl_bignum const &r1, int r2)
vnl_bignum	operator% (long r1, vnl_bignum const &r2)
vnl_bignum	operator% (int r1, vnl_bignum const &r2)
bool	operator== (long r1, vnl_bignum const &r2)
bool	operator!= (long r1, vnl_bignum const &r2)
bool	operator< (long r1, vnl_bignum const &r2)
bool	operator> (long r1, vnl_bignum const &r2)
bool	operator<= (long r1, vnl_bignum const &r2)
bool	operator>= (long r1, vnl_bignum const &r2)
vnl_bignum	vnl_math_abs (vnl_bignum const &x)
vnl_bignum	vnl_math_squared_magnitude (vnl_bignum const &x)
vnl_bignum	vnl_math_sqr (vnl_bignum const &x)
bool	vnl_math_isnan (vnl_bignum const &)
bool	vnl_math_isfinite (vnl_bignum const &x)

Function Documentation

void add	(	const vnl_bignum &	,
		const vnl_bignum &	,
		vnl_bignum &
	)

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

Definition at line 927 of file vnl_bignum.cxx.

void decrement ( vnl_bignum & bnum )

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

Definition at line 1006 of file vnl_bignum.cxx.

void divide	(	const vnl_bignum &	b1,
		const vnl_bignum &	b2,
		vnl_bignum &	q,
		vnl_bignum &	r
	)

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.

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
	)

void increment ( vnl_bignum & bnum )

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

Definition at line 963 of file vnl_bignum.cxx.

vnl_bignum left_shift	(	const vnl_bignum &	b1,
		int	l
	)

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.

int magnitude_cmp	(	const vnl_bignum &	b1,
		const vnl_bignum &	b2
	)

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 multiply_aux	(	const vnl_bignum &	b,
		Data	d,
		vnl_bignum &	prod,
		Counter	i
	)

multiply a non-infinite vnl_bignum by a "single digit".

Inputs: vnl_bignum reference, single word multiplier, reference to the product, and index of starting storage location to use in product

Definition at line 1048 of file vnl_bignum.cxx.

unsigned short multiply_subtract	(	vnl_bignum &	,
		const vnl_bignum &	,
		unsigned	short,
		unsigned	short
	)

unsigned short normalize	(	const vnl_bignum &	b1,
		const vnl_bignum &	b2,
		vnl_bignum &	u,
		vnl_bignum &	v
	)

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.

vnl_bignum operator *	(	long double	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 336 of file vnl_bignum.h.

vnl_bignum operator *	(	double	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 331 of file vnl_bignum.h.

vnl_bignum operator *	(	int	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 326 of file vnl_bignum.h.

vnl_bignum operator *	(	long	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 321 of file vnl_bignum.h.

vnl_bignum operator *	(	vnl_bignum const &	r1,
		long double	r2
	)			`[inline]`

Definition at line 316 of file vnl_bignum.h.

vnl_bignum operator *	(	vnl_bignum const &	r1,
		double	r2
	)			`[inline]`

Definition at line 311 of file vnl_bignum.h.

vnl_bignum operator *	(	vnl_bignum const &	r1,
		int	r2
	)			`[inline]`

Definition at line 306 of file vnl_bignum.h.

vnl_bignum operator *	(	vnl_bignum const &	r1,
		long	r2
	)			`[inline]`

Definition at line 301 of file vnl_bignum.h.

bool operator!=	(	long	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 418 of file vnl_bignum.h.

vnl_bignum operator%	(	int	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 410 of file vnl_bignum.h.

vnl_bignum operator%	(	long	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 405 of file vnl_bignum.h.

vnl_bignum operator%	(	vnl_bignum const &	r1,
		int	r2
	)			`[inline]`

Definition at line 400 of file vnl_bignum.h.

vnl_bignum operator%	(	vnl_bignum const &	r1,
		long	r2
	)			`[inline]`

Definition at line 395 of file vnl_bignum.h.

vnl_bignum operator+	(	long double	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 280 of file vnl_bignum.h.

vnl_bignum operator+	(	double	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 279 of file vnl_bignum.h.

vnl_bignum operator+	(	int	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 278 of file vnl_bignum.h.

vnl_bignum operator+	(	long	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 277 of file vnl_bignum.h.

vnl_bignum operator+	(	vnl_bignum const &	r1,
		long double	r2
	)			`[inline]`

Definition at line 276 of file vnl_bignum.h.

vnl_bignum operator+	(	vnl_bignum const &	r1,
		double	r2
	)			`[inline]`

Definition at line 275 of file vnl_bignum.h.

vnl_bignum operator+	(	vnl_bignum const &	r1,
		int	r2
	)			`[inline]`

Definition at line 274 of file vnl_bignum.h.

vnl_bignum operator-	(	long double	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 292 of file vnl_bignum.h.

vnl_bignum operator-	(	double	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 291 of file vnl_bignum.h.

vnl_bignum operator-	(	int	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 290 of file vnl_bignum.h.

vnl_bignum operator-	(	long	r2,
		vnl_bignum const &	r1
	)			`[inline]`

Definition at line 289 of file vnl_bignum.h.

vnl_bignum operator-	(	vnl_bignum const &	r1,
		long double	r2
	)			`[inline]`

Definition at line 288 of file vnl_bignum.h.

vnl_bignum operator-	(	vnl_bignum const &	r1,
		double	r2
	)			`[inline]`

Definition at line 287 of file vnl_bignum.h.

vnl_bignum operator-	(	vnl_bignum const &	r1,
		int	r2
	)			`[inline]`

Definition at line 286 of file vnl_bignum.h.

vnl_bignum operator-	(	vnl_bignum const &	r1,
		long	r2
	)			`[inline]`

Definition at line 285 of file vnl_bignum.h.

vnl_bignum operator/	(	long double	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 383 of file vnl_bignum.h.

vnl_bignum operator/	(	double	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 378 of file vnl_bignum.h.

vnl_bignum operator/	(	int	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 373 of file vnl_bignum.h.

vnl_bignum operator/	(	long	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 368 of file vnl_bignum.h.

vnl_bignum operator/	(	vnl_bignum const &	r1,
		long double	r2
	)			`[inline]`

Definition at line 363 of file vnl_bignum.h.

vnl_bignum operator/	(	vnl_bignum const &	r1,
		double	r2
	)			`[inline]`

Definition at line 358 of file vnl_bignum.h.

vnl_bignum operator/	(	vnl_bignum const &	r1,
		int	r2
	)			`[inline]`

Definition at line 353 of file vnl_bignum.h.

vnl_bignum operator/	(	vnl_bignum const &	r1,
		long	r2
	)			`[inline]`

Definition at line 348 of file vnl_bignum.h.

bool operator<	(	long	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 419 of file vnl_bignum.h.

bool operator<=	(	long	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 421 of file vnl_bignum.h.

bool operator==	(	long	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 417 of file vnl_bignum.h.

bool operator>	(	long	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 420 of file vnl_bignum.h.

bool operator>=	(	long	r1,
		vnl_bignum const &	r2
	)			`[inline]`

Definition at line 422 of file vnl_bignum.h.

vnl_bignum right_shift	(	const vnl_bignum &	b1,
		int	l
	)

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

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

Definition at line 1354 of file vnl_bignum.cxx.

void subtract	(	const vnl_bignum &	,
		const vnl_bignum &	,
		vnl_bignum &
	)

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

Definition at line 983 of file vnl_bignum.cxx.

vnl_bignum vnl_math_abs ( vnl_bignum const & x ) [inline]

Definition at line 424 of file vnl_bignum.h.

bool vnl_math_isfinite ( vnl_bignum const & x ) [inline]

Definition at line 428 of file vnl_bignum.h.

bool vnl_math_isnan ( vnl_bignum const & ) [inline]

Definition at line 427 of file vnl_bignum.h.

vnl_bignum vnl_math_sqr ( vnl_bignum const & x ) [inline]

Definition at line 426 of file vnl_bignum.h.

vnl_bignum vnl_math_squared_magnitude ( vnl_bignum const & x ) [inline]

Definition at line 425 of file vnl_bignum.h.

Generated on Fri Nov 21 05:06:16 2008 for core/vnl by

1.5.1

core/vnl/vnl_bignum.h File Reference

Detailed Description

Classes

Functions

Function Documentation