core/vnl/vnl_bignum.h File Reference

Infinite precision integers. More...

#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 from bnum (unsigned, non-infinite, non-zero).
void	increment (vnl_bignum &bnum)
	Add 1 to bnum (unsigned, non-infinite).
vcl_ostream &	operator<< (vcl_ostream &s, vnl_bignum const &r)
	formatted output.
vcl_istream &	operator>> (vcl_istream &s, vnl_bignum &r)
	simple input.
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.
vnl_bignum	operator+ (vnl_bignum const &r1, long r2)
	Returns the sum of two bignum numbers.
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, vnl_bignum const &r2)
	Returns the difference of two bignum numbers.
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, vnl_bignum const &r2)
	Returns the product of two bignum numbers.
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, vnl_bignum const &r2)
	Returns the division of two bignum numbers.
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, vnl_bignum const &r2)
	Returns the remainder of r1 divided by 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)

---

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
    Peter Vanroose, June 2009: finally fixed this long standing divide bug
   

Definition in file vnl_bignum.h.

---

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

void decrement

(

vnl_bignum &

bnum

)

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

Definition at line 1000 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 1218 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 959 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 1277 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 1019 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 1040 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 1076 of file vnl_bignum.cxx.

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

Definition at line 419 of file vnl_bignum.h.

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

Returns the remainder of r1 divided by r2.

Definition at line 391 of file vnl_bignum.h.

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

Definition at line 396 of file vnl_bignum.h.

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

Definition at line 401 of file vnl_bignum.h.

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

Definition at line 406 of file vnl_bignum.h.

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

Definition at line 411 of file vnl_bignum.h.

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

Returns the product of two bignum numbers.

Definition at line 297 of file vnl_bignum.h.

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

Definition at line 302 of file vnl_bignum.h.

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

Definition at line 307 of file vnl_bignum.h.

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

Definition at line 312 of file vnl_bignum.h.

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

Definition at line 317 of file vnl_bignum.h.

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

Definition at line 322 of file vnl_bignum.h.

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

Definition at line 327 of file vnl_bignum.h.

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

Definition at line 332 of file vnl_bignum.h.

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

Definition at line 337 of file vnl_bignum.h.

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

Returns the sum of two bignum numbers.

Definition at line 274 of file vnl_bignum.h.

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

Definition at line 275 of file vnl_bignum.h.

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

Definition at line 276 of file vnl_bignum.h.

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

Definition at line 277 of file vnl_bignum.h.

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

Definition at line 278 of file vnl_bignum.h.

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

Definition at line 279 of file vnl_bignum.h.

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

Definition at line 280 of file vnl_bignum.h.

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

Definition at line 281 of file vnl_bignum.h.

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

Returns the difference of two bignum numbers.

Definition at line 285 of file vnl_bignum.h.

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

Definition at line 286 of file vnl_bignum.h.

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

Definition at line 287 of file vnl_bignum.h.

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

Definition at line 288 of file vnl_bignum.h.

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

Definition at line 289 of file vnl_bignum.h.

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

Definition at line 290 of file vnl_bignum.h.

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

Definition at line 291 of file vnl_bignum.h.

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

Definition at line 292 of file vnl_bignum.h.

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

Definition at line 293 of file vnl_bignum.h.

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

Returns the division of two bignum numbers.

Definition at line 344 of file vnl_bignum.h.

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

Definition at line 349 of file vnl_bignum.h.

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

Definition at line 354 of file vnl_bignum.h.

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

Definition at line 359 of file vnl_bignum.h.

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

Definition at line 364 of file vnl_bignum.h.

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

Definition at line 369 of file vnl_bignum.h.

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

Definition at line 374 of file vnl_bignum.h.

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

Definition at line 379 of file vnl_bignum.h.

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

Definition at line 384 of file vnl_bignum.h.

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

Definition at line 420 of file vnl_bignum.h.

vcl_ostream& operator<<	(	vcl_ostream &	s,
		vnl_bignum const &	r
	)

formatted output.

Formatted output for bignum.

Definition at line 657 of file vnl_bignum.cxx.

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

Definition at line 422 of file vnl_bignum.h.

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

Definition at line 418 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 423 of file vnl_bignum.h.

vcl_istream& operator>>	(	vcl_istream &	s,
		vnl_bignum &	r
	)

simple input.

Reads a vnl_bignum from a stream.

Definition at line 404 of file vnl_bignum.cxx.

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

vnl_bignum& vnl_bignum_from_string	(	vnl_bignum &	b,
		const vcl_string &	s
	)

Convert the number from a decimal representation in a string.

Definition at line 707 of file vnl_bignum.cxx.

vcl_string& vnl_bignum_to_string	(	vcl_string &	s,
		const vnl_bignum &	b
	)

Convert the number to a decimal representation in a string.

Definition at line 683 of file vnl_bignum.cxx.

vnl_bignum vnl_math_abs

(

vnl_bignum const &

x

)

[inline]

Definition at line 425 of file vnl_bignum.h.

bool vnl_math_isfinite

(

vnl_bignum const &

x

)

[inline]

Definition at line 429 of file vnl_bignum.h.

bool vnl_math_isnan

(

vnl_bignum const &

)

[inline]

Definition at line 428 of file vnl_bignum.h.

vnl_bignum vnl_math_sqr

(

vnl_bignum const &

x

)

[inline]

Definition at line 427 of file vnl_bignum.h.

vnl_bignum vnl_math_squared_magnitude

(

vnl_bignum const &

x

)

[inline]

Definition at line 426 of file vnl_bignum.h.