Integers of Arbitrary Length ( integer )

Definition

An instance of the data type integer is an integer number of arbitrary length. The internal representation of an integer consists of a vector of so-called digits and a sign bit. A digit is an unsigned long integer (type unsigned long).

#include < LEDA/numbers/integer.h >

Creation

integer	a	creates an instance a of type integer and initializes it with zero.
integer	a(int n)	creates an instance a of type integer and initializes it with the value of n.
integer	a(unsigned int i)	creates an instance a of type integer and initializes it with the value of i.
integer	a(long l)	creates an instance a of type integer and initializes it with the value of l.
integer	a(unsigned long i)	creates an instance a of type integer and initializes it with the value of i.
integer	a(double x)	creates an instance a of type integer and initializes it with the integral part of x.
integer	a(unsigned int sz, const digit* vec, int sign=1)
		creates an instance a of type integer and initializes it with the value represented by the first sz digits vec and the sign.
integer	a(const char* s)	a creates an instance a of type integer from its decimal representation given by the string s.
integer	a(const string& s)	a creates an instance a of type integer from its decimal representation given by the string s.

Operations

The arithmetic operations +, -, *, /, + =, - =, * =, / =, -(unary), + +, - -, the modulus operation (%, % =), bitwise AND (&, & =), bitwise OR (|,| =), the complement (  $\tilde{{}}$ ), the shift operations (< <, > >), the comparison operations <, < =, >, > =, = =, ! = and the stream operations all are available.

int	a.sign()	returns the sign of a.
int	a.length()	returns the number of bits of the representation of a.
bool	a.is_long()	returns whether a fits in the data type long.
long	a.to_long()	returns a long number which is initialized with the value of a. Precondition a.is_long() is true.
double	a.to_double()	returns a double floating point approximation of a.
double	a.to_double(bool& is_double)
		as above, but also returns in is_double whether the conversion was exact.
double	a.to_float()	as above.
string	a.to_string()	returns the decimal representation of a.
integer&	a.from_string(string s)	sets a to the number that has decimal respresentation s.
sz_t	a.used_words()	returns the length of the digit vector that represents a.
digit	a.highword()	returns the most significant digit of a.
digit	a.contents(int i)	returns the i-th digit of a (the first digit is a.contents(0)).
void	a.hex_print(ostream& o)	prints the digit vector that represents a in hex format to the output stream o.
bool	a.iszero()	returns whether a is equal to zero.

Non-member functions

double	to_double(const integer& a)
		returns a double floating point approximation of a.
integer	sqrt(const integer& a)	returns the largest integer which is not larger than the square root of a.
integer	abs(const integer& a)	returns the absolute value of a.
integer	factorial(const integer& n)
		returns n!.
integer	gcd(const integer& a, const integer& b)
		returns the greatest common divisor of a and b.
int	log(const integer& a)	returns the logarithm of a to the basis 2 (rounded down).
int	log2_abs(const integer& a)
		returns the logarithm of | a| to the basis 2 (rounded up).
int	sign(const integer& a)	returns the sign of a.
integer	sqr(const integer& a)	returns a2.
double	double_quotient(const integer& a, const integer& b)
		returns a the best possible floating-point approximation of a/b.
integer	integer::random(int n)	returns a random integer of length n bits.

Implementation

An integer is essentially implemented by a vector vec of unsigned long numbers. The sign and the size are stored in extra variables. Some time critical functions are also implemented in assembler code.