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 (    ), 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: Rational Numbers ( rational Up: Number Types and Linear Previous: Number Types and Linear   Contents   Index
Christian Uhrig 2017-04-07