next up previous contents index
Next: Rational Numbers ( rational Up: Number Types and Linear Previous: Number Types and Linear   Contents   Index


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.


next up previous contents index
Next: Rational Numbers ( rational Up: Number Types and Linear Previous: Number Types and Linear   Contents   Index
Christian Uhrig 2017-04-07