- Author(s) of this documentation:
- Jacques-Olivier Lachaud
Part of the Arithmetic package.
This module gathers several functions to make computations with integers (either basic types or big integer representations). The main part of the module is the class IntegerComputer, which holds methods but also data to perform computations efficiently.
Integer types and standard arithmetic operations
We use integer types DGtal::int32_t, DGtal::int64_t, and DGtal::BigInteger (integers of arbitrary size). The last type is available only if DGtal was compiled with cmake
-DWITH_GMP=true
...
You may use any of these types or new ones, provided they satisfy the concepts CInteger, as well as its semantic. See also Number and Integer Concepts.
These types provide the standard arithmetic operators +, -, *, /, %, arithmetic comparisons <, <=, >=, >, ==, !=, assignements =, +=, *=, -=, /=, %=.
More elaborate computations with integers
The templated class IntegerComputer is parameterized by a type that is a model of CInteger. Most – but not all – of the methods of this class require the class to be instantiated. Indeed, it allows the instantiation of mutable integer data members, which are then used in all intermediate computations. This is especially useful with GMP big integers, where memory management takes a lot of time. The idea is thus to allocate once and for all these variables.
We list below the main methods:
- static trivial ones: IntegerComputer::isZero, IntegerComputer::isNotZero, IntegerComputer::isPositive, IntegerComputer::isNegative, IntegerComputer::isPositiveOrZero, IntegerComputer::isNegativeOrZero, whose meaning is obvious.
- static min and max methods: IntegerComputer::min, IntegerComputer::max for 2 and 3 arguments.
- euclidean division and remainder: IntegerComputer::getEuclideanDiv.
- floor and ceil division (takes into account the signs of integers): IntegerComputer::floorDiv, IntegerComputer::ceilDiv, IntegerComputer::getFloorCeilDiv
- static greatest common divisor IntegerComputer::staticGcd (for an exceptionnal computation), or non-static greatest common divisor IntegerComputer::gcd and IntegerComputer::getGcd (for many gcd computations).
- continued fraction development: two versions of IntegerComputer::getCFrac(), one where quotients are outputed in a vector, the other where quotients are outputed through a templated output iterator.
- convergents of a fraction specified by its quotients: IntegerComputer::convergents()
- defines the inner types IntegerComputer::Vector2I and IntegerComputer::Vector3I as PointVector<2,Integer> and PointVector<3,Integer> for representing 2D and 3D integer vectors.
- methods for 2D integer vectors: IntegerComputer::reduce() for making the vector irreducible, cross product between two vectors with IntegerComputer::crossProduct() and IntegerComputer::getCrossProduct(), dot product between two vectors with IntegerComputer::dotProduct() and IntegerComputer::getDotProduct()
- extended Euclid algorithm with IntegerComputer::extendedEuclid. Used for instance to compute modular inverses or Bézout vectors. The number of iterations is below \( \log(\max(a,b)) / \log(\phi) \) by Lamé's theorem, where \( \phi=\frac{1+\sqrt{5}}{2} \) is the gold number. The complexity is hence \( O(\log(\max(a,b))) \) for a computational model where standard integer operations are O(1).
typedef IntegerComputer<int32_t> IC;
IC ic;
IC::Vector2I X = ic.extendedEuclid( a, b, c );
bool ok = a * X[ 0 ] + b * X[ 1 ] == c;