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/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(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_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(integer a)	returns a double floating point approximation of a.
integer	sqrt(integer a)	returns the largest integer which is not larger than the square root of a.
integer	abs(integer a)	returns the absolute value of a.
integer	gcd(integer a, integer b)	returns the greatest common divisor of a and b.
int	log(integer a)	returns the logarithm of a to the basis 2.
int	sign(integer a)	returns the sign of a.
integer	sqr(integer a)	returns a2.
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 sparc assembler code.