vnl_bignum.h File Reference

Infinite precision integers. More...

#include <iostream>
#include <string>
#include "vnl/vnl_export.h"

Go to the source code of this file.

Classes
class	vnl_bignum
	Infinite precision integers. More...

Namespaces
	vnl_math
	real numerical constants.

Functions
VNL_EXPORT int	magnitude_cmp (const vnl_bignum &, const vnl_bignum &)
	compare absolute values of two vnl_bignums. More...
VNL_EXPORT void	add (const vnl_bignum &, const vnl_bignum &, vnl_bignum &)
	add two non-infinite vnl_bignum values and save their sum. More...
VNL_EXPORT void	subtract (const vnl_bignum &, const vnl_bignum &, vnl_bignum &)
	subtract bmin from bmax (unsigned, non-infinite), result in diff. More...
VNL_EXPORT void	multiply_aux (const vnl_bignum &, unsigned short d, vnl_bignum &, unsigned short i)
	multiply a non-infinite vnl_bignum by a "single digit". More...
VNL_EXPORT unsigned short	normalize (const vnl_bignum &, const vnl_bignum &, vnl_bignum &, vnl_bignum &)
	normalize two vnl_bignums. More...
VNL_EXPORT void	divide_aux (const vnl_bignum &, unsigned short, vnl_bignum &, unsigned short &)
	divide a vnl_bignum by a "single digit". More...
VNL_EXPORT unsigned short	estimate_q_hat (const vnl_bignum &, const vnl_bignum &, unsigned short)
	estimate next dividend. More...
VNL_EXPORT unsigned short	multiply_subtract (vnl_bignum &, const vnl_bignum &, unsigned short, unsigned short)
	calculate u - v*q_hat. More...
VNL_EXPORT void	divide (const vnl_bignum &, const vnl_bignum &, vnl_bignum &, vnl_bignum &)
	divide b2 into b1, getting quotient q and remainder r. More...
VNL_EXPORT vnl_bignum	left_shift (const vnl_bignum &b1, int l)
	left shift (arithmetic) non-infinite vnl_bignum by positive number. More...
VNL_EXPORT vnl_bignum	right_shift (const vnl_bignum &b1, int l)
	right shift (arithmetic) non-infinite vnl_bignum by positive number. More...
VNL_EXPORT void	decrement (vnl_bignum &bnum)
	Subtract 1 from bnum (unsigned, non-infinite, non-zero). More...
VNL_EXPORT void	increment (vnl_bignum &bnum)
	Add 1 to bnum (unsigned, non-infinite). More...
VNL_EXPORT std::ostream &	operator<< (std::ostream &s, vnl_bignum const &r)
	formatted output. More...
VNL_EXPORT std::istream &	operator>> (std::istream &s, vnl_bignum &r)
	simple input. More...
VNL_EXPORT std::string &	vnl_bignum_to_string (std::string &s, const vnl_bignum &b)
	Convert the number to a decimal representation in a string. More...
VNL_EXPORT vnl_bignum &	vnl_bignum_from_string (vnl_bignum &b, const std::string &s)
	Convert the number from a decimal representation in a string. More...
vnl_bignum	operator+ (vnl_bignum const &r1, long r2)
	Returns the sum of two bignum numbers. More...
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. More...
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. More...
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. More...
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. More...
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

add()

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

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

Definition at line 887 of file vnl_bignum.cxx.

decrement()

VNL_EXPORT void decrement

(

vnl_bignum &

bnum

)

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

Definition at line 969 of file vnl_bignum.cxx.

divide()

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

divide_aux()

VNL_EXPORT void divide_aux	(	const vnl_bignum &	b1,
		Data	d,
		vnl_bignum &	q,
		Data &	r
	)

divide a vnl_bignum by a "single digit".

(Refer to Knuth, V.2, Section 4.3.2, exercise 16 for details. A digit here is one data element in the radix 2**2.)

• Inputs: reference to vnl_bignum dividend, single digit divisor d, vnl_bignum quotient, and single digit remainder r

Definition at line 1062 of file vnl_bignum.cxx.

estimate_q_hat()

VNL_EXPORT unsigned short estimate_q_hat	(	const vnl_bignum &	u,
		const vnl_bignum &	v,
		Counter	j
	)

estimate next dividend.

(Refer to Knuth, V.2, Section 4.3.1, Algorithm D for details. This function estimates how many times v goes into u, starting at u's jth digit. A digit here is actually a data element, thought of as being in the radix 2**2.)

• Inputs: reference to vnl_bignum dividend and divisor and starting digit j
• Outputs: estimated number of times v goes into u

Definition at line 1082 of file vnl_bignum.cxx.

increment()

VNL_EXPORT void increment

(

vnl_bignum &

bnum

)

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

Definition at line 928 of file vnl_bignum.cxx.

left_shift()

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

magnitude_cmp()

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

multiply_aux()

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

multiply_subtract()

VNL_EXPORT unsigned short multiply_subtract	(	vnl_bignum &	u,
		const vnl_bignum &	v,
		Data	q_hat,
		Counter	j
	)

calculate u - v*q_hat.

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

• Inputs: reference to vnl_bignum dividend, divisor, estimated result, and index into jth digit of dividend
• Outputs: true number of times v goes into u

Definition at line 1129 of file vnl_bignum.cxx.

normalize()

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

operator *() [1/9]

vnl_bignum operator * ( vnl_bignum const &  r1, vnl_bignum const &  r2  )

inline

Returns the product of two bignum numbers.

Definition at line 302 of file vnl_bignum.h.

operator *() [2/9]

vnl_bignum operator * ( vnl_bignum const &  r1, long  r2  )

inline

Definition at line 307 of file vnl_bignum.h.

operator *() [3/9]

vnl_bignum operator * ( vnl_bignum const &  r1, int  r2  )

inline

Definition at line 312 of file vnl_bignum.h.

operator *() [4/9]

vnl_bignum operator * ( vnl_bignum const &  r1, double  r2  )

inline

Definition at line 317 of file vnl_bignum.h.

operator *() [5/9]

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

inline

Definition at line 322 of file vnl_bignum.h.

operator *() [6/9]

vnl_bignum operator * ( long  r2, vnl_bignum const &  r1  )

inline

Definition at line 327 of file vnl_bignum.h.

operator *() [7/9]

vnl_bignum operator * ( int  r2, vnl_bignum const &  r1  )

inline

Definition at line 332 of file vnl_bignum.h.

operator *() [8/9]

vnl_bignum operator * ( double  r2, vnl_bignum const &  r1  )

inline

Definition at line 337 of file vnl_bignum.h.

operator *() [9/9]

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

inline

Definition at line 342 of file vnl_bignum.h.

operator!=()

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

inline

Definition at line 424 of file vnl_bignum.h.

operator%() [1/5]

vnl_bignum operator% ( vnl_bignum const &  r1, vnl_bignum const &  r2  )

inline

Returns the remainder of r1 divided by r2.

Definition at line 396 of file vnl_bignum.h.

operator%() [2/5]

vnl_bignum operator% ( vnl_bignum const &  r1, long  r2  )

inline

Definition at line 401 of file vnl_bignum.h.

operator%() [3/5]

vnl_bignum operator% ( vnl_bignum const &  r1, int  r2  )

inline

Definition at line 406 of file vnl_bignum.h.

operator%() [4/5]

vnl_bignum operator% ( long  r1, vnl_bignum const &  r2  )

inline

Definition at line 411 of file vnl_bignum.h.

operator%() [5/5]

vnl_bignum operator% ( int  r1, vnl_bignum const &  r2  )

inline

Definition at line 416 of file vnl_bignum.h.

operator+() [1/8]

vnl_bignum operator+ ( vnl_bignum const &  r1, long  r2  )

inline

Returns the sum of two bignum numbers.

Definition at line 279 of file vnl_bignum.h.

operator+() [2/8]

vnl_bignum operator+ ( vnl_bignum const &  r1, int  r2  )

inline

Definition at line 280 of file vnl_bignum.h.

operator+() [3/8]

vnl_bignum operator+ ( vnl_bignum const &  r1, double  r2  )

inline

Definition at line 281 of file vnl_bignum.h.

operator+() [4/8]

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

inline

Definition at line 282 of file vnl_bignum.h.

operator+() [5/8]

vnl_bignum operator+ ( long  r2, vnl_bignum const &  r1  )

inline

Definition at line 283 of file vnl_bignum.h.

operator+() [6/8]

vnl_bignum operator+ ( int  r2, vnl_bignum const &  r1  )

inline

Definition at line 284 of file vnl_bignum.h.

operator+() [7/8]

vnl_bignum operator+ ( double  r2, vnl_bignum const &  r1  )

inline

Definition at line 285 of file vnl_bignum.h.

operator+() [8/8]

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

inline

Definition at line 286 of file vnl_bignum.h.

operator-() [1/9]

vnl_bignum operator- ( vnl_bignum const &  r1, vnl_bignum const &  r2  )

inline

Returns the difference of two bignum numbers.

Definition at line 290 of file vnl_bignum.h.

operator-() [2/9]

vnl_bignum operator- ( vnl_bignum const &  r1, long  r2  )

inline

Definition at line 291 of file vnl_bignum.h.

operator-() [3/9]

vnl_bignum operator- ( vnl_bignum const &  r1, int  r2  )

inline

Definition at line 292 of file vnl_bignum.h.

operator-() [4/9]

vnl_bignum operator- ( vnl_bignum const &  r1, double  r2  )

inline

Definition at line 293 of file vnl_bignum.h.

operator-() [5/9]

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

inline

Definition at line 294 of file vnl_bignum.h.

operator-() [6/9]

vnl_bignum operator- ( long  r2, vnl_bignum const &  r1  )

inline

Definition at line 295 of file vnl_bignum.h.

operator-() [7/9]

vnl_bignum operator- ( int  r2, vnl_bignum const &  r1  )

inline

Definition at line 296 of file vnl_bignum.h.

operator-() [8/9]

vnl_bignum operator- ( double  r2, vnl_bignum const &  r1  )

inline

Definition at line 297 of file vnl_bignum.h.

operator-() [9/9]

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

inline

Definition at line 298 of file vnl_bignum.h.

operator/() [1/9]

vnl_bignum operator/ ( vnl_bignum const &  r1, vnl_bignum const &  r2  )

inline

Returns the division of two bignum numbers.

Definition at line 349 of file vnl_bignum.h.

operator/() [2/9]

vnl_bignum operator/ ( vnl_bignum const &  r1, long  r2  )

inline

Definition at line 354 of file vnl_bignum.h.

operator/() [3/9]

vnl_bignum operator/ ( vnl_bignum const &  r1, int  r2  )

inline

Definition at line 359 of file vnl_bignum.h.

operator/() [4/9]

vnl_bignum operator/ ( vnl_bignum const &  r1, double  r2  )

inline

Definition at line 364 of file vnl_bignum.h.

operator/() [5/9]

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

inline

Definition at line 369 of file vnl_bignum.h.

operator/() [6/9]

vnl_bignum operator/ ( long  r1, vnl_bignum const &  r2  )

inline

Definition at line 374 of file vnl_bignum.h.

operator/() [7/9]

vnl_bignum operator/ ( int  r1, vnl_bignum const &  r2  )

inline

Definition at line 379 of file vnl_bignum.h.

operator/() [8/9]

vnl_bignum operator/ ( double  r1, vnl_bignum const &  r2  )

inline

Definition at line 384 of file vnl_bignum.h.

operator/() [9/9]

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

inline

Definition at line 389 of file vnl_bignum.h.

operator<()

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

inline

Definition at line 425 of file vnl_bignum.h.

operator<<()

VNL_EXPORT std::ostream& operator<<	(	std::ostream &	s,
		vnl_bignum const &	r
	)

formatted output.

Formatted output for bignum.

formatted output.

Definition at line 617 of file vnl_bignum.cxx.

operator<=()

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

inline

Definition at line 427 of file vnl_bignum.h.

operator==()

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

inline

Definition at line 423 of file vnl_bignum.h.

operator>()

bool operator> ( long  r1, vnl_bignum const &  r2  )

inline

Definition at line 426 of file vnl_bignum.h.

operator>=()

bool operator>= ( long  r1, vnl_bignum const &  r2  )

inline

Definition at line 428 of file vnl_bignum.h.

operator>>()

VNL_EXPORT std::istream& operator>>	(	std::istream &	s,
		vnl_bignum &	r
	)

simple input.

Reads a vnl_bignum from a stream.

simple input.

Definition at line 354 of file vnl_bignum.cxx.

right_shift()

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

subtract()

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

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

Definition at line 947 of file vnl_bignum.cxx.

vnl_bignum_from_string()

VNL_EXPORT vnl_bignum& vnl_bignum_from_string	(	vnl_bignum &	b,
		const std::string &	s
	)

Convert the number from a decimal representation in a string.

Definition at line 667 of file vnl_bignum.cxx.

vnl_bignum_to_string()

VNL_EXPORT std::string& vnl_bignum_to_string	(	std::string &	s,
		const vnl_bignum &	b
	)

Convert the number to a decimal representation in a string.

Definition at line 643 of file vnl_bignum.cxx.